QuickSort

6 07 2008

QuickSort. It’s widely accepted as the fastest generic sorting algorithm around. It’s also very simple. A comment in the last article showed me this Haskell beauty:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

While my C implementations aren’t any where as beautiful, I’m quite satified with their efficiencies. I’ll keep the code to a minimum, and the let the graphs do the talking.

Read the rest of this entry »

Advertisements




Mergesort. Dissected.

4 07 2008

(Note: All code in this under the WTFPL [0]. Except possibly for Stepane Delcroix’s adapted code, which is under the MIT/X11 license)

Very recently, I decided to spend some time coding those standard algorithms that every programmer should know, but I am woefully ignorant of. The plan was to do an algorithm a day. Unfortunately, yesterday night, I started on the Merge sort algorithm, and I found some ancient bash script I wrote to profile and graph the running time of some other sorts (i.e. the bubble sort). Which led to me spending precious time playing around with gnuplot and various program parameters. Expect graphs. Lots of them.

Read the rest of this entry »