Page 2 of 3 FirstFirst 123 LastLast
Results 41 to 80 of 100

Thread: VB6: Sorting algorithms (sort array, sorting arrays)

  1. #41

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Never mind about debugging smooth sort; Doogle figured it out.

    I could still use some help with Shear sort if anyone wants to hook me up.

  2. #42
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Hello Dee Ellis,
    You do great work, I have been searching for a working implementation of smooth sort for a long time because I do not understand Dijkstra's pseudo code. I hope to understand the sort now soon.

    I think you are too hard on QuickSort. I plan to do some maths and leap to the defence of QuickSort in the near future.

    In any case, I have done some VB coding of "In Place" (ie only needing O(logN) extra space), "Stable" sorting. One is "In-Place Merge Sort", which I borrowed someone elses algorithm. The other is "Stable Quick Sort", which I worked out myself but am sure that other people have done before me because the algorithm isn't all that novel.

    The both perform well, but not as well as the original quick or merge sorts because maintaining stability without using O(n) extra storage is hard.

    You can find them here: http://www.codeproject.com/KB/recipe...QuickSort.aspx
    Craig
    Last edited by cbrow; May 18th, 2008 at 07:19 PM.

  3. #43

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Thanks for the link; that looks like a nice resource.
    Quote Originally Posted by cbrow
    I have been searching for a working implementation of smooth sort for a long time because I do not understand Dijkstra's pseudo code. I hope to understand the sort now soon.
    Tell me about it. I'm trying to rename all the variables to be more meaningful, and I have to admit it's slow going. It's helpful seeing the graphical representation of exactly what's going on, but even with that I find myself scratching my head a lot.

    I think I'm going to go ahead and post the project as is and revamp the writeups just to get it out there. As I improve the program I'll update the attachments.

  4. #44
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    I am working on understanding Smoothsort. I understand q, b, c, R and r2 variables. I am working on the p variable. I know what it does, I just don't know how! It is some subtle mathematical thing. I will post an explanation of how it works when I get there.

  5. #45

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by cbrow
    I am working on understanding Smoothsort. I understand q, b, c, R and r2 variables. I am working on the p variable. I know what it does, I just don't know how! It is some subtle mathematical thing. I will post an explanation of how it works when I get there.
    Please do; any insight into what the variables are would be most appreciated.

  6. #46
    VB For Fun Edgemeal's Avatar
    Join Date
    Sep 2006
    Location
    WindowFromPoint
    Posts
    4,255

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Is it possible to make Quick Sort (post #13) so it sorts in descending order?
    Last edited by Edgemeal; May 21st, 2008 at 11:23 PM.

  7. #47
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Edgemeal
    Is it possible to make Quick Sort (post #13) so it sorts in descending order?
    Code:
    Public Sub QuickRevSort(ByRef vArray As Variant, _
                            Optional ByVal Lower As Long = 0, _
                            Optional ByVal Upper As Long = -1)
        Dim iFirst As Long, iLast As Long
        Dim vMiddle As Variant, vTemp As Variant
        
        If Lower = 0 And Upper = -1 Then
            Lower = LBound(vArray)
            Upper = UBound(vArray)
        End If
        If Lower >= Upper Then Exit Sub
        iFirst = Lower
        iLast = Upper
        vMiddle = vArray((Lower + Upper) \ 2)
        Do
            Do While vArray(iFirst) > vMiddle And iFirst < Upper
                iFirst = iFirst + 1
            Loop
            Do While vMiddle > vArray(iLast) And iLast > Lower
                iLast = iLast - 1
            Loop
            If iFirst <= iLast Then
                vTemp = vArray(iFirst)
                vArray(iFirst) = vArray(iLast)
                vArray(iLast) = vTemp
                iFirst = iFirst + 1
                iLast = iLast - 1
            End If
        Loop Until iFirst > iLast
        If Lower < iLast Then QuickRevSort vArray, Lower, iLast
        If iFirst < Upper Then QuickRevSort vArray, iFirst, Upper
    End Sub
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    • Baby Steps a guided tour
    • IsDigits() and IsNumber() functions • Wichmann-Hill Random() function • >> and << functions for VB • CopyFileByChunk

  8. #48

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Knowing anhn, I'm going to just assume his code works flawlessly without bothering to test it. But there are other considerations when it comes to using one of these algorithms to sort descending.

    First and foremost is that quicksort is unstable. Any unstable algorithm will "shuffle" items with equal keys. Stable algorithms retain the original order of equal keys. Stable algorithms are nice for achieving multi-column sorts by simply re-running the algorithm on the different key. Say, for instance, you wanted to sort by State then by City. You could do the following:

    MergeSort SomeArray, CityColumn
    MergeSort SomeArray, StateColumn

    Your array will now be sorted primarily by state, since that was the last pass. Within each state, the array will be sorted by City. If you tried to do the same thing with Quicksort, it would end up only sorted by state; the cities would end up in an undefined order.

    Because of this, I honestly don't see any point to ever coding a descending sort for an unstable algorithm. Because the only order achieved is a single primary key, you can always simply iterate the array in reverse to display results in descending order.

    Even if I wanted to end up with a descending order for some reason, I would simple use an ArrayReverse() function to do it afterward. Reversing an array is quite simple and extremely fast, at least compared to sorting it. Here's the ArrayReverse() function:
    vb Code:
    1. Private Sub ArrayReverse(ByRef pvarArray As Variant)
    2.     Dim i As Long
    3.     Dim iMin As Long
    4.     Dim iMax As Long
    5.     Dim varSwap As Variant
    6.    
    7.     iMin = LBound(pvarArray)
    8.     iMax = UBound(pvarArray)
    9.     For i = 0 To (iMax - iMin) \ 2
    10.         varSwap = pvarArray(iMin + i)
    11.         pvarArray(iMin + i) = pvarArray(iMax - i)
    12.         pvarArray(iMax - i) = varSwap
    13.     Next
    14. End Sub

  9. #49
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Ellis Dee
    Knowing anhn, I'm going to just assume his code works flawlessly without bothering to test it. But there are other considerations when it comes to using one of these algorithms to sort descending.

    First and foremost is that quicksort is unstable.
    Thanks for your trusting on me but becareful my codes sometimes "causes disasters" same as everyone else's.

    Actually, that is your code (sorry I didn't mention in the post). I did modify it last month from ascending to descending (took less than 2 minutes) to use in one of my project. To quickly answer Edgemeal's question particularly on QuickSort, I just copied and pasted there without comment.

    About "unstable" and "stable" sort algorithms: Not many people know or care about this unless they have to work on more complicated array.
    The word "unstable" may cause misunderstanding and people may think the algorithm is "unreliable".

    There is a disadvantage of QuickSort is it uses recursive calls, this may cause stack memory problem with large array in some particular orders.
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    • Baby Steps a guided tour
    • IsDigits() and IsNumber() functions • Wichmann-Hill Random() function • >> and << functions for VB • CopyFileByChunk

  10. #50
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Stable and unstable are confusing, coming back and forth having long periods in between I always forget what it is about in this context. So I'd suggest to use more descriptive words, or anything else than "stable". Most of the time it either tells me either "the code doesn't crash, it is very mature" or "place where you can find horses"

    Multidimension safe?

  11. #51

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by anhn
    There is a disadvantage of QuickSort is it uses recursive calls, this may cause stack memory problem with large array in some particular orders.
    Yep, randem ran into that very issue back in post 36. Quicksort3 is much more reliable in avoiding stack overruns.

    As for the stable vs unstable, the main point I was making is that I don't see any need to use a descending order for an unstable algorithm. For example, Let's say you want to populate a listbox descending instead of ascending using the standard ascending sort function:
    vb Code:
    1. QuickSort MyArray
    2. ListBox1.Clear
    3. For i = LBound(MyArray) To UBound(MyArray)
    4.     If blnDescending Then
    5.         ListBox1.AddItem 0
    6.     Else
    7.         ListBox1.AddItem
    8.     End If
    9. Next
    That technique uses a quirk of ListBoxes that allows easy reversing of the order. For other uses, you can simply Step -1 backwards through the array to get descending order.
    Last edited by Ellis Dee; May 22nd, 2008 at 08:07 PM.

  12. #52

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Merri
    Stable and unstable are confusing
    Agreed, but Stability is the actual official term.

  13. #53
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quicksort3

    Stable: No
    In-Place: Yes
    Online: No
    Recursive: No
    Grade: A+
    Ellis, one question: That says "Recursive: No" but actually the code uses recursive calls?
    Code:
    Private Sub MedianThreeQuickSort1(ByRef pvarArray As Variant, Optional ByVal plngLeft As Long, Optional ByVal plngRight As Long)
        ... ...
        If plngLeft < lngLast Then MedianThreeQuickSort1 pvarArray, plngLeft, lngLast
        If lngFirst < plngRight Then MedianThreeQuickSort1 pvarArray, lngFirst, plngRight
    End Sub
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    • Baby Steps a guided tour
    • IsDigits() and IsNumber() functions • Wichmann-Hill Random() function • >> and << functions for VB • CopyFileByChunk

  14. #54

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    My bad. I fixed it.

  15. #55
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Hello All,
    I have finally worked out how SmoothSort works in detail. I have attached a documented version to this post.
    Craig
    Attached Files Attached Files

  16. #56

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Dude, seriously, that's the greatest explanation ever. Mad props to you.

    Did you do this for school, or just personal edification?

  17. #57
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    I did it for personal edification. But mostly because I didn't know what I was getting in to. I am now working on a defence of QuickSort and then a commentary on SnakeSort.

  18. #58

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Cool. And welcome to the boards.

  19. #59
    VB For Fun Edgemeal's Avatar
    Join Date
    Sep 2006
    Location
    WindowFromPoint
    Posts
    4,255

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Ellis Dee
    Even if I wanted to end up with a descending order for some reason, I would simple use an ArrayReverse() function to do it afterward. Reversing an array is quite simple and extremely fast, at least compared to sorting it. Here's the ArrayReverse() function:
    Yes I thought about using the ArrayReverse routine (already had it thanks) but didn't expect it to be so fast, I just started testing some sorting options.

    I was playing around with the grade B and better algorithms with a string array. When the string array has numbers instead of characters none of the algorithms sorted the numbers correctly (logical order) except MedianThreeQuickSort1, but it errors when the string array passed to it is characters.

    I have a sort (posted by MrMac? in the vb6 forum) that can do both alpha and numeric correctly but its so sloooow compared to these QuickSorts!

    btw, Thanks anhn, hope you didn't go through too much trouble.

  20. #60

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Edgemeal
    I was playing around with the grade B and better algorithms with a string array. When the string array has numbers instead of characters none of the algorithms sorted the numbers correctly (logical order) except MedianThreeQuickSort1, but it errors when the string array passed to it is characters.
    Strings are different from numbers. For example, "123" comes before "20" in a string sort. This is as it should be.

    What do you mean that Quicksort3 errors on characters? As a guess, if you are running into case issues, you have to remember to put Option Compare Text at the top of the module where any of the listed sorting algorithms reside.

  21. #61
    VB For Fun Edgemeal's Avatar
    Join Date
    Sep 2006
    Location
    WindowFromPoint
    Posts
    4,255

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Ellis Dee
    What do you mean that Quicksort3 errors on characters? As a guess, if you are running into case issues, you have to remember to put Option Compare Text at the top of the module where any of the listed sorting algorithms reside.
    Just to make it more clear, here is a test I did,

    Module1.bas with a Public Sub MedianThreeQuickSort1 in it. (a.k.a. Quicksort3 POST #14).
    Code:
    Option Compare Text
    Public mList(0 To 2) As String
    Form Code, sort error,
    Code:
        mList(0) = "C"
        mList(1) = "B"
        mList(2) = "A"
        MedianThreeQuickSort1 mList ' Error Type Mismatch see *  below
        Debug.Print mList(0) ' Returns C 
    
    ' * If I change lngMid to a Variant it doesn't error.

    Form Code, no errors,
    Code:
        mList(0) = "120"
        mList(1) = "12"
        mList(2) = "119"
        MedianThreeQuickSort1 mList ' no errors returned
        Debug.Print mList(0) ' Returns 12
    Last edited by Edgemeal; May 26th, 2008 at 03:11 PM.

  22. #62

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Edgemeal
    ' * If I change lngMid to a Variant it doesn't error.
    That is indeed the fix. I have edited the code posted to reflect this fix, as well as changed the function prototype to Public.

    Thanks much for the bug report. It's always nice when the bug report includes the fix, so thanks for that as well.

  23. #63
    VB For Fun Edgemeal's Avatar
    Join Date
    Sep 2006
    Location
    WindowFromPoint
    Posts
    4,255

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Ellis Dee
    That is indeed the fix. I have edited the code posted to reflect this fix, as well as changed the function prototype to Public.
    I may just keep a copy of the original Quicksort3 for sorting string arrays that contain only numbers since it sorts logically and seems pretty fast, unless there is a better/faster way to accomplish that task? Thanks.

  24. #64

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Edgemeal
    I may just keep a copy of the original Quicksort3 for sorting string arrays that contain only numbers since it sorts logically and seems pretty fast, unless there is a better/faster way to accomplish that task? Thanks.
    I'm not aware of any finished solution for sorting that way. Basically, every comparison would require checking the Val() value before comparing the strings directly.

    Maybe a mirror array holding the Val()s would be the most efficient approach, where you compare the mirror array values first, and if they're equal then compare the actual array values.

  25. #65
    VB For Fun Edgemeal's Avatar
    Join Date
    Sep 2006
    Location
    WindowFromPoint
    Posts
    4,255

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Ellis Dee
    I'm not aware of any finished solution for sorting that way. Basically, every comparison would require checking the Val() value before comparing the strings directly.
    Ya thats what I figured, I made a few changes to Quick Sort(#13) to do numbers and it seems to be a hair faster then the original Quicksort3. Good enough,Thanks.

  26. #66
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Ellis, I have a very minor suggestion:

    Due to VB6 allows negative index for array such as: Dim myArray(-10, 0) As Long

    This may come up with a call later such as: MedianThreeQuickSort1 myArray, -7, 0
    or QuickSort myArray, -7, 0

    In this case plngLeft and plngRight will be reset to LBound()=-10 and UBound()=0.

    To avoid that, as in post#47, I suggest to give plngLeft a default value of 0 and plngRight a default value of -1.
    Then you can test: If plngLeft > plngRight Then ... instead of: If plngRight = 0 Then ...
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    • Baby Steps a guided tour
    • IsDigits() and IsNumber() functions • Wichmann-Hill Random() function • >> and << functions for VB • CopyFileByChunk

  27. #67
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    QuickSort often gets a bad rap from people because in its worst case, it could take N squared operations to sort N elements. This fear is entirely undeserved because in practice, a good implementation of QuickSort just isn’t going to do it. For example, if 1024 elements are being sorted, the probability of achieving the worst case scenario is:

    P(worst case) = 2/1024 * 2/512 * 2/512 * 2/256 * 2/256 * 2/256 * 2/256 * 2/128…
    = 2/1024 * (2/512)^2 * (2/256)^4 * (2/128)^8 * (2/64)^16 * (2/32)^32 * …
    = (2^-9)^1 * (2^-8)^2 * (2^-7)^4 * (2^-6)^8 * (2^-5)^16 * (2^-4)^32 * (2^-3)^64 * (2^-2)^128 * (2^-1)^256
    = 2^-9 * 2^-16 * 2^-28 * 2^-48 * 2^-80 * 2^-128 * 2^-192 * 2^-256 * 2^-256
    = 2^(-9-16-28-48-80-128-192-256-256)
    = 2^(-1013)

    The probability of this is so low that if every computer on Earth was sorting using quicksort until the universe ends, it is still unlikely to happen. This is staggeringly unlikely.

    But this is only the worst case, there are still a lot of very-bad-cases. The mathematics of this is beyond me but it is not too difficult to simulate the performance of QuickSort. I wrote a simulator and simulated sorting 128, 1024 and 65536 elements, 150,000 times each. This is a graph of the results:



    When sorting 65536 elements, Quicksort performs an average of 1,420,143 comparisons. After doing 150,000 sorts, the best performance was 92% of the average while the worst performance was 120% of the average.

    From the simulated numbers, I estimate that the chances of Quicksort taking more than 10% more than the average to be <0.005, more than 15% than the average to be <0.0003 and more than 20% more than the average to be <0.000007. If you wanted to guess the probability of Quicksort taking twice as long as its average case then you need to think about lots and lots more zeros in the probability. At this point, you are still looking at performance of order NlogN.

    If you refer back to the graph again, it is apparent that the more data that is being sorted, the narrower the range of performance.

    Another related problem for QuickSort is the exploding stack. Once again, unexpected large usage of the stack is unlikely, but if your stack space is limited, you may have a problem. There is a solution.

    The exploding stack problem occurs when the partitions created by QuickSort are uneven and the stack fills up with details about lots of small partitions. The solution is to put the larger partition on the stack first and process the smaller partition first. This way, the stack contains details of large partition and there can not be many of these. In this case, the worst case number of partitions on the stack is logN.

    If the likelihood of a bad case of QuickSort is so extreme, why have many people experienced it? The answer is that there are lots of bad ways to implement QuickSort. The golden rule is that the choice of the pivot value must always, always, always be independent and uncorrelated to the data. The best way to achieve this is to choose a random pivot. Do this always, always, always.

    In addition, if your random number generator is predictable then your selection of the pivot is predictable and someone can engineer the worst case set of data – do not seed your random number generator in a predictable way if you are concerned about security.

    With these thoughts in mind, the “QuickSort” routine in the application uses a poor method of choosing the pivot value. As Dee acknowledges, this will perform poorly when the data has a camel-hump in the middle. This will probably explode the stack with any reasonable amount of camel-hump data.

    The “MedianThreeQuickSort” routine in the application is much much better. It is a good implementation of QuickSort. The random method of choosing the pivot value means that it is extremely unlikely that any given set of data will break it. The likelihood of it being broken is staggeringly small. The fact that this routine uses a median of three means that the pivot value is likely to be closer to the middle of the data, this actually speeds up the sort and makes it less likely to have a bad case.

    The “MedianThreeQuickSort” routine could be improved by replacing the last two lines with:

    Code:
    If lngLast – plngLeft < plngRight – lngFirst Then
        If plngLeft < lngLast Then QuickSort plngArray, plngLeft, lngLast
        If lngFirst < plngRight Then QuickSort plngArray, lngFirst, plngRight
    Else
        If lngFirst < plngRight Then QuickSort plngArray, lngFirst, plngRight
        If plngLeft < lngLast Then QuickSort plngArray, plngLeft, lngLast
    End If
    This will guarantee that the stack depth is never more than logN.

    In summary, go ahead and use QuickSort. It is fast. Just make sure that you choose your pivot randomly.
    Attached Images Attached Images  
    Last edited by cbrow; May 26th, 2008 at 09:13 PM.

  28. #68

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by anhn
    VB6 allows negative index for array
    My head hurts just contemplating handling for this. I need to think about whether it's worth the added complexity, or if it's better in the long run to just ignore this ill-advised "feature".

    Anything I do at the array level has to be implemented 54 times: 18 graphical algorithms, 18 one-dimensional algorithms, and 18 two-dimensional algorithms. So even minor changes tend to seem daunting.

  29. #69

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by cbrow
    The “MedianThreeQuickSort” routine could be improved by replacing the last two lines with:

    Code:
    If lngLast – plngLeft < plngRight – lngFirst Then
        If plngLeft < lngLast Then QuickSort plngArray, plngLeft, lngLast
        If lngFirst < plngRight Then QuickSort plngArray, lngFirst, plngRight
    Else
        If lngFirst < plngRight Then QuickSort plngArray, lngFirst, plngRight
        If plngLeft < lngLast Then QuickSort plngArray, plngLeft, lngLast
    End If
    Good suggestion. I implemented it in the posted code on the first page.

  30. #70
    Head Hunted anhn's Avatar
    Join Date
    Aug 2007
    Location
    Australia
    Posts
    3,669

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by Ellis Dee
    My head hurts just contemplating handling for this. I need to think about whether it's worth the added complexity, or if it's better in the long run to just ignore this ill-advised "feature".
    Oh!Oh! Forget about that if you think that is an "ill-advised", but that is a real thing I had to deal with in the past, so I just suggested. Never mind!
    • Don't forget to use [CODE]your code here[/CODE] when posting code
    • If your question was answered please use Thread Tools to mark your thread [RESOLVED]
    • Don't forget to RATE helpful posts

    • Baby Steps a guided tour
    • IsDigits() and IsNumber() functions • Wichmann-Hill Random() function • >> and << functions for VB • CopyFileByChunk

  31. #71
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Hello Ellis Dee,
    I have looked at Snake Sort and like it. I agree with what you say that it is about as fast as QuickSort on random data and much faster on sorted or partially sorted data. Other people call this sort a "Natural Merge Sort" but your implementation is about as fast as they get on randomly ordered data. It is possible to make it faster for partially sorted data but the added complexity will probably slow it when sorting random data.

    I wouldn’t change it but there are a couple of things that are interesting to think about:

    1. The buffer of ordered section details (lngIndex) only needs to be size logN. There is an elegant way to merge the sections in a binary pattern to achieve the exact same result as you have. It is marginally slower than your approach.

    2. Consider the scenario when you have a lot of data that has been previously processed and is therefore in order. Then you get some new data added to the end that is not sorted. Say you look for your ordered sections and get:
    Section 0: 1,000,000 elements in order
    Section 1: 2 elements in reverse order
    Section 2: 5 elements in order
    Section 3: 7 elements in reverse order.

    The binary approach that SnakeSort uses (and my suggestion above) would merge sections 0 & 1 (cost 1,000,002), then sections 2 and 3 (cost 12) and then the two results for a total cost of (1,000,002 + 12 + 1,000,014) = 2,000,028 operations.

    A smarter approach would be to merge sections 1 and 2 (cost 7), then merge this with secion 3 (cost 14) and then merge this with section 0 (cost 1,000,014). The total cost of this is (7 + 14 + 1,000,014) = 1,000,035 operations.

    It is most efficient to merge the smaller sections together first.

    The problem is that these two ideas make the algorithm more complicated and therefore slower on random data. Unless you can think of anything.

  32. #72

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by cbrow
    I have looked at Snake Sort and like it. I agree with what you say that it is about as fast as QuickSort on random data and much faster on sorted or partially sorted data. Other people call this sort a "Natural Merge Sort"
    Boooo. I thought I'd come up with an original idea, but googling does turn up references to and descriptions of natural mergesort, and it is indeed snake sort. Oh well.

    Oddly, the only references I see to it are in messageboard discussions. There is no mention of this variation in the wikipedia entry for merge sort. (Wikipedia was my primary reference in this whole endeavor.) I also posted the snake sort algorithm along with a description on a heavily trafficked general interest board, claiming it as my own and asking if anyone had heard of anything similar. Nobody had; in fact, several people thought it was smooth sort. (ha!)

    But after a day of mourning I'll go through and remove the self-credits in the Natural Mergesort algorithm, along with giving it its proper name. Again: Boooo!

    As far as your points of consideration, particularly for an already-ordered list with new random elements. That situation calls for either an online algorithm like insertion sort or the unbelievably efficient smooth sort. That is what impresses me the most about smooth sort: it is an offline algorithm that handles "online data" as efficiently as any online algorithm. That's beyond impressive; it's pure genius.

    I've also always been on the fence about what the term "nearly sorted" really means. If you use the utility attached to the OP and select "5% Shuffled", that techincally qualifies as "nearly sorted" because every element starts out near its final sorted position. And yet, this yields one of snake sort's worst performances, while smooth sort flies through it like greased lightning.

    To really put it in perspective, select snake sort, smooth sort and insertion sort by clicking them, hit the Filter button and then the 5% Shuffled button. Watch smooth sort kick all kinds of ass. The higher your screen resolution the more obvious the difference will be. Even though this is Insertion sort's best case, smooth sort still wins.

  33. #73

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by cbrow
    2. Consider the scenario when you have a lot of data that has been previously processed and is therefore in order. Then you get some new data added to the end that is not sorted. Say you look for your ordered sections and get:
    Section 0: 1,000,000 elements in order
    Section 1: 2 elements in reverse order
    Section 2: 5 elements in order
    Section 3: 7 elements in reverse order.
    In the previous post I claimed that insertion sort or smooth sort would be the better choice for such a scenario, but I appear to be mistaken. To see it in action, change the following code from the OrderArray function in basGraphical.bas:
    Code:
            Case oeWeave
                ShellSort1 plngArray
                For i = iMax To iMax - 5 Step -1
                    plngArray(i) = Int((iMax - iMin + 1) * Rnd) + iMin
                Next
    '            WeaveArray plngArray, iMin, iMax
    To get the full effect you really need to filter so that each algorithm fills the entire vertical space of the screen. Note that Weave order is called Thatched in the tooltip balloons on the toolbar.

    Crazy as this seems, after a quick glance it would appear that even changing it to be one single out-of-place element at the end of the array -- the very definition of what an online algorithm is supposed to excel at -- the order of fastest to slowest seems to go snake sort, smooth sort, insertion sort.

  34. #74
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Hello Ellis Dee,
    I have looked at Shear Sort and have read up on it. Don't expect this sort to work very fast because it is meant to run on N parallel processors. In any case I have found the problem:

    There are three for loops that look like:
    For j = 0 To Cols \ 2 - 1
    or For j = 0 To Rows \ 2 - 1

    When rows or columns are odd, these numbers need to round up like:
    For j = 0 To CLng(Cols / 2) - 1
    and For j = 0 To CLng(Rows / 2) - 1

    or For j = 0 To (Cols + 1) \ 2 - 1
    or For j = 0 To (Rows + 1) \ 2 - 1

    The other thing is that this sort is especially bad if the number N is prime or if N has a large prime root.

    Craig

  35. #75

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by cbrow
    I have looked at Shear Sort [...] I have found the problem
    Sweet, that looks like a winner.

    I can't thank you enough for all your help.

  36. #76
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Sorry, Something bizarre is happening:
    The CLng in: For j = 0 To CLng(Cols / 2) - 1
    is rounding down.

    This form works though: For j = 0 To (Cols + 1) \ 2 - 1

  37. #77

    Thread Starter
    PowerPoster Ellis Dee's Avatar
    Join Date
    Mar 2007
    Location
    New England
    Posts
    3,530

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Quote Originally Posted by cbrow
    Sorry, Something bizarre is happening:
    The CLng in: For j = 0 To CLng(Cols / 2) - 1
    is rounding down.

    This form works though: For j = 0 To (Cols + 1) \ 2 - 1
    That's the one I used anyway, since \ is significantly faster than /.

    I just learned in another thread that Mod is slow, which is unfortunate for smooth sort. I'll be interested to see how it performs when I get the benchmark logic implemented.

  38. #78
    New Member
    Join Date
    May 2008
    Posts
    9

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Hello Ellis,
    Just looking at SmoothSort, the mods seem to be Mod 8, Mod 4 and Mod 2.

    N Mod 8 is the same as N And 7
    N Mod 4 is the same as N And 3
    N Mod 2 is the same as N And 1

    Also if VB had bit-wise shift operators these are much faster than \ 2, \ 4 and \ 8.

    The And operator is much faster.
    Craig

  39. #79
    Cumbrian Milk's Avatar
    Join Date
    Jan 2007
    Location
    0xDEADBEEF
    Posts
    2,448

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    At risk of drifting a little off topic, here's what I have found about Mod vs And in VB6.

    Just to be clear And can be used in place of Mod when the divider is a power of 2.

    In the IDE And is much quicker than Mod but when compiled with optimizations on it can appear to run at exactly the same speed. Further tinkering reveals that And is still much quicker but the compiler is clever enough to convert N Mod Power2 into N And (Power2-1) if the divider is hard coded. This can be further shown by comparing N Mod Power2 with N Mod NotPower2 where the power2 version runs at 10x the speed. This only happens when the optimize for speed compile option is selected and where the divider is hard coded.

    It's a real shame VB does not have bit shift operators, they are really useful. However... Again if optimize for speed is selected try comparing N \ Power2 with N \ Not Power2 with a variety of different numbers. N \ Power2 works out 3x faster, so not as fast as a bit shift but something good is going on.

    ______________________________________________
    Edit: Partly in reference to Merri's post below, as safearrays are at the core of this.

    I while ago I started working on a UDT array sorter. It's still not ready (It's a back burner project) but I'm getting re-interested in it again. There's a tricky issue of sorting 8 byte datatypes in UDT's where the element size does not align to multiples of 8 but multiples of 4. All other types are quite easy as they always align thanks to the padding used. I've resolved the 8 byte issue by treating it as two arrays which are sorted separately and then recombined, it still needs a lot of tidying and optimising. At it's core are to be several different versions (one for every data type) of one of the algorithms here, at this stage it's just bubble sort (to keep it simple) but that will change. Not sure which one yet though, it seems like a toss up between Stability and Speed.

    These are the parameters as it stands
    Code:
    Public Function SortArrayX(ByVal ArrayPtr As Long, SortFieldElement As Variant, Optional Descending As Boolean = False) as boolean
    I'm not super happy with this as the return of VarPtrArray has to be passed rather than the array itself, I can't think of any other way to do it. Thankfully it's fairly easy to check that it is a valid array structure and that the passed element does reside in arrays range so it should be safe to use. One of the bonuses of it is that it could in theory sort any one dimensional array (not sub type variant or object) UDT or not, and it should be quicker than a general algorithm that uses a variant to carry the array. Progress is slow for me as this is on the edge of my ability, but I take it this would be something of interest, yes?

    Quote Originally Posted by Merri
    <snip>[*]Create a new identical header that changes to zero base (if I recall correctly you simply change one value!)
    Yes, the array structure stores the lowerbound and the number of elements, the upperbound is calculated.
    Last edited by Milk; May 30th, 2008 at 06:22 AM.

  40. #80
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: VB6: Sorting algorithms (sort array, sorting arrays)

    Ellis Dee: if you do some learning on SafeArrays, you could make your code only work on zero base simply by replacing the array's header with a zero based one during processing of the array. This would also speed up the processing of all sorting no matter what base the array is in. The problem is of course that you'd need to learn how to handle all the cases properly with the technique and how to do it in the first place, but once you get it you only need to account for one base in sorting code (the zero base), the safe array tricking should perfectly take care of all the negative and positive bases.

    In short the code would work something like this:
    • Read existing array header
    • Create a new identical header that changes to zero base (if I recall correctly you simply change one value!)
    • Replace the array's header
    • Sorting code runs here, no need to check LBound because it is always zero and UBound returns the correct value!
    • Restore the old header & clean up


    Of course a bit of the stuff depends on how the sorting code is done in the first place, I didn't take a look into that.

Page 2 of 3 FirstFirst 123 LastLast

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width