Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / Visual Basic
Article

A Fast New Sorting Routine - The Human Sort

Rate me:
Please Sign up or sign in to vote.
2.57/5 (28 votes)
22 Mar 20053 min read 119.3K   359   20   23
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.

VB
    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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 3 Pin
lsatenstein25-Feb-12 3:39
lsatenstein25-Feb-12 3:39 
GeneralTournament Sort (O(NlgN) selection sort) Pin
supercat916-Nov-07 6:15
supercat916-Nov-07 6:15 
GeneralRe: Tournament Sort (O(NlgN) selection sort) Pin
wtu_ben19-Dec-07 14:44
wtu_ben19-Dec-07 14:44 
GeneralFor those interested take a look at Radix Sort. Pin
Mike Whitenton2-Aug-05 23:29
Mike Whitenton2-Aug-05 23:29 
GeneralGreat work Pin
Terence Wallace6-Apr-05 17:05
Terence Wallace6-Apr-05 17:05 
GeneralRe: Great work Pin
Patented14-Jul-05 11:37
sussPatented14-Jul-05 11:37 
GeneralThis is Selection Sort Pin
Anonymous1-Apr-05 0:18
Anonymous1-Apr-05 0:18 
GeneralShell-Metzner Sort Pin
TAPhilo31-Mar-05 2:14
TAPhilo31-Mar-05 2:14 
GeneralWaste of bandwidth Pin
Byron Goodman29-Mar-05 14:53
Byron Goodman29-Mar-05 14:53 
GeneralRe: Waste of bandwidth Pin
Anonymous29-Mar-05 15:42
Anonymous29-Mar-05 15:42 
GeneralRe: Waste of bandwidth Pin
aerospaceboy10-Apr-05 8:02
aerospaceboy10-Apr-05 8:02 
GeneralRe: Waste of bandwidth Pin
hometoast5-Dec-05 3:34
hometoast5-Dec-05 3:34 
GeneralRe: Waste of bandwidth Pin
Joshua Boyle23-May-06 3:42
Joshua Boyle23-May-06 3:42 
GeneralGood thought, but not a fast sort Pin
29-Mar-05 14:10
suss29-Mar-05 14:10 
GeneralNeat! Pin
Lou Zher29-Mar-05 14:10
sussLou Zher29-Mar-05 14:10 
GeneralRe: Neat! Pin
John R. Shaw19-Feb-06 12:55
John R. Shaw19-Feb-06 12:55 
Good answer! Smile | :)

It reminds me of when I started programming, it did not realy matter that I was reinventing a few wheels. What I was learning was far more important. I "invented" the most commonly used (well known) line drawing algorithm (forgot name), how was I to know someone had wrote a paper on it years ealier (no Web then). All it took was some graphing paper and an understanding of basic algebra.

INTP
Every thing is relative...
Generalsorry Pin
umnop0022-Mar-05 21:06
umnop0022-Mar-05 21:06 
GeneralRe: sorry Pin
technomanceraus23-Mar-05 10:50
technomanceraus23-Mar-05 10:50 
GeneralRe: sorry Pin
umnop0023-Mar-05 21:30
umnop0023-Mar-05 21:30 
GeneralRe: sorry Pin
Barbara C10-Aug-05 5:25
Barbara C10-Aug-05 5:25 
QuestionCan be improved easily Pin
Troberg22-Mar-05 20:32
Troberg22-Mar-05 20:32 
AnswerRe: Can be improved easily Pin
Mike Whitenton2-Aug-05 22:28
Mike Whitenton2-Aug-05 22:28 
GeneralRe: Can be improved easily Pin
Troberg2-Aug-05 22:45
Troberg2-Aug-05 22:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.