Sorting Quickly

Merge sort and heap sort both run in O(nlgn), which is where the lower limit lies in comparison sort algorithms.

Merge sort is intuitive and fairly straightforward. Heap sort has the advantage of being able to be used in priority queues efficiently.

Then there is quick sort. Quick sort also runs in O(nlgn), but only for its average and best case scenarios. In the worst case, quick sort runs in O(n^2). However, quick sort is preferred over merge sort and heap sort. Why? Because other than the worst case, quick sort runs faster in practice due to its tighter loops. But what about the worst case? The good news is that there is only 1 worst case sequence, which is if at each iteration, we choose the largest number as the pivot. If we use a randomized algorithm of quick sort, the chances of hitting the worst case is 1/n!, which is very low. Hence, in practice, it's worth the risk of hitting the worst case.

Here's my code for quick sort and a test file.
https://gist.github.com/wmwong/6758508#file-quicksort-rb
https://gist.github.com/wmwong/6758508#file-quicksort_test-rb

Fun with Heaps!

It's been a while since my undergraduate and I've forgotten how fun my Computer Science degree was.

I'm re-reading Introduction to Algorithms and having quite a lot of fun with it.

The latest chapter I went over was the chapter on heaps. So I decided to implement some of the data structures and algorithms.

Here is my code for creating heaps (both max and min-heaps) and heap sort.
https://gist.github.com/wmwong/6747122#file-heap-rb

I also created a test file.
https://gist.github.com/wmwong/6747122#file-heap_test-rb

Also introduced along with heaps are priority queues as they go really well together. Here are my implementations for a max and min-priority queue.
https://gist.github.com/wmwong/6747122#file-priority_queue-rb

And of courses tests!
https://gist.github.com/wmwong/6747122#file-priority_queue_test-rb