Learning Prolog via Examples - Sorting

Part of INTERACTIVE PROLOG GUIDE

Prev

TOC

Next

This lecture covers sort algorithms. Notice the natural and short representation of sort algorithms in Prolog.

---

naive sort

Naive sort is not very effective algorithm. It generates all permutations and then it tests if the permutation is a sorted list.

naive_sort(List,Sorted):-perm(List,Sorted),is_sorted(Sorted).

is_sorted([]).
is_sorted)[_]).
is_sorted([X,Y|T]):-X<=Y,is_sorted([Y|T]).

Naive sort uses the generate and test approach to solving problems which is usually utilized in case when everything else failed. However, sort is not such case.

---

insert sort

Insert sort is a traditional sort algorithm. Prolog implementation of insert sort is based on idea of accumulator.

insert_sort(List,Sorted):-i_sort(List,[],Sorted).
i_sort([],Acc,Acc).
i_sort([H|T],Acc,Sorted):-insert(H,Acc,NAcc),i_sort(T,NAcc,Sorted).

insert(X,[Y|T],[Y|NT]):-X>Y,insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]:-X<=Y.
insert(X,[],[X]).

---

bubble sort

Bubble sort is another traditional sort algorithm which is not very effective. Again, we use accumulator to implement bubble sort.

bubble_sort(List,Sorted):-b_sort(List,[],Sorted).
b_sort([],Acc,Acc).
b_sort([H|T],Acc,Sorted):-bubble(H,T,NT,Max),b_sort(NT,[Max|Acc],Sorted).

bubble(X,[],[],X).
bubble(X,[Y|T],[Y|NT],Max):-X>Y,bubble(X,T,NT,Max).
bubble(X,[Y|T],[X|NT],Max):-X<=Y,bubble(Y,T,NT,Max).

---

merge sort

Merge sort is usually used to sort large files but its idea can be utilized to every list. If properly implemented it could be a very efficient algorithm.

merge_sort([],[]).
merge_sort(List,Sorted):-
	divide(List,L1,L2),merge_sort(L1,Sorted1),merge_sort(L2,Sorted2),
	merge(Sorted1,Sorted2,Sorted).
merge([],L,L).
merge(L,[],L):-L\=[].
merge([X|T1],[Y|T2],[X|T]):-X<=Y,merge(T1,[Y|T2],T).
merge([X|T1],[Y|T2],[Y|T]):-X>Y,merge([X|T1],T2,T).

We can use distibution into even and odd elements of list (other distibutions are also possible).

divide(L,L1,L2):-even_odd(L,L1,L2).

---

quick sort

Quick sort is one of the fastest sort algorithms. However, its power is often overvalued. The efficiency of quick sort is sensitive to choice of pivot which is used to distribute list into two "halfs".

quick_sort([],[]).
quick_sort([H|T],Sorted):-
	pivoting(H,T,L1,L2),quick_sort(L1,Sorted1),quick_sort(L1,Sorted2),
	append(Sorted1,[H|Sorted2]).

pivoting(H,[],[],[]).
pivoting(H,[X|T],[X|L],G):-X<=H,pivoting(H,T,L,G).
pivoting(H,[X|T],L,[X|G]):-X>H,pivoting(H,T,L,G).

Similarly to merge sort, quick sort exploits the divide and conquer method of solving problems.

The above implementation of quick sort using append is not very effective. We can write better program using accumulator.

quick_sort2(List,Sorted):-q_sort(List,[],Sorted).
q_sort([],Acc,Acc).
q_sort([H|T],Acc,Sorted):-
	pivoting(H,T,L1,L2),
	quick_sort(L1,Acc,Sorted1),quick_sort(L1,[H|Sorted1],Sorted)