프롤로그(Prolog ) 언어를 이용한 교환정렬, 합병정렬, 쾌속정렬, 8-queens 구현

1. 개요

 

가. Prolog 란?

 

프롤로그(Prolog)는 논리형 프로그래밍 언어이다.

이름은 '논리 프로그래밍'을 의미하는 프랑스어: programmation en logique에서 온 것이다. 1973년 프랑스 마르세유대학교의 알랭 콜메르(Alan Colmerauer)가 개발한 언어로서, 논리식을 토대로 하여 오브젝트와 오브젝트 간의 관계에 관한 문제를 해결하기 위해 사용한다.

프롤로그는 술어 논리식을 프로그램, 증명하는 것을 계산한다는 것으로 간주하는 관점에서 새로운 계산의 기술 형태를 취하고 있다. 즉, 프로그램 자체는 논리식의 모양으로 만들어지고, 그 프로그램을 실행하는 처리계가 그 증명기로 되어 있다.

추론 기구를 간결하게 표현할 수 있기 때문에 인공지능이나 계산 언어학 분야, 특히 프롤로그가 만들어진 목적이었던 자연언어 처리 분야에서 많이 사용된다.

 

나. 사용한 Prolog 문법

 

1) 변수

대문자나 밑줄(_)로 시작하는 문자, 숫자, 밑줄의 조합으로 된 문자열이 변수의 역할을 한다

 

2) 텀(Terms)

텀, 혹은 스트럭처(Strucuture)는 프롤로그에서 복잡한 데이터를 표현할 때 쓰는 방법이다. 펑터(functor)라 불리는 아톰의 형태를 띤 것을 앞에 쓰고, 인자들(parameters)을 괄호 안에 나열하여 구성된다

 

3) 리스트

리스트는 대괄호([])로 표시되며, 내부적으로는 '.'/2라는 텀을 재귀적으로 사용함으로써 표현된다.

1 .[]는 빈 리스트이다.

2. T가 리스트이고, H가 리스트의 한 요소라고 하면, '.'(H, T) 라는 텀은 리스트가 된다.

H는 머릿요소가 되고, 리스트의 나머지 부분 전체는 꼬리가 된다.

3. 편의를 위해 [H|T] 같이 써서 리스트 맨 앞의 머릿 요소와 나머지 부분 전체를 분리할 수 있다.

 

4) 사실(Fact)

프롤로그에서는 사실(Fact)과 규칙(Rule)들을 제공하여 데이터베이스를 만들고, 이 데이터베이스에 질의를 함으로써 프로그램을 수행하게 된다. 프롤로그에서는 어떤 하나의 사실을 true로 정의하는 것이 가장 기본적인 동작이다. 하나의 사실은 헤드(head)와 그에 딸린 인자들(arguments)로 구성되는 서술식(predicate)으로 표현 된다.

 

5) 규칙(Rule)

프롤로그 프로그램의 또다른 표현방법은 규칙 혹은 클로즈(clause)다. 규칙은 다음과 같이 표현된다.

ex) light(on) :- switch(on).

 

6) 계산

인터프리터에 질의를 입력하면, 그 질의에 맞는 사실을 찾으려고 노력한다. 만약 직접적인 사실이 주어지지 않은 경우, 해당 사실을 결론으로 갖는 규칙들을 만족시키기 위해 재귀적으로 계속 노력한다

 

.

2. Sort using Prolog

 

가. Exchange Sort (sequence sort)

 

1) 교환정렬이란?

 

파일에 있는 모든 레코드의 키 중에서 가장 작은 키를 갖는 레코드를 찾아 맨 앞의 레코드와 교환한다. 다음에는 파일에 있는 두 번째 레코드에서 맨 끝 레코드까지의 키 중에서 가장 작은 키를 갖는 레코드를 찾아 두 번째 레코드와 교환하는데, 이 방법을 교환 정렬이라고 한다. 선택 정렬은 다른 파일에 정렬된 레코드를 기록하는 데 반하여 교환 정렬은 다른 기억 장소를 필요로 하지 않는다.

 

2) 소스코드 분석

 

main 함수	코드 분석 및 정리
list([98,11,7,4,51,20,15,35,25,55, 19,93,77,23,1,59,81,10,28]).   exchangesort:- write('Exchange Sort'),nl, list(E_list), write('start :'),write(E_list),nl, exchange(E_list, E_Sort), write('end :'),write(E_Sort),nl.	% 정렬할 리스트는 프로그램 안에 정의 % 정렬을 할 값은 과제 문서에 정해진 값으로 제한   % 프로그램 실행방법: exchange sort. % 정렬을 시작하기 전에 정렬방식의 이름을 출력 % 정렬할 리스트 변수를 설정 % 초기에 지정된 정렬할 숫자 입력 값을 출력 % 교환정렬 시작 % 최종 정렬된 리스트 출력

 

