VB6: Sorting algorithms (sort array, sorting arrays)

[Ellis Dee]

Not sure which one yet though, it seems like a toss up between Stability and Speed.

These are the parameters as it stands

Public Function SortArrayX(ByVal ArrayPtr As Long, SortFieldElement As Variant, Optional Descending As Boolean = False) as boolean

Merge sort is both stable and fast, plus it has the bonus of having no worst case; it's always fast. And as I discussed upthread, if you're going to include a Descending option, you pretty much have to use a stable algorithm. (There is just no relevance to the direction of an unstable sort; ascending and descending don't matter. Just change the direction you iterate the array after sorting.) I really can't see using any other algorithm if your going to create a one-stop sorting function. The code sprawl is annoying, but whaddya gonna do?

A generic UDT array sorter would be one of the most impressive things I could imagine in VB6, but I'm not sure of the utility of it. I have in the past used sorted UDT arrays, but as comfortable as I am with sorting code, even I didn't physically sort the UDT array. Instead, I built two-dimensional variant index arrays and sorted those. That's pretty much always going to be faster than sorting a UDT directly, even if you write a specific sorting function devoted to that particular UDT.

[Milk]

Because sorting involves much swapping internally it sorts a long array of indexes which refer back to the original UDT. Comparisons are a little slower but it only needs to swap a 4 byte element instead of say a 54 byte element. Once the index array is sorted it then moves each of the UDT elements to their new positions, if descending is selected then this is just done back to front. Moving the elements at the end is relatively slow per move but each element only needs to be moved once. It has occurred to me that simply returning the index array could be more efficient and certainly quicker. Another function could be written which takes an index array and a pointer to a UDT array that could reorder the UDT if that is required.

I have other issues to look at first and bearing in mind I started playing with it 12 months ago it might not be finished so soon.

[Ellis Dee]

Yeah, that's a solid approach.

[Floady]

Ellis, just here to say, great work on this thread, real good to see you compare them and the new algorithms

also i can find myself in this statement:
I think you're almost as into watching those little lines draw as I am. I swear, I can just sit and stare at them like a mental patient. I don't need food, or drink, or sleep; must watch lines.

i love demo`s like these: and im gonna make one with all the algorithms in here ;p
http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html

Greetz and keep it up!

[oddperfect]

Public Sub MedianThreeQuickSort1(ByRef pvarArray As Variant, Optional
...
        If plngLeft < lngLast Then MedianThreeQuickSort1 plngArray, plngLeft, lngLast
        If lngFirst < plngRight Then MedianThreeQuickSort1 plngArray, lngFirst, plngRight
    Else
        If lngFirst < plngRight Then MedianThreeQuickSort1 plngArray, lngFirst, plngRight
        If plngLeft < lngLast Then MedianThreeQuickSort1 plngArray, plngLeft, lngLast

A minor bug in this and related quicksort routines:

the recursive calls use "plngArray", which is undefined. It should be pvarArray.

Except for this, thanks for the clean and quick code example.

[Ellis Dee]

Nice catch, thanks much.

[saed]

both QuickSort1 and QuickSort3 have the same speed: 10000 elements are sorted in 31 ms.
SnakeSort is a little bit slower: 10000 elements are sorted in about 80 ms

[Ellis Dee]

That's a small sample size; most algorithms will handle 10k pretty well.

[Merri]

I guess people may have a need for speed? Here is an optimized median three quicksort. Usage is only a little harder than when using Ellis Dee's functions:

QSort Not Not YourArrayVariable

The odd Not Not call is used to get the safe array header's pointer. This allows to avoid the use of Variant datatype so it is a requirement. VB6 does not allow declaring it's own procedures As Any so this is a workaround.


Supports following datatypes: Boolean, Byte, Currency, Date, Double, Integer, Long, Single & String.

Note that it uses countsort for Boolean, Byte & Integer. Also, Dates are sorted as Double (this should make no difference however, Dates are the same as Double, only a bit slower to access).

The module includes Ellis Dee's MedianThreeQuickSort1 for comparison.


Edit!
QSort is safe with negative arrays (Dim MyArray(-6 To 0) is not a problem). It modifies the array to zero base temporarily, which means the rest of the code does not need to account for negative indexes (QSort handles the array as Dim MyArray(0 To 6)).

[Merri]

Just to let you know I've also taken a look at Ellis Dee's SnakeSort. From what I can see I can't just go on and duplicate the behavior, the extra memory usage is too much imo. I think I can use a few tricks to reduce the memory requirements. I already know how to do it with lngIndex() with a very acceptable level of speed decrease.

The greater challenge is to limit the memory use of the mirror array. Whether my ideas work require a deeper look into how it all works. In general if you can reduce overall memory usage you also gain some speed, because all memory handling does slow things down. This is also why I guess SnakeSort seems to be so slow compared to QuickSort in timed benchmarks: the mirror array as it is currently does not do any good for how much stuff happens in memory. Especially strings will multiply the memory use much more than needs to happen thanks to new string allocations.

Note that I haven't yet taken any timed benchmarks of my own! I've mostly focused in getting things to work in the first place. I guess QSort could be optimized further. As QuickSort and SnakeSort seem to be the strongest competitors for the moment, I think they both need attention to get the speed & memory optimized solutions out so that better benchmarking can be done. The name I'll use for my own version of SnakeSort will be SSort. Just to keep it all nice & short

[Ellis Dee]

Snake sort is actually a slightly modified Natural Merge Sort, so I'd just go with that name. It of course has the same memory-hogging pitfall of the standard Merge sort. I believe there are ways to reduce the memory overhead for merge sort, so one assumes that same optimization could be applied to the natural merge sort. I don't actually know what it is, but have seen it mentioned in passing.

I posted an explanation of exactly how it works in this thread over on the Straight Dope. That was before cbrow identified the algorithm as a Natural Merge Sort in this post, which also includes some ideas for making it more efficient.

[Merri]

In that case I'll name SnakeSort1 as NaturalMergeSort1 and use NSort as the short function name for optimized version. I'll also take a look at the efficiency post. I don't need to read the explaining post to understand how it works, I think I understand stuff via code much better. I'm not so good when it comes to talking about which algorithm is better and why, but I can tell when I see inefficiency and I sure can benchmark So here I'm trying to pick the ones that make sense to optimize for speed. For my own interest, for general good and for finding out how Natural Merge Sort can truly perform versus Quick Sort when both have been tweaked closer to the optimal performance.

Can you fix your posts here to use Natural Merge Sort instead of Snake Sort? (Of course it is a good idea to leave a note in the main function post that the name has been changed and why it has been done so.)

[masheen]

Hi guys i just need a quick help with bubble sort i got from this thread. can anyone help me simply this piece of code further? Is function will sort either asc or desc. Is there any other way to simply the code below? especially on the part marked in red.

Function Sort(ByRef str() As String, ByVal flag As Boolean)
 Dim iLower As Integer, iUpper As Integer, iCount As Integer, Temp As String
 Dim str2 As String
 
       iUpper = UBound(str)
       iLower = 1
 
       Dim bSorted As Boolean
       bSorted = False
       Do While Not bSorted
            bSorted = True
            For iCount = iLower To iUpper - 1
               [COLOR="Red"] If flag Then
                    str2 = StrComp(str(iCount + 1), str(iCount), vbTextCompare)
                Else
                    str2 = StrComp(str(iCount), str(iCount + 1), vbTextCompare)
                End If
                     If str2 = 1 Then
                           Temp = str(iCount + 1)
                           str(iCount + 1) = str(iCount)
                           str(iCount) = Temp
                           bSorted = False
                     End If[/COLOR]
            Next iCount
         iUpper = iUpper - 1
       Loop
End Function