A Fast New Sorting Routine - The Human Sort

• Download demo project - 24.9 Kb
• Download source - 3.38 Kb

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.