Sub 함수 #1	코드 분석 및 정리
exchange(X, Result):- e_swap(X, Sorting_X), write('sorting..:'),write(Sorting_X),nl, exchange(Sorting_X, Result).   exchange([X|Y],[X|Z]):- write('next sort:'),write(Y),nl, exchange(Y,Z).   exchange([],[]).	% exchange sort 본 함수 % X : 미정렬 리스트, Result : 정렬된 리스트 % 재귀호출을 통한 Sorting % write : 내부 함수로서 변수를 화면에 출력   % 첫 번째 레코드가 정해지면 두 번째 레코드에서 맨 끝 레코드까지 재정렬 시작     % 맨 끝 레코드까지 도착하면 true 반환

 

Sub 함수 #2	코드 분석 및 정리
e_swap([X,Y|Rest], [Y,X|Rest]):- X>Y.   e_swap([X,Y|Rest], [Z,Y|Rest1]):- X=<Y, e_swap([X|Rest], [Z|Rest1]).	% 입력 받은 리스트의 모든 레코드의 키 중에서 가장 작은 키를 갖는 레코드를 찾아 맨 앞의 레코드와 교환해주는 함수 % 두번째 원소가 맨 앞 원소보다 작은 값이면 swap     % 두번째 원소가 맨 앞의 원소보다 크면, % 두번째 원소의 다음 원소를 탐색

 

 

나. Merge Sort

 

1) 합병정렬이란?

 

하나의 리스트를 정렬하기 위해서 해당 리스트를 n개의 서브리스트로 분할하여 각각을 정렬한 수, 정렬된 n개의 서브리스트로 합병시켜서 정렬시키는 방법.

 

2) 소스코드 분석

 

main 함수	코드 분석 및 정리
list([98,11,7,4,51,20,15,35,25,55, 19,93,77,23,1,59,81,10,28]).   mergesort:- write('Merge Sort'),nl, list(M_list), write('start : '),write(M_list),nl, mergesort(M_list, M_Sort), write('end : '),write(M_Sort),nl.	% 정렬할 리스트는 프로그램 안에 정의 % 정렬을 할 값은 과제 문서에 정해진 값으로 제한   % 프로그램 실행방법: merge sort. % 정렬을 시작하기 전에 정렬방식의 이름을 출력 % 정렬할 리스트 변수를 설정 % 초기에 지정된 정렬할 숫자 입력 값을 출력 % 합병 정렬 시작 % 최종 정렬된 리스트 출력

 

 

Sub 함수 #1	코드 분석 및 정리
mergesort([],[]). mergesort([X],[X]).   mergesort(M_list, M_Sort):-   divide(M_list,Left,Right), write('divide : '),write(Left),write(Right),nl, mergesort(Right, M_Sort1), mergesort(Left, M_Sort2), write('merge :'), write(M_Sort1),write(M_Sort2),nl, conquer(M_Sort1, M_Sort2, M_Sort).	% merge sort 본 함수 % 레코드가 없는 리스트가 들어오거나 % 한 개만 있는 레코드가 들어온 경우 항상 true   % M_list : 미정렬 리스트, M_Sort : 정렬된 리스트 % 분할 리스트의 재귀호출을 통한 Sorting % 리스트를 반으로 분할 % 분할한 리스트 출력 % 분할한 오른쪽 리스트 meresort 재귀호출 % 분할한 왼쪽 리스트 meresort 재귀호출 % 정렬된 왼쪽리스트와 오른쪽리스트출력   % 분할된 왼쪽, 오른쪽 리스트 둘을 정렬하면서 하나로 합병

 

Sub 함수 #2	코드 분석 및 정리
divide([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S], [A,B,C,D,E,F,G,H,I,J],[K,L,M,N,O,P,Q,R,S]). divide([A,B,C,D,E,F,G,H,I,J],[A,B,C,D,E], [F,G,H,I,J]). divide([K,L,M,N,O,P,Q,R,S],[K,L,M,N,O],[P,Q,R,S]). divide([A,B,C,D,E],[A,B,C],[D,E]). divide([P,Q,R,S],[P,Q],[R,S]). divide([A,B,C],[A,B],[C]). divide([A,B],[A],[B]). divide([A],[A],[]). divide([],[],[]).	% 입력받은 리스트를 반으로 분할하는 함수 % 모든 경우의 수에 맞는 함수 존재 % 리스트의 수에 따라 다른 함수 호출 % 19 = 10 + 9   % 10 = 5 + 5   % 9 = 5 + 4 % 5 = 3 + 2 % 4 = 2 + 2 % 3 = 2 + 1 % 2 = 1 + 1 % 1 = 1 + 0 % 0 = 0 + 0

 

