Sort routines - Quicksort & Bubblesort

[BackupUser]

Restored from previous forum. Originally posted by Andre.

Code: Select all

; Conversion of a BB sourcecode example
; Done by Andre ([url]mailto:andre@purebasic.com[/url])
; 06. April 2003


;- Init section
max=10000
Dim feld(max)
Dim speed(1,10)


;- Functions
Procedure quicksort(s,e)
  i=s
  j=e
  Repeat
    a = i+j
    While feld(i)  feld(a/2)
      j = j-1
    Wend
    If i  j
  If j > s  :  quicksort(s,j)  : EndIf
  If i  feld(j)
        tmp = feld(i)
        feld(i) = feld(j)
        feld(j) = tmp
      EndIf
    Next
  Next
EndProcedure

;- Start output
OpenConsole()
PrintN("Now Quicksort begins...")

;- Quicksort use
For t=1 To 10
  For i=0 To max
    feld(i)=Random(max)
  Next
  
  t1=gettickcount_()         ; Windows API call to millisecs since system start
  quicksort(0,1000*t)
  t2=gettickcount_()
  speed(0,t)=t2-t1
Next

PrintN("Quicksort finished.")
PrintN("Now Bubblesort begins...")


;- Bubblesort use
For t=1 To 10
  For i=0 To max
    feld(i)=Random(max)
  Next
  t1=gettickcount_()         
  bubblesort(0,1000*t)
  t2=gettickcount_()
  speed(1,t)=t2-t1
Next

PrintN("Bubblesort finished.")
PrintN("")
Print("Press Return to show results....")
Input()
ClearConsole()

;- Show results
ConsoleLocate(1,1)
Print("Lines")
ConsoleLocate(15,1)
Print("Quick [ms]")
ConsoleLocate(30,1)
Print ("Bubble [ms]")
For i=1 To 10
  ConsoleColor(7,0)
  ConsoleLocate(1,i+1)
  Print(Str(i*1000))
  ConsoleColor(14,0)
  ConsoleLocate(15,i+1)
  Print(Str(speed(0,i)))
  ConsoleColor(11,0)
  ConsoleLocate(30,i+1)
  Print(Str(speed(1,i)))
Next
PrintN("") : PrintN("")
ConsoleColor(7,0)
Print("Press return to exit...")
Input()
CloseConsole()
End

Regards
André

*** German PureBasic Support ***

[BackupUser]

Restored from previous forum. Originally posted by tinman.

Also:

viewtopic.php?t=5290

--
I used to be a nihilist but I don't believe in that any more.
(Win98first ed. + all updates, PB3.62, external editor)

[geoff]

Andre,

Your quicksort algorithm seems to be wrong.

Have you checked the sorted array?

[Fred]

There already is a quick sort example in the regular PB examples (Advanced) IIRC.

[geoff]

Thanks Fred.

There are several qsort algorithms published and I prefer the one which
uses a pivot variable based on the value of the array element mid way between
the high and low pointers. This is supposed to be faster for sorting arrays
that are already partially sorted.

To Andre and others:
If you post code that you haven't tested please say so.

[Fred]

If you post code that you haven't tested please say so.

Please cool down, Andre has tested it for sure, but an error is always possible...

[geoff]

I'm cool Fred

It's OK to post untested code but useful to know it's untested.
Isn't that just sensible?

I found Andre's qsort helpful, even though the logic is wrong.
Trouble was, I wasted an hour or two checking PureBasic's handling of the
re-entrant procedure only to find that the compiler was working properly.
Then I checked the logic of the qsort and found it was wrong. This routine
cannot have been tested, it doesn't just contain an error, it is based on faulty logic.

Next I did a search of the Forum to find an earlier posting of qsort, maybe
the one from which Andre derived his code. That was wrong as well.

So I posted my reply to save others from wasting their time like I had done.
Isn't that just being friendly?

Then I added the suggestion that we all test our code, at least
cursorily before we post it. Surely a good idea?

