[bb] Various Sorting Algorithms by N [ 1+ years ago ]

[BlitzBot]

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 : EndThis 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