Sub 함수 #3	코드 분석 및 정리
conquer(X,[],X). conquer([],X,X).   conquer([X|Rest1], [Y|Rest2], [X|Rest]):- X=<Y, conquer(Rest1, [Y|Rest2],Rest). conquer([X|Rest1], [Y|Rest2], [Y|Rest]):- X>Y, conquer([X|Rest1], Rest2, Rest).	% 분할되었던 리스트를 합병하면서 정렬하는 함수 % 오른쪽리스트가 없으면 왼쪽리스트를 반환 % 왼쪽리스트가 없으면 오른쪽 리스트를 반환   % 왼쪽, 오른쪽리스트의 첫번째 원소끼리 값을 비교한후 작은 값을 선택, 나머지는 다시 재귀호출로 정렬

 

 

다. quick sort

 

1) 쾌속정렬이란?

 

주어진 파일을 특정한 키값보다 작은 값을 갖는 레코드들과 큰 값을 갖는 레코드들로 분리하여, 1개의 파일을 논리적으로 2개의 부 파일로 재배열하고 각각의 부 파일에 대해 순환적으로 같은 퀵 정렬을 적용하여 파일을 정렬하는 방법.

 

2) 소스코드 분석

 

main 함수	코드 분석 및 정리
list([98,11,7,4,51,20,15,35,25,55,19,93,77,23,1,59,81,10,28]).   quicksort:- write('Quick Sort'),nl, list(Q_list), write('start :'),write(Q_list),nl, quick(Q_list, Q_Sort), write('end :'),write(Q_Sort),nl.	% 정렬할 리스트   % 프로그램 실행방법: quicksort. % 정렬을 시작하기 전에 정렬방식의 이름을 출력 % 정렬할 리스트 변수를 설정 % 초기에 지정된 정렬할 숫자 입력 값을 출력 % 쾌속 정렬 시작 % 최종 정렬된 리스트 출력

 

Sub 함수 #1	코드 분석 및 정리
quick([Z|List], Result):- q_swap([Z|List], Sorting_X), divide(Sorting_X,Left,[Z],Right), write('divide :'),write(Left),write([Z]),write(Right),nl, quick(Left, Q_Sort1), quick(Right,Q_Sort2), write('merge :'),write(Q_Sort1),write([Z]),write(Q_Sort2),nl, merge(Q_Sort1,[Z],Merge), merge(Merge,Q_Sort2,Result). quick(X,X).	%quick sort의 본 함수 % 첫번째 노드를 피벗으로 삼아 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 swap 한다. % 피벗을 중심으로 임시정렬된 리스트를 왼쪽리스트와 오른쪽리스트로 분할한다. % 왼쪽의 리스트를 다시 퀵소트한다. % 오른쪽의 리스트를 다시 퀵소트한다. % 왼쪽리스트, 피벗, 오른쪽리스트를 병합한다. % 더이상 정렬할 수 없으면 함수는 종료한다.

 

Sub 함수 #2	코드 분석 및 정리
q_swap([A,B|Rest],[B,C|Sort]):- A>B, q_swap([A|Rest],[C|Sort]). q_swap([A,B|Rest],[C,B|Sort]):- A=<B,q_swap([A|Rest],[C|Sort]). q_swap([A],[A]).	% 피벗보다 작으면 좌측으로 이동  % 피벗보다 크면 우측으로 이동

 

 

Sub 함수 #3	코드 분석 및 정리
divide([X|List],[X|List1],[Z],List2):- X =\= Z, divide(List,List1,[Z],List2). divide([X|List],[],[Z], List):- X = Z.	% 리스트를 입력받고 피벗을 중심으로 좌측리스트 우측리스트로 분할 % 피벗과 같은 값을 찾을 때 까지 우측으로 이동 % 피벗을 찾으면 좌측은 왼쪽리스트, 우측은 오른쪽리스트

 

 

4. 출력화면

가. exchange sort

 

 

나. merge sort

 

다. quick sort

 

라. 8-queens

 

5. 소스코드

 

