11,705,451 members (51,770 online)

# A Fast New Sorting Routine - The Human Sort

, 22 Mar 2005 96.2K 208 20
 Rate this:
Please Sign up or sign in to vote.
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.

## 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

## About the Author

 Web Developer United States
No Biography provided

## Comments and Discussions

 First Prev Next
 My vote of 3 lsatenstein25-Feb-12 3:39 lsatenstein 25-Feb-12 3:39
 Tournament Sort (O(NlgN) selection sort) supercat916-Nov-07 6:15 supercat9 16-Nov-07 6:15
 Re: Tournament Sort (O(NlgN) selection sort) wtu_ben19-Dec-07 14:44 wtu_ben 19-Dec-07 14:44
 For those interested take a look at Radix Sort. Mike Whitenton2-Aug-05 23:29 Mike Whitenton 2-Aug-05 23:29
 Great work TLWallace.NET6-Apr-05 17:05 TLWallace.NET 6-Apr-05 17:05
 Re: Great work Patented14-Jul-05 11:37 Patented 14-Jul-05 11:37
 This is Selection Sort Anonymous1-Apr-05 0:18 Anonymous 1-Apr-05 0:18
 Shell-Metzner Sort TAPhilo31-Mar-05 2:14 TAPhilo 31-Mar-05 2:14
 Waste of bandwidth Byron Goodman29-Mar-05 14:53 Byron Goodman 29-Mar-05 14:53
 Re: Waste of bandwidth Anonymous29-Mar-05 15:42 Anonymous 29-Mar-05 15:42
 Re: Waste of bandwidth aerospaceboy10-Apr-05 8:02 aerospaceboy 10-Apr-05 8:02
 Re: Waste of bandwidth hometoast5-Dec-05 3:34 hometoast 5-Dec-05 3:34
 Re: Waste of bandwidth Joshua Boyle23-May-06 3:42 Joshua Boyle 23-May-06 3:42
 Good thought, but not a fast sort Carl Burke29-Mar-05 14:10 Carl Burke 29-Mar-05 14:10
 Neat! Lou Zher29-Mar-05 14:10 Lou Zher 29-Mar-05 14:10
 Re: Neat! John R. Shaw19-Feb-06 12:55 John R. Shaw 19-Feb-06 12:55
 sorry umnop0022-Mar-05 21:06 umnop00 22-Mar-05 21:06
 Re: sorry technomanceraus23-Mar-05 10:50 technomanceraus 23-Mar-05 10:50
 Re: sorry umnop0023-Mar-05 21:30 umnop00 23-Mar-05 21:30
 Re: sorry Barbara Crane10-Aug-05 5:25 Barbara Crane 10-Aug-05 5:25
 Can be improved easily Troberg22-Mar-05 20:32 Troberg 22-Mar-05 20:32
 Re: Can be improved easily Mike Whitenton2-Aug-05 22:28 Mike Whitenton 2-Aug-05 22:28
 Re: Can be improved easily Troberg2-Aug-05 22:45 Troberg 2-Aug-05 22:45
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Aug-15 7:45 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150819.1 | Last Updated 23 Mar 2005
Article Copyright 2005 by Clark Hay
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid