A Fast New Sorting Routine - The Human Sort
2.57/5 (28 votes)
Mar 23, 2005
3 min read
121161
363
A new and fast sorting routine for your projects.
Introduction
The bit of code below is an in-place sorting routine that, by and large, is faster than the Shell Sort - nearly as fast as Quick Sort, and in some cases faster. It is stable, easy to implement, is not recursive, and does not use the stack. There is little difference in its speed no matter how the list/array is ordered. Overall, I believe you will find it very useful to use for any sorting needs. Any feedback would be appreciated.
Background
As I laid in bed one night, thinking about a couple of sorting routines I had used in a recent project, I began to tinker with the idea of creating my own routine. Since a computer is much like a person without vision, I tried to imagine how (as a blind person) I might sort a list of items in Braille. In a matter of a few minutes, the algorithm below occurred to me. I got up, wrote it down in rough form, and then fell asleep. The next morning I set up a simple program to test the algorithm - and it worked beautifully.
As the code comments below indicate, we start by using a simple scan of the list to see if it is already sorted. If not, we start scanning our list below the first item to find the smallest item. Once the smallest item is found, we compare it to our current list item. If the smallest item found is smaller than our current item then we perform a swap. We then move down to the next item in our list/array and repeat the process and keep doing this until we are done.
The process is so simple that I'm surprised no one has thought of it before. As the sort progresses, the list gets shorter and goes faster and faster ...
I think you will find that the swapping of items is reduced to an absolute minimum in this method. On unsorted lists, it performs very well indeed, - but on lists that are very nearly sorted, you should probably use the Shell sort. I made an initial attempt to incorporate the Shell Sort (and a modified/enhanced version of it), but had mixed results (which depended on how sorted the list already was).
I'd love to get some feedback on my approach - especially if you can suggest any improvements. Feel free to use the code, and download the sample demo program and source code and experiment with it.
Please note that I used Microsoft's new Visual Basic. NET 2005 beta program to write and compile the code. With a few tweaks, it should readily run on other software platforms.
Using the code
The code below sorts in ascending format, A to Z. Converting it to descending format is fairly easy (an exercise I will leave to you - unless you need help). As it is listed below, the code is set up to sort strings from a ListBox, but it can easily be adapted to sort numbers or records or whatever you are wanting to sort.
Private Sub HumanSort()
'HumanSort - Intellectual copyright of Clark Hay - created on 02/15/2005
'This is a unique and very fast in-place sort.
'I wanted something that sorts like
'a blind human might, but at computer speeds.
'The basic idea is to scan the list/array
'first to see if it is already sorted.
'If it is, then we're done.
'If the list/array is almost sorted then you can use the Shell sort.
'Otherwise use the Human sort.
'Starting with the item below the current item in our list/array -
'we scan our list/array to find the smallest item.
'When the smallest item is found, we compare it to our current item.
'If the smallest item found is smaller
'than our current item then we perform a swap.
'We then move down to the next item in
'or list/array and repeat the process.
'We keep doing this till we are done.
'This is a simple and quick process.
'I'm surprised no one has thought of it before.
'As the sort progresses, the list gets shorter and goes faster and faster ...
'The swapping of items is reduced to the absolute minimum in this method.
'On unsorted lists it performs very well indeed, -
'but on lists that are very nearly sorted, you should use the Shell sort.
'The Human Sort does not use recursion
'& doesn't have stack overflow problems.
Dim i As Integer
Dim numRecs As Integer
Dim tempRec As String
Dim NextSmallRec As String
Dim NextSmallIndex As Integer
Dim CurrentRec As String
Dim numsorted As Integer
Dim Ascending As Integer
'===> Get number of records in database
numRecs = ListBox1.Items.Count - 1
'Set our counter to 0
numsorted = 0
'***************************************************
'* Here is where we see if our items are sorted *
'***************************************************
'Set our counter to zero
Ascending = 0
If numRecs < 2 Then
GoTo VeryEnd '===> if only 1 or 0 items, then there is nothing to sort
Else
'===> See how many items are in descending or ascending order:
For i = 0 To numRecs - 1
If ListBox1.Items(i) <= ListBox1.Items(i + 1) Then
Ascending = Ascending + 1
End If
Next
End If
'===> if our list is already sorted in ascending order,
' then there is nothing to sort
If Ascending = numRecs Then GoTo VeryEnd
'I've commented out the next 4 lines for a reason:
'As you play with the demo sort program,
'you will notice there are times -
'when the ShellSort out-performs
'the Human Sort and the ShellSortEnhanced.
'I haven't yet determined which sort to use.
'It all depends on a number of factors that I have yet to figure out.
'If Ascending > Int(numRecs * 0.9) Then
'ShellSort()
'GoTo VeryEnd
'End If
'===> otherwise we'll default to our ascending Human sort routine:
'***************************************************
'* This is the ascending version of the Human sort *
'***************************************************
Do While numsorted < numRecs
'===> Get the zip code from the current record in our list
CurrentRec = ListBox1.Items(numsorted)
NextSmallIndex = numsorted
NextSmallRec = ListBox1.Items(NextSmallIndex)
For i = (numsorted + 1) To numRecs
'===> see if the next zipcode down
' is > than what we've found so far
If NextSmallRec > ListBox1.Items(i) Then
'===> If we've found something
' smaller or = then get it's index
NextSmallIndex = i
'===> and record it's value to see
' if anything is smaller than it
NextSmallRec = ListBox1.Items(i)
End If
Next
If NextSmallIndex >= numsorted + 1 Then
'===> Now that we know the smallest item
' in our list, we see if we need to swap
If CurrentRec > NextSmallRec Then
tempRec = ListBox1.Items(numsorted)
ListBox1.Items(numsorted) = ListBox1.Items(NextSmallIndex)
ListBox1.Items(NextSmallIndex) = tempRec
ElseIf CurrentRec = NextSmallRec Then
numsorted = numsorted + 1 '
tempRec = ListBox1.Items(numsorted)
ListBox1.Items(numsorted) = ListBox1.Items(NextSmallIndex)
ListBox1.Items(NextSmallIndex) = tempRec
End If
End If
'===> Now we can increment the number of records we have sorted
numsorted = numsorted + 1
'===> and we keep going till we are done
Loop
VeryEnd:
End Sub
Points of Interest
If you download the demo code, you will also find two implementations of the Shell sort. One is fairly generic, but the other uses an array of predetermined gap sizes that outperforms any other such predetermined gap list I've seen.
The demo lets you sort though a list of 10,000 numbers (sorted as strings) using the Human sort, the generic Shell sort and an enhanced Shell sort. You can opt to select a randomly generated list, a descending list, an ascending list, a list that is half ascending and half descending, one that is 75% descending and 25% random, and one that is 75% ascending and 25% random.
The sorting times for each method are shown in seconds and milliseconds. As I said at the beginning, the sorting time for the Human sort is fairly constant - no matter how the list/array is ordered.
History
This is version 1.0.