This is the second in my series of algorithm posts in trying to become a better programmer. Counting sort is possibly my favorite of the sorting algorithms because it looks so complicated at first glance, but its actually very simple and graceful.

The principle behind counting sort is to store a count of each value that appears in the array and use that as a way to place the original value in the resulting array. It's generally used for fairly low numbered positive integer values, and the running time of the algorithm depends on both the number of elements, and the range of values within the array. For example, a simple array with the values (1, 6, 1000000000) will take a LONG time to be sorted, even though there are only three elements because at some point there will be a loop from 0 to 1000000000. Also note that the sort method requires a parameter k, which is the maximum value contained in the array.

If you don't understand the algorithm, it would probably be better to read the wikipedia article instead of trying to rely on my brief and badly written version.

Language Choice

I decided to do a version in Python because I've never really used the language much and I figured it was a good way to give it a try. My first impressions are pretty positive, and I love how it uses indenting as part of the language semantics.

My C Implementation:

My Python Implementation

This is the first post in my quest to be a better programmer. Quicksort is one of the 'standard' sorting algorithms. Its fairly easy to implement, and normally runs fairly quickly. I've implemented quicksort in both C and Scheme, although I think my Scheme implementation is more of a pseudo-quicksort due to a reluctance to break from the functional style encouraged by Scheme syntax.

Quicksort Overview

The 'Partition' algorithm is at the core of a quicksort implementation, and this partitions an array into groups of 'less than x' and 'more than x', with x itself being placed inbetween. The final position of x is the value returned by the partition function. In my simple implementation, the choice of x remains constant (either the first or last element). Randomizing this is the main way to increase the worst case speed of this algorithm.

After partitioning the initial input, quicksort recursivly calls itself on the 'less-than' and 'more-than' groups returned from partition. The result is a chain of recursive calls which continues until quicksort is trying to sort a single number.

Check out Wikipedia to get a more in-depth understanding of quicksort.

Special Property

Quicksort is good because it sorts 'in-place'. In other words it doesn't use a secondary array to sort the elements into. This can save a lot of memory, especially if you are sorting a list of complicated data structures which are a few KB each.

My C Implementation

My Scheme Implementation

I think its worth noting that the scheme implementation doesn't exactly sort 'in-place'. Instead it recursivly builds up secondary lists then joins them together at the end as the return value instead of moving the elements around in a single list. However the amount of memory used should still be in the order of the number of elements in the input array unlike other sorting algorithms (counting-sort, and bucket-sort come to mind) which use secondary arrays which do not form part of the solution.

(define pHelper (lambda (all chk l m)
                  (cond ((null? all) (cons l (cons chk (cons m '()))))
                        (else
                        (let ((x (car all)))
                          (if (<= x chk) 
                              (pHelper (cdr all) chk (cons x l) m)
                              (pHelper (cdr all) chk l (cons x m))))))))

(define partition (lambda (l)
                      (pHelper (cdr l) (car l) '() '())))



(define quicksort (lambda (l)
                    (cond ((null? l) l)
                          (else
                          (let ((lx (partition l)))
                            (append (quicksort (car lx)) (cons (cadr lx) (quicksort (caddr lx)))))))))

In an attempt to be a better programmer, and even better student, I'm undertaking a new mini-project: I will make a series of blog posts whereby I describe a particular (well known) algorithm, then provide an implementation in 2 different programming languages.

Skills++

Doing this should help with two things.

1) It should make me remember these algorithms in more detail. Most of these algorithms are so very clever that it will certainly help if I know them by heart.

2) At a time when I don't need to use anything other than Java it will help to keep me comfortable with other languages.

Languages

I'm certainly going to do every algorithm in C, probably not with the best C code, but certainly C code that works. Also I'll probably switch in and out of a functional language such as Scheme and something like VBA to keep it old-school.

Algorithms and Links

I will update this post with links when I make each post. Also check out the Operation-Algorithm tag in my tag cloud for easy access.

Quicksort
Counting Sort
BucketSort (love this one)
Heapsort (including the making of a Max-heap)
Binary Search Tree creation and traversal

Stay tuned!