VB6: Sorting algorithms (sort array, sorting arrays) - Page 3-VBForums
Page 3 of 3 FirstFirst 123
Results 81 to 96 of 96

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

  1. #81

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

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

    Quote Originally Posted by Milk
    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
    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.

  2. #82
    Cumbrian Milk's Avatar
    Join Date
    Jan 2007
    Location
    0xDEADBEEF
    Posts
    2,428

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

    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.

  3. #83

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

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

    Yeah, that's a solid approach.

  4. #84
    New Member
    Join Date
    May 2008
    Posts
    1

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

    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!

  5. #85
    New Member
    Join Date
    Sep 2008
    Posts
    1

    Re: Sorting algorithms (sort array, sorting arrays)

    Code:
    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.

  6. #86

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

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

    Nice catch, thanks much.

  7. #87
    New Member
    Join Date
    Jul 2010
    Posts
    1

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

    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

  8. #88

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

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

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

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

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

    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)).
    Attached Files Attached Files
    Last edited by Merri; Aug 15th, 2010 at 07:04 AM.

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

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

    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

  11. #91

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

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

    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.
    Last edited by Ellis Dee; Aug 16th, 2010 at 04:48 AM.

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

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

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

  13. #93
    New Member
    Join Date
    May 2011
    Location
    Zamboanga
    Posts
    1

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

    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.

    vb Code:
    1. Function Sort(ByRef str() As String, ByVal flag As Boolean)
    2.  Dim iLower As Integer, iUpper As Integer, iCount As Integer, Temp As String
    3.  Dim str2 As String
    4.  
    5.        iUpper = UBound(str)
    6.        iLower = 1
    7.  
    8.        Dim bSorted As Boolean
    9.        bSorted = False
    10.        Do While Not bSorted
    11.             bSorted = True
    12.             For iCount = iLower To iUpper - 1
    13.                [COLOR="Red"] If flag Then
    14.                     str2 = StrComp(str(iCount + 1), str(iCount), vbTextCompare)
    15.                 Else
    16.                     str2 = StrComp(str(iCount), str(iCount + 1), vbTextCompare)
    17.                 End If
    18.                      If str2 = 1 Then
    19.                            Temp = str(iCount + 1)
    20.                            str(iCount + 1) = str(iCount)
    21.                            str(iCount) = Temp
    22.                            bSorted = False
    23.                      End If[/COLOR]
    24.             Next iCount
    25.          iUpper = iUpper - 1
    26.        Loop
    27. End Function

  14. #94
    New Member
    Join Date
    Feb 2014
    Location
    Sarasota, FL, USA
    Posts
    2

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

    A Few More Sorts:

    This is a String Sort I invented once. I call it PH91 (Pigeon Hole 91)
    Fairly quick - comparable to Quick Sort in speed, but uses up a lot of stack space because it is recurrsive.
    Could be unstable the same as Quicksort, if it runs out of stack space.

    It uses a method I haven't seen before. At least I don't know that I reinvented the wheel.
    Imagine several desks, each with 91 pigeon holes. Each pigeon hole is labeled [ Space ] & punctuation, then 0-9, then A-Z caps, then a-z Lower case.

    You recieve an unsorted list in an Array.

    Take the items 1 at a time and place them in the pigeon holes based on their first character. Some holes will hold 0 items and some will hold multiple Items.
    When that is finished return to the first hole. proceed through the holes in order till you find the first hole that is filled. If it contains only 1 Item, then that item is finished sorting. place it in the final "sorted" stack to be returned by the rutine. If it contains more than 1 item, take the entire hole's contents to the desk #2 (Recurrsion).

    Going through the same steps as just outlined, pigeonhole these Items also, but placed in their holes according to the second character of the item. Again check the pigeonholes. All holes that contain single items are finished sorting. All holes that contain more that 1 Item, take to desk #3 (Recurrsion).

    New desks are created with each recurrsion till all items in the present desk are pigeonholed with only 1 item each hole. At this point there is no need to make a new desk and the present items now sorted may be returned to the former desk. Proceed through the remaining pigeonholes in this desk creating new desks as needed and returning the sorted results, until all pigeon holes in this desk have been processed. Return these sorted results to the formeer desk, and process the remaining pigeon holes. Return these sorted result to the former desk also. ect...

    Finally you will arrive at the inital desk with all items sorted.
    Since the Array list is passed to the rutine ByRef, the original list is now sorted. The rutine now ends & the calling rutine can now use the sorted array.

    The rutine as it stands can crash if a word list contains a character asc value below 31 or above 122, but these chararcters are not normal text input, and if care is used not to accept these characters as input, then it's integrity is safe.

    Without a doubt some wizard will find a way to speed this up even more, but it's aleady very fast.
    Here it is.
    Code:
     
    Public Sub PH91(ByRef L$(), ByVal S&)
    'Recursive
    'Initial call with S = 1
    Dim A$(), T$(), K&, P&, I&, J&, C&, B&(91), D&
    Const Q& = 31
    
    K& = UBound(B&):P& = UBound(L$):ReDim A$(K&, 0)
    For I& = 0 To P&
        If S& <= Len(L$(I&)) Then
            J& = AscW(Mid$(L$(I&), S&, 1)) - Q&:D& = B&(J&)
            If D& > UBound(A$, 2) Then ReDim Preserve A$(K&, D&)
            A$(J&, D&) = L$(I&):B&(J&) = D& + 1
        Else
            L$(C&) = L$(I&): C& = C& + 1
        End If
    Next I&
    
    K& = UBound(A$, 1)
    For I& = 1 To K&
        If B&(I&) Then
            If B&(I&) > 1 Then
                P& = B&(I&) - 1: ReDim T$(P&)
                For J& = 0 To P&
                    T$(J&) = A$(I&, J&)
                Next J&
                S& = S& + 1:Call PH91(T$, S&):P& = UBound(T$)
                For J& = 0 To P&
                    L$(C&) = T$(J&): C& = C& + 1
                Next J&
                S& = S& - 1
            Else
                L$(C&) = A$(I&, 0): C& = C& + 1
            End If
        End If
    Next I&
    
    End Sub


    A Binary Search is very fast. I wondered why nobody thought to write a Binary Sort. Maybe they exist but I don't see them listed in any list of fast sorts.

    I thought to experiment and write one .

    I made it so you recieve the unsorted list as an array. I thought then that the quickest way to sort this list was to create a new one (sorted), then return it.

    I used the Binary search method to find each word's new place in the sorted list, but I couldn't figure out another way to create the new list except by insertion.

    Aaah! Thats' why it has never turned up in a list of fast sorts. It does great on small lists. The search to find it's new place in the list is very fast even with lists of 1 million entrys. BUT! To insert that item in the new list is a big drag if you must use insertion. It's much faster though than a bubble sort. ( Not saying much there )

    I later saw some selection sort rutines, and they are similar in method though not quite the same. I suppose though this should be listed as another selection sort variation.

    Well here it is. It is non-recursive.

    Code:
    Private Sub BinSort(ByRef LST$())
    Dim L$(), I&, J&, LT&, P&, A$, Q&, LP&, HP&
    
    LT& = UBound(LST$)
    ReDim L$(LT& + 1)
    For I& = 0 To LT&
        A$ = LST(I&):LP& = 0:HP& = I&:P& = 0
        Do
            Q& = P&
            If A$ > L$(P&) Then
                LP& = P&
            ElseIf A$ < L$(P&) Then
                HP& = P&
            End If
            P& = Int((LP& + HP&) / 2)
        Loop While P& <> Q&
        If A$ > L$(P&) And L$(P&) <> "" Then P& = P& + 1
        If I& > P& Then
    	'  ********* The Loop below here is the time killer ***********
            For J& = I& To P& Step -1
               L$(J& + 1) = L$(J&)
            Next J&
            DoEvents
        End If
        L$(P&) = A$
    Next I&
    Redim Preserve L$(LT&)
       LST$() = L$()
    
       End Sub

    This Insertion drag on the rutine is something that irritates me to no end.

    I thought why can't we chunk it up, then combine the chunks after each chunk is sorted?

    So I set about to write that too.

    This rutine is designed to write a long list with sorted chunks within it. It creates pointers to the beginning of each chunk, so that it can properly assemble them later into a final sorted list.

    If the initial list is under the established chunk size then the rutine sorts without chunking, but if over that threshold, it will chunk it up and feed it back into the rutine in smaller list sizes.

    I did a lot of experimenting with the chunk size along with various list sizes, then established the best chunk size as a constant.

    The Chunking rutine increased the speed of the sort 9 times faster on large lists ( 5000 - 100000 )

    I used the Binary Sort rutine listed above, but Chunking should increase the speed of any sort that uses the insertion method. It will not increase the speed of Quicksort, or Shellsort since they do not use the insertion method. The insertion method is slow because of chunk size and this should allieviate that bottleneck somewhat.

    It became longer than I wanted, and I suppose some Genius may be able to improve it as well.
    It is recursive, but it is not capable of compounded recersion, so it can be used on systems where stack space is limited.
    Here it is with the above Binary Sort included.
    Code:
      
    Private Sub ChunkSort(ByRef LST$())
    Dim I&, J&, LS&, P&, A$, Q&, LP&, HP&
    Dim L$(), SL$(), B&()
    Const R& = 512  '******** The Chunk size is stored in a constant **********
    
    LS& = UBound(LST$)::ReDim L$(LS& + 1)
    
    '******** Below here is Chunking Rutine **********
    If LS& > R& Then
        HP& = LS& \ R&:ReDim B&(HP&):ReDim SL$(R& - 1)
        Q& = R&
        For I& = 0 To LS& Step Q&
            If I& + Q& > LS& Then
                Q& = LS& - I& + 1: ReDim SL$(Q& - 1)
            End If
            For J& = 0 To Q& - 1
                SL$(J&) = LST$(I& + J&)
            Next J&
            ChunkSort SL$()
            For J& = 0 To Q& - 1
                L$(I& + J& + 1) = SL$(J&)
            Next J&
            B&(I& \ R&) = 0
        Next I&
        For I& = 1 To LS& + 1
            A$ = ""
            For J& = 0 To HP&
              If B&(J&) < R& Then
                P& = J& * R& + B&(J&) + 1
                If P& <= LS& + 1 Then
                  If Trim(L(P&)) <> "" Then
                    If L$(P&) < A$ Or A$ = "" Then
                        A$ = L$(P&): LP& = J&
                    End If
                  End If
                End If
              End If
            Next J&
            B&(LP&) = B&(LP&) + 1:LST$(I& - 1) = A$
    	DoEvents
        Next I&
        Exit Sub
    End If
    
    '********Below is the Binary Sort Rutine **********
    For I& = 0 To LS&
        A$ = LST(I&): LP& = 0:HP& = I&:: P& = 0
        Do
            Q& = P&
            If A$ > L$(P&) Then
                LP& = P&
            ElseIf A$ < L$(P&) Then
                HP& = P&
            End If
            P& = Int((LP& + HP&) / 2)
        Loop While P& <> Q&
        If A$ > L$(P&) And L$(P&) <> "" Then P& = P& + 1
        If I& > P& Then
            For J& = I& To P& Step -1
               L$(J& + 1) = L$(J&)
            Next J&
            DoEvents
        End If
        L$(P&) = A$
    Next I&
    ReDim Preserve L$(LS&)
    LST$() = L$()
    
    End Sub

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

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

    Quote Originally Posted by Perry Miller View Post
    The rutine as it stands can crash if a word list contains a character asc value below 31 or above 122, but these chararcters are not normal text input, and if care is used not to accept these characters as input, then it's integrity is safe.
    I don't visit here much at all anymore, but I have to drop in to say that statement above is far too ignorant. You'll run out of normal text input immediately when you start dealing with stuff like surnames. Take Mόller or Selδnne. In the internationalized world of today it is not safe to assume 91 characters to be enough for anything.

    And in any case whatever code you write you better write it so that unexpected input doesn't crash it. There will always be unexpected input. Some people do unexpected input by purpose. They are called NSA.

  16. #96
    New Member
    Join Date
    Feb 2014
    Location
    Sarasota, FL, USA
    Posts
    2

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

    Merri;
    Thanks for your input.
    Of course it is not suitable for every application in it's present version, but see how easily it can be changed to allow for other input that would not normally be expected.
    In the revision below to accept characters 0 - 255, I simply changed 1 array variable, and the constant.

    B&(255), & Const Q& = 0

    This is all it takes to allow more varied input, and there should be no crash on non-standard input.
    There are some situations where the input is more controlable however, and where that is possible, and
    due care is taken, one could use a version which can be Optimized for your particular application.

    Code:
    Public Sub PH91(ByRef L$(), ByVal S&)
    'Recursive
    'Initial call with S = 1
    Dim A$(), T$(), K&, P&, I&, J&, C&, B&(255), D&
    Const Q& = 0
    
    K& = UBound(B&):P& = UBound(L$):ReDim A$(K&, 0)
    For I& = 0 To P&
        If S& <= Len(L$(I&)) Then
            J& = AscW(Mid$(L$(I&), S&, 1)) - Q&:D& = B&(J&)
            If D& > UBound(A$, 2) Then ReDim Preserve A$(K&, D&)
            A$(J&, D&) = L$(I&):B&(J&) = D& + 1
        Else
            L$(C&) = L$(I&): C& = C& + 1
        End If
    Next I&
    
    K& = UBound(A$, 1)
    For I& = 1 To K&
        If B&(I&) Then
            If B&(I&) > 1 Then
                P& = B&(I&) - 1: ReDim T$(P&)
                For J& = 0 To P&
                    T$(J&) = A$(I&, J&)
                Next J&
                S& = S& + 1:Call PH91(T$, S&):P& = UBound(T$)
                For J& = 0 To P&
                    L$(C&) = T$(J&): C& = C& + 1
                Next J&
                S& = S& - 1
            Else
                L$(C&) = A$(I&, 0): C& = C& + 1
            End If
        End If
    Next I&
    
    End Sub
    I don't visit here much at all anymore, but I have to drop in to say that statement above is far too ignorant.
    I can't plead Ignorance, I did think of it, but chose not to make it initially in the above variation, so I will admit that I am unaccomodating at times. Please accept my apology.

Page 3 of 3 FirstFirst 123

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
  •  



Featured


Click Here to Expand Forum to Full Width

Survey posted by VBForums.