Posts Tagged ‘algorithm’

Naive Sort in Prolog

October 15, 2011

The simplest way to code a sort in Prolog is to describe what a sorted list looks like.  A sorted list is a permutation of some given list such that elements that appear earlier in the list are smaller than elements that appear later in the list.  In SWI Prolog:

srt(X,Y) :- permutation(X,Y), isSrt(Y).

isSrt([]).
isSrt([_]).
isSrt([H,I|J]) :- H=<I, isSrt([I|J]).

The beauty of this solution is that Prolog does all the dirty work of finding a sorted Y for our given X. The darker side is that Prolog’s satisfaction mechanism carries out a brute force search through all possible permutations of the given list. This is dangerous; compare the runtimes of our naive sort and the Prolog built-in sort (which is decidedly less naive):

% 5 seconds vs. something < 0.01 seconds
reverse([1,2,3,4,5,6,7,8,9,10],X), profile(srt(X,Y)).
reverse([1,2,3,4,5,6,7,8,9,10],X), profile(msort(X,Y)).

Not great, and notice how fast the worst case time of O(n!) grows:

% 55 seconds vs. something < 0.01 seconds
reverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(srt(X,Y)).
reverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(msort(X,Y)).

This is to be expected; if we want to be picky about how the job gets done, we can be more explicit in our description. So let’s ignore performance and and see how to write a declarative “permutation” predicate from scratch.

(more…)

Advertisements

An Empirical Analysis of QuickSelect and QuickMedian

September 28, 2011

The QuickSelect algorithm is an efficient way to find the N-th largest element in a list. The QuickMedian algorithm uses QuickSelect to efficiently find the middle element(s) of the array.

This blog post sketches how QuickSelect and QuickMedian work in general and in my Java implementation. The bulk of the post discusses the plot of QuickMedian vs. SortMedian’s runtime shown below (click the image for more details).

Runtime of QuickMedian and SortMedian Trials, sorted by trial conditions to show regularities

(more…)