Results 1 to 25 of 25

Thread: VB - Quick Sort algorithm (very fast sorting algorithm)

  1. #1

    Thread Starter
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,802

    VB - Quick Sort algorithm (very fast sorting algorithm)

    The example is sorting string arrays, but you can modify it to use any type of arrays, just replace "As String" to the type you need...
    VB Code:
    1. Option Explicit
    2.  
    3. Private Sub Form_Load()
    4.     Dim MyStrArray() As String, K As Long, Q As Long
    5.     ReDim MyStrArray(1 To 10)
    6.    
    7.     Randomize
    8.    
    9.     Debug.Print "Unsorted strings:"
    10.     For K = LBound(MyStrArray) To UBound(MyStrArray)
    11.        
    12.         ' create a random string
    13.         MyStrArray(K) = String(10, " ")
    14.         For Q = 1 To 10
    15.             Mid$(MyStrArray(K), Q, 1) = Chr(Asc("A") + Fix(26 * Rnd))
    16.         Next Q
    17.        
    18.         ' print the string to the immediate window
    19.         Debug.Print MyStrArray(K)
    20.     Next K
    21.    
    22.     ' sort the array
    23.     QuickSort MyStrArray, LBound(MyStrArray), UBound(MyStrArray)
    24.    
    25.     ' print the sorted string to the immediate window
    26.     Debug.Print vbNewLine & "Sorted strings:"
    27.     For K = LBound(MyStrArray) To UBound(MyStrArray)
    28.         Debug.Print MyStrArray(K)
    29.     Next K
    30. End Sub
    31.  
    32. Private Sub QuickSort(C() As String, ByVal First As Long, ByVal Last As Long)
    33.     '
    34.     '  Made by Michael Ciurescu (CVMichael from vbforums.com)
    35.     '  Original thread: [url]http://www.vbforums.com/showthread.php?t=231925[/url]
    36.     '
    37.     Dim Low As Long, High As Long
    38.     Dim MidValue As String
    39.    
    40.     Low = First
    41.     High = Last
    42.     MidValue = C((First + Last) \ 2)
    43.    
    44.     Do
    45.         While C(Low) < MidValue
    46.             Low = Low + 1
    47.         Wend
    48.        
    49.         While C(High) > MidValue
    50.             High = High - 1
    51.         Wend
    52.        
    53.         If Low <= High Then
    54.             Swap C(Low), C(High)
    55.             Low = Low + 1
    56.             High = High - 1
    57.         End If
    58.     Loop While Low <= High
    59.    
    60.     If First < High Then QuickSort C, First, High
    61.     If Low < Last Then QuickSort C, Low, Last
    62. End Sub
    63.  
    64. Private Sub Swap(ByRef A As String, ByRef B As String)
    65.     Dim T As String
    66.    
    67.     T = A
    68.     A = B
    69.     B = T
    70. End Sub
    Last edited by CVMichael; Nov 30th, 2005 at 11:28 AM.

  2. #2
    Lively Member
    Join Date
    Sep 2002
    Posts
    103
    Good stuff

  3. #3
    New Member
    Join Date
    May 2005
    Posts
    6

    Question Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Yes, it's very usefull.

    But i've a small (?) problem with it...

    My array has 35 elements.

    Every time when i try to search in this one, at element 4, my program ends in an endless loop.

    The debugger says, that Mid is 32, and the High Value 33.
    So it starts always again at 32 (rounding error).

    Is there any way to fix that?

    PS: Sorry 4 my bad english I#m still working on it....

    Regards from Frankfurt/Germany,
    freescale

  4. #4

    Thread Starter
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,802

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    I tested it for 35 elements, and it worked perfectrly. I also tried with 34, and 36 elements (just in case), and it still worked fine...

    Maybe there's something wrong with your computer ?

    What VB version do you have ?

  5. #5
    New Member
    Join Date
    May 2005
    Posts
    6

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    I am currently using Visual Basic 6 without any Service Packs.
    But i've just saw that i've posted in the wrong thread. I ment the Function ArrBinarySearch
    in the thread http://vbforums.com/showthread.php?t=231934

  6. #6
    I'm about to be a PowerPoster! Hack's Avatar
    Join Date
    Aug 2001
    Location
    Searching for mendhak
    Posts
    58,333

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Quote Originally Posted by freescale
    I am currently using Visual Basic 6 without any Service Packs.
    But i've just saw that i've posted in the wrong thread. I ment the Function ArrBinarySearch
    in the thread http://vbforums.com/showthread.php?t=231934
    You really should apply at least SP5 to your VB installation.

  7. #7
    New Member
    Join Date
    May 2005
    Posts
    6

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Yes, at home i had this.
    But here at work it isn't possible, because all the software runs on a software server.
    So i haven't the possibility to install anything.

  8. #8
    New Member
    Join Date
    Dec 2008
    Posts
    1

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Ok so I set up a small program that uses this to sort data files containing address information to sort by zip code.

    I read the lines in and put the zips into the array. At the same time I put the record number in a separate array.

    I send the zip array into the sorting procedure. And anytime I run the swap routine on the zip code array I run the swap on the record number array.

    At then end I have a list of record numbers sorted in the correct order for zip code sort.

    I then open the input file for random access read and get records one at a time in the order of the record number array and then print them to an output file.

    My problem and question is this. When I retrieve the records and print them at the end the process in very slow compared to every other step in the process. Is there anything anyone knows I can do to make this process much faster?

    Thank you,

  9. #9
    Frenzied Member
    Join Date
    Oct 2008
    Posts
    1,181

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Does VB have a built in function that can either sort arrays, or automatically find the minimum or maximum values in arrays?

  10. #10

    Thread Starter
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,802

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Not VB6... that's why we have to make our own functions for that.

    VB.NET does ! that's why we all should switch to .NET and don't look back.

  11. #11
    New Member
    Join Date
    Feb 2006
    Posts
    4

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Just an observation that made the code a fraction quicker for me:

    On line 54 which reads:
    Swap C(Low), C(High)

    This is being called even when Low and High "meet" e.g. they both refer to the same array element.

    I just put an if statement around them e.g.

    if low <> high then
    Swap C(Low), C(High)
    endif

  12. #12
    Frenzied Member yrwyddfa's Avatar
    Join Date
    Aug 2001
    Location
    England
    Posts
    1,253

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    This sort routine has a bug in it.

    (Low + High) \ 2 might overflow, replace with Low + (High - Low) \ 2 won't.
    "As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality." - Albert Einstein

    It's turtles! And it's all the way down

  13. #13
    Frenzied Member
    Join Date
    Jan 2010
    Posts
    1,103

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Quote Originally Posted by yrwyddfa View Post
    this sort routine has a bug in it.

    (low + high) \ 2 might overflow, replace with low + (high - low) \ 2 won't.
    good catch!

  14. #14

    Thread Starter
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,802

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Quote Originally Posted by Jonney View Post
    good catch!
    Correct! it MIGHT overflow! ... let's see WHEN?

    So, a Long data type is 32 bits, but we are using a signed integer, so 31 bits, and that is 2,147,483,648... those are array items...
    Now lets see how much memory you would need to store that many items (so that you get the overflow)

    So, internally, each item is a pointer to another location in the memory (basically an array of pointers) each one pointing to a string structure (a BSTR, I can't find anywhere the actual structure of BSTR), similar to this one, and that structure is 12 bytes (on a x86 processor) (and there is another pointer to the actual string... and lets say on average the string is 10 bytes? so let's do the math...

    2^31 * 4 * 12 * 10 = 1.0307922e+12
    that number is in bytes... so let's convert that into GBytes:
    (2^31 * 4 * 12 * 10) / 1073741824 = 960 GBytes

    So... you will get an overflow error if the total memory your array takes is approximately (with a few assumptions) 960 GBytes that has to be stored in RAM (by the way)... and again... this is if your average string is 10 bytes long... and since all strings are unicode, that means 5 characters each string

    So... in conclusion... let's add another operation to the loop to slow it down, because we might get an overflow sometime in the future when computers will have a few terabytes of RAM... it might not be that much far away...

    But.... good catch though


    [Edit]... if you port this code to VB.net then the Long data type is 64 bits.... so.... do you still think you might get an overflow?
    Last edited by CVMichael; Aug 13th, 2014 at 11:23 AM.

  15. #15
    Frenzied Member
    Join Date
    May 2014
    Location
    Kallithea Attikis, Greece
    Posts
    1,289

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    For strings
    Code:
    Private Sub QuicksortString(List() As String, ByVal min As Integer, ByVal max As Integer)
    Dim med_value As String
    Dim hi As Integer
    Dim lo As Integer
    Dim i As Integer
        If max <= min Then Exit Sub
        i = Int((max - min + 1) * Rnd + min)
        med_value = List(i)
         List(i) = List(min)
        lo = min
        hi = max
        Do
            Do While List(hi) >= med_value
                hi = hi - 1
                If hi <= lo Then Exit Do
            Loop
            If hi <= lo Then
                List(lo) = med_value
                Exit Do
            End If
            List(lo) = List(hi)
           lo = lo + 1
            Do While List(lo) < med_value
                lo = lo + 1
                If lo >= hi Then Exit Do
            Loop
            If lo >= hi Then
                lo = hi
                List(hi) = med_value
                Exit Do
            End If
            
            ' Swap the lo and hi values.
            List(hi) = List(lo)
        Loop
        QuicksortString List(), min, lo - 1
        QuicksortString List(), lo + 1, max
    End Sub

  16. #16

    Thread Starter
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,802

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Quote Originally Posted by georgekar View Post
    For strings...
    OK... so the code I posted in this thread 11 years ago, is also sorting strings.... so what's the point of your post? you have to be more descriptive than that! Or is this the quality of posts we should expect these days?

    Woow... why is there a "Rnd" in there? is this what my code evolved into? since when randomising the search gives faster result? (assuming that's why you post the code?)

  17. #17
    Frenzied Member
    Join Date
    May 2014
    Location
    Kallithea Attikis, Greece
    Posts
    1,289

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    You have fun...
    This is not a code to make someone smarter..it just a sorting routine. I am not the inventor of quicksort. It is very fast, but as you can see the random isn't actually the good point (it is a point of interest). The bad news first: This function uses integer offsets and not long. So anyone can change that with long offsets. The good news: This function uses integers so it is faster. The very good news: This is very fast because no waste time provided for swapping the value that it is in semi swap state. As you can see there isn't a swap function or a a call like that one on the code that you provide. Why? Because we get value as a "middle" (or by random...not the middle always, why middle is better....do you know why?) and that value putting in the right position...because at that position we hold the value in an other "middle" value..So not needed for swap function. And that’s why the point of my post is for improving the readers knowledge and not to conflict with your scope of posting
    Hello From Sunny Greece...
    Have a nice day.
    Last edited by georgekar; Aug 14th, 2014 at 05:40 AM.

  18. #18
    Frenzied Member
    Join Date
    May 2014
    Location
    Kallithea Attikis, Greece
    Posts
    1,289

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Don't get it personal CVMichalel but your code is fault. I check it without running, while I explain the code I post...

    Code:
        i = Int((max - min + 1) * Rnd + min)
        med_value = List(i)
         List(i) = List(min)    ' this is the beautiful point of the code.
    When we enter the outer Do Loop we have change the List(i) with List(min) so we have 2 times List(min) item.
    The Rnd function needed to us to pick any value not the value at the middle..There is always a best item to pick, and that item isn't in the middle. So with the rnd function...maybe we found it..In worse scenario we are the same as for the choice of middle...In that scenario all items are in the wrong position.
    The outer loop must find the place of chosen as "middle".
    In the first inner loop we setting the hi pointer to the item less than"middle".
    If we don't find any smaller then this is true hi<=lo and we put in List(lo) the "middle" item. So we found the right position...we perform a swap in three steps, two steps out of outer loop and one in the inner loop.

    Lets see what your routine do at the same situation.
    You pick the middle as actually middle (not a problem here), so we say that this item is the lowest from all other
    You skip the first inner loop, because you get an early false
    You going through all items in the second loop....

    if you don't find any item less that the middle....you get a BIG error because your pointer goes beyond limit...
    So you have to place as in code that i post (i can't remember which part is mine...but I remember that I do some changes), a line with a if clause like that
    If high < low Then Exit Do ' I change <= to < because you have this in the outer loop "Loop While Low <= High"

    So perhaps you correct your code, we have a High<Low condition.
    So the next "if" clause is skipped. Because you "Loop While Low <= High" your loop end without nothing doing
    next ...the First < High is false (high<low and first is low now)
    next ....the Low<Last is true (low is first now and last is the first high)...
    So you call exactly the same QuickSort C, Low, Last .FOREVER
    And for all your life...Your code is not working my friend...for 11 years.
    Have you ever put your code in an application??
    Last edited by georgekar; Aug 15th, 2014 at 02:53 PM.

  19. #19
    Frenzied Member yrwyddfa's Avatar
    Join Date
    Aug 2001
    Location
    England
    Posts
    1,253

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Quote Originally Posted by CVMichael View Post
    Correct! it MIGHT overflow! ... let's see WHEN?

    So, a Long data type is 32 bits, but we are using a signed integer, so 31 bits, and that is 2,147,483,648... those are array items...
    Now lets see how much memory you would need to store that many items (so that you get the overflow)

    So, internally, each item is a pointer to another location in the memory (basically an array of pointers) each one pointing to a string structure (a BSTR, I can't find anywhere the actual structure of BSTR), similar to this one, and that structure is 12 bytes (on a x86 processor) (and there is another pointer to the actual string... and lets say on average the string is 10 bytes? so let's do the math...

    2^31 * 4 * 12 * 10 = 1.0307922e+12
    that number is in bytes... so let's convert that into GBytes:
    (2^31 * 4 * 12 * 10) / 1073741824 = 960 GBytes

    So... you will get an overflow error if the total memory your array takes is approximately (with a few assumptions) 960 GBytes that has to be stored in RAM (by the way)... and again... this is if your average string is 10 bytes long... and since all strings are unicode, that means 5 characters each string

    So... in conclusion... let's add another operation to the loop to slow it down, because we might get an overflow sometime in the future when computers will have a few terabytes of RAM... it might not be that much far away...

    But.... good catch though


    [Edit]... if you port this code to VB.net then the Long data type is 64 bits.... so.... do you still think you might get an overflow?
    Yes, it's always possible.

    This calculation refers to the array index, not the array contents; you only need greater than 2^30 items in the array, regardless of element size which is just over a billion items, which is not insofar as your gigantic amount that unreasonable to expect.

    Nevertheless, even if this limit is way beyond the expected maximum ever likley, having that bug in to save one operation (which is likely optimised out by the compiler) is premature optimisation and is therefore evil.

    Still saving 0.0000000000000000000000000001 extra seconds available might be worthwhile, I suppose - especially if you're sorting on greater than a billion records ....

    "As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality." - Albert Einstein

    It's turtles! And it's all the way down

  20. #20
    Frenzied Member yrwyddfa's Avatar
    Join Date
    Aug 2001
    Location
    England
    Posts
    1,253

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    For reference, anyway. you shouldn't be middling the partitions - although it's a very common thing to do. The principle is quite clear; if the list is almost sorted the partitions will be partitioned into one each side leading to performance of n-squared which is no better than a bubblesort. Using a random number as shown above protects against this, but, even better is to use the median of three technique.

    Sorting nearly sorted lists is incredibly common: for instance, naive programmers will put a new item in a sorted list, and then run quicksort on it to insert it into it's correct place. The code will work, but it's very (very) inefficient.
    "As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality." - Albert Einstein

    It's turtles! And it's all the way down

  21. #21
    Frenzied Member
    Join Date
    May 2014
    Location
    Kallithea Attikis, Greece
    Posts
    1,289

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    The quicksort example in #15 uses the median of three technique.

  22. #22
    Member
    Join Date
    Mar 2018
    Posts
    35

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    CVMichael

    Nice job.

    For the first time in my life, I attended to sorting and got such beautiful satisfaction :)

    Works from box.
    Super fast and efficiently.

    I got the total list of files & folders of %SystemDrive%
    ~15'000 objects with total lentgh of list as ~800'000 bytes,
    preliminary sorted in Far by size.

    Timing below:
    1-st line - without sorting;
    2-nd line - the same code with calling sort.
    Tiks - QueryPerfomanceCounter

    Code:
    ~200'000'000 ticks / ~ 0.075 sec
    ~400'000'000       / ~ 0.150
    I expected much worse results
    (not from the code, but from the sorting of strings itself, especially in such volumes)

    Next I compared both lists - source, aftersorted in Notepad++, and target, sorted by this routine.
    They are identical.

    CVMichael, thanks once more.
    .

  23. #23
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,120

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Quote Originally Posted by georgekar View Post
    The quicksort example in #15 uses the median of three technique.
    For posterity: this is *not* true as of today (see post date).

    cheers,
    </wqw>

  24. #24
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Quote Originally Posted by wqweto View Post
    For posterity: this is *not* true as of today (see post date).

    cheers,
    </wqw>
    Since post #15 hasn't been edited, I don't think it is not true as of today, but hasn't been true since posted.
    But, I guess you mean not true up to today.

    He is picking a value at random in the range, rather than taking the median of three values in the range. That is simpler codewise than dealing with the issue of not having three values left to take the median of.

  25. #25
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,120

    Re: VB - Quick Sort algorithm (very fast sorting algorithm)

    Ooops, sorry for the poor language -- "hasn't been true since posted" is what I meant.

    Quicksort algorithm is nice to know but then everyone is using ADO.Recordset Sort method to do the job :-))

    cheers,
    </wqw>

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