가. exchange sort

 

% Author: AmericanoJH (americano@korea.ac.kr) % Date: 2012-05-26   % Exchange Sort % 정렬할 리스트 정의 list([98,11,7,4,51,20,15,35,25,55,19,93,77,23,1,59,81,10,28]).   % 프로그램 시작 : exchangesort. exchangesort:- write('Exchange Sort'),nl, list(E_list), write('start :'),write(E_list),nl, exchange(E_list, E_Sort), write('end :'),write(E_Sort),nl.   % exchange(미정렬 리스트, 정렬된 리스트) % 의 재귀호출을 통한 Sorting exchange(X, Result):- e_swap(X, Sorting_X), write('sorting..:'),write(Sorting_X),nl, exchange(Sorting_X, Result).   % 가장 맨 앞의 원소를 가장 작은 값을 찾아 swap % 완료하면 그 원소 뒤의 리스트를 정렬 exchange([X|Y],[X|Z]):- write('next sort:'),write(Y),nl, exchange(Y,Z).   % exchange sort가 리스트의 끝에 도달하였을 끝났을 경우 exchange([],[]).   % 두번째 원소가 맨 앞 원소보다 작은 값이면 swap e_swap([X,Y|Rest], [Y,X|Rest]):- X>Y. % 두번째 원소가 맨 앞의 원소가 크면, 맨 앞 원소보다 작은 두번째 원소의 다음 원소를 탐색 e_swap([X,Y|Rest], [Z,Y|Rest1]):- X=<Y, e_swap([X|Rest], [Z|Rest1]).

 

나. merge sort

 

% Author: AmericanoJH (americano@korea.ac.kr) % Date: 2012-05-27 % merge sort % 정렬할 리스트 list([98,11,7,4,51,20,15,35,25,55,19,93,77,23,1,59,81,10,28]).   % 프로그램시작 : mergesort. mergesort:- write('Merge Sort'),nl, list(M_list), write('start : '),write(M_list),nl, mergesort(M_list, M_Sort), write('end : '),write(M_Sort),nl.   mergesort([],[]). mergesort([X],[X]).   mergesort(M_list, M_Sort):- % 리스트를 반으로 분할 divide(M_list,Left,Right), % 분할한 리스트 출력 write('divide : '),write(Left),write(Right),nl, % 분할한 오른쪽 리스트 meresort 재귀호출 mergesort(Right, M_Sort1), % 분할한 왼쪽 리스트 meresort 재귀호출 mergesort(Left, M_Sort2), % 정렬된 왼쪽리스트와 오른쪽리스트출력 write('merge : '),write(M_Sort1),write(M_Sort2),nl, % 분할된 리스트 둘을 정렬하면서 하나로 합병 conquer(M_Sort1, M_Sort2, M_Sort).5     % 리스트의 수에 따라 다르게 분할 % 19 = 10 + 9 divide([A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S], [A,B,C,D,E,F,G,H,I,J],[K,L,M,N,O,P,Q,R,S]). % 10 = 5 + 5 divide([A,B,C,D,E,F,G,H,I,J],[A,B,C,D,E],[F,G,H,I,J]). % 9 = 5 + 4 divide([K,L,M,N,O,P,Q,R,S],[K,L,M,N,O],[P,Q,R,S]). % 5 = 3 + 2 divide([A,B,C,D,E],[A,B,C],[D,E]). % 4 = 2 + 2 divide([P,Q,R,S],[P,Q],[R,S]). % 3 = 2 + 1 divide([A,B,C],[A,B],[C]). % 2 = 1 + 1 divide([A,B],[A],[B]). % 1 = 1 + 0 divide([A],[A],[]). % 0 = 0 + 0 divide([],[],[]).   % 오른쪽리스트가 없으면 왼쪽리스트를 반환 conquer(X,[],X). % 왼쪽리스트가 없으면 오른쪽 리스트를 반환 conquer([],X,X).   % 왼쪽, 오른쪽리스트의 첫번째 원소끼리 값을 비교한후 작은 값을 선택, 나머지는 다시 재귀호출로 정렬 conquer([X|Rest1], [Y|Rest2], [X|Rest]):- X=<Y, conquer(Rest1, [Y|Rest2],Rest). conquer([X|Rest1], [Y|Rest2], [Y|Rest]):- X>Y, conquer([X|Rest1], Rest2, Rest).

 

다. quick sort

 

