Earlier in the week I was working on something completely unrelated to programming (sorting some school work actually) and I had an idea about sorting integers using array indices. I finally got around to implementing and benchmarking it in Java this morning.

The process is fairly simple, though it might be kinda hard to explain. To start with I’m going to describe a simplified version that uses a bit more array space than my optimized version.

Imagine you have an array of integers, something like *int myArray[] = {5,9,3,8,4,10,2,8,6,4}; *for example. The first thing the code does is loop through the whole array once to determine the maximum value in the array. In this case that would be max:10. Using this value, we create a second empty array, as follows: *int sorted[] = new int[max+1]; *

Here’s where the trick comes in. Rather than using the array itself to sort the data, we use the array’s indices. This means that we now loop through the original *myArray* and for each value we encounter, we do *sorted[value]++; *

Once we’re done looping through *myArray*, we’re left with:

*sorted[0]=0 sorted[1]=0 sorted[2]=1 sorted[3]=1 sorted[4]=2 *

*sorted[5]=1 sorted[6]=1 sorted[7]=0 sorted[8]=2 sorted[9]=1 *

*sorted[10]=1*

Since array indices are sorted, all we need to do now is loop through the array one more time and printed out the indices that have non-zero values. If the value is >1, we print out the number that many times. This gives us 2,3,4,4,5,6,8,8,9,10. And look, it’s sorted!

With a small-scale array like this, QuickSort is much faster. However with datasets at around 50,000 or more the “ArraySort” method starts to start looking very nice. I recorded and graphed some running times at intervals of 100,000, between 100,000 and 3,000,000. Each array contains n elements generated by a for loop, with each element being set to: *(int) (Math.random() * 1000000);*

Here’s the resulting graph:

I couldn’t believe the results. I changed the ArraySort program to print out the sorted array at the end of the run, just to make sure it was actually sorting, and it was. I guess the difference here is that 1) ArraySort only uses a constant 3 loops and 2)QuickSort is recursive, so with more things to sort more method calls have to be made.

I plan on trying this again using C++ instead of Java later today to see how the performance compares.

T

July 22nd, 2011 at 4:59 PM

See http://en.wikipedia.org/wiki/Counting_sort

July 22nd, 2011 at 6:07 PM

Awesome, thanks for the link. I haven’t really had a lot of experience with different sorting algorithms, aside from the common ones like quick, merge, insertion, etc. I was pretty sure going into this that the concept had been done before, but figured I’d take a stab at it anyway.