January 15, 2021, 05:33:31 PM

Author Topic: [bb] Various Sorting Algorithms by N [ 1+ years ago ]  (Read 434 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] Various Sorting Algorithms by N [ 1+ years ago ]
« on: June 29, 2017, 12:28:38 AM »
Title : Various Sorting Algorithms
Author : N
Posted : 1+ years ago

Description : Functions for the following sorting algorithms:

Shell Sort
Bubble Sort
Insertion Sort
Selection Sort
Quick Sort


Code :
Code: BlitzBasic
  1. ;; All sorting functions have been ported from C/C++ code on the website http://linux.wku.edu/~lamonml/
  2. ;; All credit for writing these functions goes to Michael Lamont
  3.  
  4. Graphics 800,600,32,2
  5.  
  6. F = LoadFont( "Arial", "16" )
  7. SetFont F
  8.  
  9. ;; The array
  10. Const ARRAYSIZE = 3000
  11. Dim SortArray( ARRAYSIZE )
  12.  
  13.  
  14. ;; Fill it with pseudo-random integers
  15. For N = 0 To ARRAYSIZE
  16.         SortArray( N ) = Rand(256*256)
  17. Next
  18.  
  19. ;; Pick a mode
  20. Print "1.  Shell Sort"
  21. Print "2.  Quick Sort"
  22. Print "3.  Bubble Sort (Warning: Can be very slow)"
  23. Print "4.  Selection Sort"
  24. Print "5.  Insertion Sort"
  25. SortMethod = Input$( "Pick a method: " )
  26.  
  27. Select SortMethod
  28.         Case 1
  29.                 Delay 250
  30.                 TT = MilliSecs()
  31.                 ShellSort( ARRAYSIZE )
  32.         Case 2
  33.                 PivotMode = Input$( "Use a random pivot position with the quick sort function? (0 or 1)    " )
  34.                 Delay 250
  35.                 TT = MilliSecs()        ;; Get the starting time
  36.                 QuickSort( 0, ARRAYSIZE, PivotMode )
  37.         Case 3
  38.                 Delay 250
  39.                 TT = MilliSecs()
  40.                 BubbleSort( ARRAYSIZE )
  41.         Case 4
  42.                 Delay 250
  43.                 TT = MilliSecs()
  44.                 SelectionSort( ARRAYSIZE )
  45.         Case 5
  46.                 Delay 250
  47.                 TT = MilliSecs()
  48.                 InsertionSort( ARRAYSIZE )
  49. End Select
  50. TT = MilliSecs() - TT   ;; Get the difference, resulting in the time it took to sort the array
  51.  
  52. For N = 64 To 128               ;; Print 64 of the array's elements
  53.         Print SortArray( N )
  54. Next
  55.  
  56. Print "Time Taken " + TT        ;; And tell you how long it took
  57.  
  58. WaitKey
  59.  
  60.  
  61.  
  62. ;; FUNCTIONS
  63.  
  64. Function ShellSort( Size% )
  65.         Local i, j, increment, temp
  66.        
  67.         increment = 3
  68.         While increment > 0
  69.                         For i = 0 To Size
  70.                                 j = i
  71.                                 temp = SortArray( i )
  72.                                 While j >= increment And SortArray( j-increment) > temp
  73.                                                 SortArray(j) = SortArray(j-increment)
  74.                                                 j = j - increment
  75.                                 Wend
  76.                                 SortArray(j) = temp
  77.                         Next
  78.                         If increment/2 <> 0 Then
  79.                                 increment = increment / 2
  80.                         ElseIf increment = 1
  81.                                 increment = 0
  82.                         Else
  83.                                 increment = 1
  84.                         EndIf
  85.         Wend
  86. End Function
  87.  
  88. Function SelectionSort( Size% )
  89.         Local i, j, min, temp
  90.        
  91.         For i = 0 To Size
  92.                 min = i
  93.                 For j = i+1 To Size
  94.                         If SortArray( j ) < SortArray( min ) Then min = j
  95.                 Next
  96.                 temp = SortArray( i )
  97.                 SortArray( i ) = SortArray( min )
  98.                 SortArray( min ) = temp
  99.         Next
  100. End Function
  101.  
  102. Function BubbleSort( Size% )
  103.         Local i, j, temp
  104.        
  105.         For i = Size To 0 Step -1
  106.                 For j = 1 To i
  107.                         If SortArray( j - 1 ) > SortArray( j ) Then
  108.                                 temp = SortArray( j - 1 )
  109.                                 SortArray( j - 1 ) = SortArray( j )
  110.                                 SortArray( j ) = temp
  111.                         EndIf
  112.                 Next
  113.         Next
  114. End Function
  115.  
  116. Function QuickSort( L, R, RandomPivot = True )
  117.         Local A, B, SwapA#, SwapB#, Middle#
  118.         A = L
  119.         B = R
  120.        
  121.         If RandomPivot Then
  122.                 Middle = SortArray( Rand(L, R) )
  123.         Else
  124.                 Middle = SortArray( (L+R)/2 )
  125.         EndIf
  126.        
  127.         While True
  128.                
  129.                 While SortArray( A ) < Middle
  130.                         A = A + 1
  131.                         If A > R Then Exit
  132.                 Wend
  133.                
  134.                 While  Middle < SortArray( B )
  135.                         B = B - 1
  136.                         If B < 0 Then Exit
  137.                 Wend
  138.                
  139.                 If A > B Then Exit
  140.                
  141.                 SwapA = SortArray( A )
  142.                 SwapB = SortArray( A )
  143.                 SortArray( A ) = SortArray( B )
  144.                 SortArray( A ) = SortArray( B )
  145.                 SortArray( B ) = SwapA
  146.                 SortArray( B ) = SwapB
  147.                
  148.                 A = A + 1
  149.                 B = B - 1
  150.                
  151.                 If B < 0 Then Exit
  152.                
  153.         Wend
  154.        
  155.         If L < B Then QuickSort( L, B )
  156.         If A < R Then QuickSort( A, R )
  157. End Function
  158.  
  159. Function InsertionSort( Size% )
  160.         Local i, j, index
  161.        
  162.         For i = 1 To Size - 1
  163.                 index = SortArray( i )
  164.                 j = i
  165.                 While j > 0 And SortArray( j-1 ) > index
  166.                         SortArray( j ) = SortArray( j - 1 )
  167.                         j = j - 1
  168.                 Wend
  169.                 SortArray( j ) = index
  170.         Next
  171. End Function