Fred, you wouldn't distribute a compiler version before you had tested it properly would you?
Of course not.

[Andre]

Sorry for the late reply. Geoff, I'm sorry when I should have posted any wrong working code.

Like written in the first lines of the code, this was just a conversion from a longer existing Blitz example. I have nothing changed on the used algorythms.

Well, I HAVE tested it several times and the final output of random values ARE in the right order. So I have not seen any error... 8O

If you found an error and you know the correct working code, why not show us your source ? We all try to learn every day....

[geoff]

Andre, this is a program to test your procedure.

It creates 2 identical random arrays a() and feld() then uses PureBasic's
SortArray() to order a() and your quicksort() to order feld().

The pairs of numbers printed in the debug lines should be the same but they aren't.

Code: Select all

;Sort test program
Global max
max=15
Dim a(max)
Dim feld(max)
;
Procedure quicksort(s,e)
 i=s
 j=e
 Repeat
   a = i+j
   While feld(i) < feld(a/2)     ; original code ".... < feld((i+j)/2)" must be splitted because of a "Too complex...." error
     i = i+1
   Wend
   a = i+j
   While feld(j) > feld(a/2)
     j = j-1
   Wend
   If i <= j
     tmp = feld(i)
     feld(i) = feld(j)
     feld(j) = tmp
     i = i+1
     j = j-1
    EndIf
  Until i > j
  If j > s  :  quicksort(s,j) : EndIf
  If i < e  :  quicksort(i,e) : EndIf
EndProcedure
;
;
If OpenWindow(1,200,200,300,200,#PB_Window_SystemMenu,"Test")
  RandomSeed(0)
  For i=0 To max
    a(i)=Random(ValF("2e9"))
    feld(i)=a(i)
  Next i
  SortArray(a(),0,0,max)
;  SortArray(feld(),0,0,max);this sort method works
  quicksort(0,max);this sort method fails
;
  For i=0 To max
    Debug Str(a(i))+"  "+Str(feld(i))
  Next i  
;
  Repeat
    Repeat
      EventID.l = WaitWindowEvent()
    Until EventID <> 0
  Until EventID = #PB_EventCloseWindow 
EndIf
End

Your flavour of quicksort normally works as follows:

Choose an element midway between the start and end pointers. This
element is normally called the pivot element. You then increase the start
pointer until it points at an element greater than the pivot and decrease
the end pointer until it points at an element smaller than the pivot. You
then exchange these two elements. You repeat this sequence until the
start and end pointers overlap. At this point all of the elements below
the pointers are less than the pivot and all the elements above the
pointers are greater than the pivot. You have divided the array into 2
groups. You now re-enter the procedure with each of these groups
dividing these groups into 2. You continue to do this until each group only
contains a single element. the array is now ordered.

In your algorithm the pivot element is not held constant as the two pointers
are increased and decreased. Thus the 2 groups you create may contain
elements that are in the wrong group relative to the final pivot value
because the pivot value was different when these elements were moved.
This is where your logic is wrong.


A corrected version of your procedure is:

Code: Select all

Procedure quicksort(s,e)
 i=s
 j=e
 pivot=feld((i+j)/2)
 Repeat
   a = i+j
   While feld(i) < pivot
     i = i+1
   Wend
   a = i+j
   While feld(j) > pivot
     j = j-1
   Wend
   If i <= j
     tmp = feld(i)
     feld(i) = feld(j)
     feld(j) = tmp
     i = i+1
     j = j-1
    EndIf
  Until i > j
  If j > s  :  quicksort(s,j) : EndIf
  If i < e  :  quicksort(i,e) : EndIf
EndProcedure

In spite of Fred's comment about heat, please be assured I'm not about to
get upset with you over this. I'm sure you had as much belief in the code
you copied as I had in the code I copied from you.

Sadly, the joke "It must be true I got it off the Net" seems to apply
to programmer's Forums as much as the rest of the Internet.