January 15, 2021, 05:33:31 PM

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

#### 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

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% = 1234512345Print nPrint Bin(n)Printx# = n%n% = x#Print nPrint 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) > temp`In 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 FunctionEnd Function`