Comments :


aCiD2(Posted 1+ years ago)

 Hehem guess you got it sorted then Noel ;) good speeds :)


N(Posted 1+ years ago)

 You could say that ;)


BulletMagnet(Posted 1+ years ago)

 When I run the sample code with Debug enabled, I see the following errors:Shell Sort = "Array index out of bounds"Insertion Sort = "Array index out of bounds"The other sorts perform fine.Later,


N(Posted 1+ years ago)

 I can't say why those errors occur, since these are pretty much straight ports of C code (refer to the comment at the top of the code for the link to it).


DJWoodgate(Posted 1+ years ago)

 Can't access that link, however I guess C evaluates its conditions slightly differently then and never executes the second comparison, (which may well be the case if it has a logical AND). Or maybe the original code has the same issue.  It will probably not cause any problems most of the time though I guess the chance is always there that you will not have access rights to the out of range memory and you will get a memory violation error.  In any event the debug annoyance alone probably makes a slight rewrite worthwhile... you may even find it speeds things up and that the modified shell implementation with an appropriate increment size can outperform your quicksort routine.


N(Posted 1+ years ago)

 I honestly can't see shell out performing quicksort, but if anyone wants to have a go at it, I'd be glad to add the changes.


Floyd(Posted 1+ years ago)

 Just looking through the code I see
Code: [Select]
Function QuickSort( L, R, RandomPivot = True )
Local A, B, SwapA#, SwapB#, Middle#
SwapA, SwapB and Middle should be the same typea as the array, namely integer.The example code should still work because the array values are no larger than 256*256, i.e. 16-bit.But larger integers can be changed by their temporary storage in floating point variables.


DJWoodgate(Posted 1+ years ago)

 Well spotted Floyd, that changes things. Quicksort is now, er, quicker.  The actual swap code does not look right either.


N(Posted 1+ years ago)

 Floyd: Actually, the use of floats is intended because what I use it for is sorting distances for any number of things (I use this to sort quads based on distance in Ulysses).DJ: The actual swap code is as it was on the website.


Floyd(Posted 1+ years ago)

 But when you use them to store integers it is just plain wrong.Numbers bigger than 24 bits will be corrupted.
Code: [Select]
n% = 1234512345
Print n
Print Bin(n)

Print

x# = n%
n% = x#

Print n
Print Bin(n)

WaitKey : End
This is the same problem as using a float to store Blitz handles for images, sounds, entities etc.It may work by accident, depending on the exact numbers involved. But then you try the same code on a different PC. The numbers change and the program crashes.


Sir Gak(Posted 1+ years ago)

 I get the error on ShellSort, too. If you have the Blitz debugger activated, it shows you that you are accessing a negative index into the array, which of course is a no-no.
Code: [Select]
While j >= increment And SortArray( j-increment) > tempIn the above, j=0 and increment is 3, giving array index of -3, which won't work.


AaronK(Posted 1+ years ago)

 Noel, turn them functions that take some base "NoelSortable" type that have to implement a Compare function or something. Then we can easily plug any sort of type into it and get them being sorted.Aaron


GW(Posted 1+ years ago)

 Zombiethread! Here is heapsort in Bmax for anyone interested.
Code: [Select]
Function HeapSort(a%[], N%)
Local aux%
Local k%

For k = N/2 To 1 Step -1
downheap(a,k,N)
Next

Repeat
aux = a[0]
a[0] = a[N - 1]
a[N - 1] = aux
    N = N - 1
    downheap(a, 1, N)
Until N <= 1

Function downheap(a%[],k%,N%)
Local aux%,j%
aux=a[k-1]
While k<=N/2
j=k*2
If (j<N) And (a[j-1] < a[j]) Then j:+1
If aux >= a[j-1] Then
Exit
Else
a[k-1] = a[j-1]
k=j
EndIf
Wend
a[k-1] = aux
End Function
End Function



 

SimplePortal 2.3.6 © 2008-2014, SimplePortal