VB6: Sorting algorithms (sort array, sorting arrays)

[Ellis Dee]

The most interesting feature of snake sort is that the more ordered the array is initially, the faster it runs. Each alogorithm has its own unique worst case scenario. Quick sort's worst case appears to be a camel hump, such as:

.1
.....5
.........9
.......7
...3

This puts the first pivot in the worst possible place, and it goes downhill from there. To see this in action, add this to the end of the seAscending Case in the GenerateArray() function:

            For i = 0 To 24
                mlngLines(i) = i * 4 + 1
                mlngLines(49 - i) = (i + 1) * 4 - 1
            Next

It would be logical to conclude that snake sort's worst case is alternating blocks of two. To see this, add this to the end of the seDescending Case:

            For i = 0 To 48 Step 2
                mlngLines(i) = (i * 2) + 3
                mlngLines(i + 1) = (i * 2) + 1
            Next

Finally, rename the SnakeSort() function to HeapSort(), and rename HeapSort() to something like HeapSortOld().

Snakesort is far more efficient on already ordered lists; virtually equal to bubblesort. It really shines on descending lists, where it can transform the array by looping only halfway through it and swapping the ends. (Comment out the added code from above to see it on ascending and descending lists.)

Most importantly, it's absolute worst case scenario is light years faster than quicksort's worst case. (Both scenarios are, IMO, unlikely in the extreme.) Given that the Time numbers are a rough approximation, where exchanges are assumed to take twice as long as comparisons and non-array comparisons and assignments are ignored, these are the Time numbers from the graphical screen:

Best case (ascending):
Quicksort: 317
Snakesort: 50 (absolute minimum + 1)

Descending:
Quicksort: 368
Snakesort: 100

Quicksort's worst case: (camel hump)
Quicksort: 884
Snakesort: 199

Snakesort's worst case: (thatched)
Quicksort: 408
Snakesort: 510

Random shuffle:
Quckisort: (roughly) 500
Snakesort: (roughly) 560

As you can see, snake sort approaches quicksort efficiency on randomly ordered lists, but gets much faster the moment any order presents itself, unlike quicksort.

(I find it odd that snake sort seems to process its "worst case" faster than it handles an arbitrary random case, but whatever.)