% Author: AmericanoJH (americano@korea.ac.kr) % Date: 2012-05-28 % Quick Sort   % 정렬할 리스트 list([98,11,7,4,51,20,15,35,25,55,19,93,77,23,1,59,81,10,28]).   % 프로그램 실행: quicksort. quicksort:- write('Quick Sort'),nl, list(Q_list), write('start :'),write(Q_list),nl, quick(Q_list, Q_Sort), write('end :'),write(Q_Sort),nl.     quick([Z|List], Result):- % 첫번째 노드를 피벗으로 삼아 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 swap 한다 q_swap([Z|List], Sorting_X), % 피벗을 중심으로 임시정렬된 리스트를 왼쪽리스트와 오른쪽리스트로 분할한다. divide(Sorting_X,Left,[Z],Right), write('divide :'),write(Left),write([Z]),write(Right),nl, % 왼쪽의 리스트를 다시 퀵소트한다. quick(Left, Q_Sort1), % 오른쪽의 리스트를 다시 퀵소트한다. quick(Right,Q_Sort2), write('merge :'),write(Q_Sort1),write([Z]),write(Q_Sort2),nl, % 왼쪽리스트, 피벗, 오른쪽리스트를 병합한다. merge(Q_Sort1,[Z],Merge), merge(Merge,Q_Sort2,Result).   % 더이상 정렬할 수 없으면 함수는 종료한다. quick(X,X).   % 피벗보다 작으면 좌측으로 이동 q_swap([A,B|Rest],[B,C|Sort]):- A>B, q_swap([A|Rest],[C|Sort]). % 피벗보다 크면 우측으로 이동 q_swap([A,B|Rest],[C,B|Sort]):- A=<B,q_swap([A|Rest],[C|Sort]).   q_swap([A],[A]).   % 리스트를 입력받고 피벗을 중심으로 좌측리스트 우측리스트로 분할 % 피벗과 같은 값을 찾을 때 까지 우측으로 이동 % 피벗을 찾으면 좌측은 왼쪽리스트, 우측은 오른쪽리스트 divide([X|List],[X|List1],[Z],List2):- X =\= Z, divide(List,List1,[Z],List2).   divide([X|List],[],[Z], List):- X = Z.

 

라. 8-queens

 

% Author: AmericanoJH (americano@korea.ac.kr) % Date: 2012-05-28 % 8-queens    % 퀸의 위치를 나타내는 리스트 array1(List):-  List = [[1,_],[2,_],[3,_],[4,_],[5,_],[6,_],[7,_],[8,_]]. % 퀸이 가질 수 있는 열의 위치 getdata(X):-  X=1;X=2;X=3;X=4;X=5;X=6;X=7;X=8. %프로그램 실행 : queen. queen:-  % 구할 수 있는 모든 리스트들을 L에 저장한다.  % findall : 내부 함수, 가능한 답(List1)이 존재할 때마다 그 답을 리스트(L)에 순차적으로 저장  findall(List,queen(List),L),  length(L,M),  write('total : '), write(M),nl,  queen(List1), write(List1).  % 구한 답의 개수를 구한다.  % length : 내부 함수, 리스트의 길이 반환  % 답의 개수 출력  % 8-queen이 가능한 답을 하나씩 출력   queen(List1):-  %퀸의 초기 리스트를 생성한다.  array1([A1|List]),!,  %퀸의 위치[1,X]에서 X를 지정  check1(A1,A2),  %나머지 퀸의 위치를 지정  check_list([A2|List],[A2|List1]),  %위치가 맞는지 확인  check_list2(List1). check_list([A],[A]). check_list([A,B|Rest],[A,X|Rest1]):-  %퀸의 위치가 [Row,Col]라면  %Col의 위치를 지정  check1(B,X),  %Row-1 번째 퀸과 Row 번째 퀸의 Col의 위치가 겹치는지 확인  check2(A,X),  %Row-1 번째 퀸과 Row 번째 퀸의 대각선의 위치가 겹치는지 확인  check3(A,X),  check_list([A|Rest],[A|Rest1]).   check_list2([A]). check_list2([A,B|Rest]):-  %8개의 퀸의 위치가 올바르게 되었는지 확인  check_list2([A|Rest]),!,  check2(A,B),  check3(A,B),  check_list2([B|Rest]),!. check1([A,B],[A,C]):-  %퀸의 Col 위치 지정  getdata(C).   check2([A,B],[C,D]):-  %퀸의 행의 위치 확인  B =\= D. check3([A,B],[C,D]):-  %퀸의 대각선 위치 확인  X is A-C,  Y is B-D,  abs(X,X1),  abs(Y,Y1),  X1 =\= Y1.