Code archives/Algorithms/Various Sorting Algorithms
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
Functions for the following sorting algorithms: Shell Sort Bubble Sort Insertion Sort Selection Sort Quick Sort | |||||
;; All sorting functions have been ported from C/C++ code on the website http://linux.wku.edu/~lamonml/ ;; All credit for writing these functions goes to Michael Lamont Graphics 800,600,32,2 F = LoadFont( "Arial", "16" ) SetFont F ;; The array Const ARRAYSIZE = 3000 Dim SortArray( ARRAYSIZE ) ;; Fill it with pseudo-random integers For N = 0 To ARRAYSIZE SortArray( N ) = Rand(256*256) Next ;; Pick a mode Print "1. Shell Sort" Print "2. Quick Sort" Print "3. Bubble Sort (Warning: Can be very slow)" Print "4. Selection Sort" Print "5. Insertion Sort" SortMethod = Input$( "Pick a method: " ) Select SortMethod Case 1 Delay 250 TT = MilliSecs() ShellSort( ARRAYSIZE ) Case 2 PivotMode = Input$( "Use a random pivot position with the quick sort function? (0 or 1) " ) Delay 250 TT = MilliSecs() ;; Get the starting time QuickSort( 0, ARRAYSIZE, PivotMode ) Case 3 Delay 250 TT = MilliSecs() BubbleSort( ARRAYSIZE ) Case 4 Delay 250 TT = MilliSecs() SelectionSort( ARRAYSIZE ) Case 5 Delay 250 TT = MilliSecs() InsertionSort( ARRAYSIZE ) End Select TT = MilliSecs() - TT ;; Get the difference, resulting in the time it took to sort the array For N = 64 To 128 ;; Print 64 of the array's elements Print SortArray( N ) Next Print "Time Taken " + TT ;; And tell you how long it took WaitKey ;; FUNCTIONS Function ShellSort( Size% ) Local i, j, increment, temp increment = 3 While increment > 0 For i = 0 To Size j = i temp = SortArray( i ) While j >= increment And SortArray( j-increment) > temp SortArray(j) = SortArray(j-increment) j = j - increment Wend SortArray(j) = temp Next If increment/2 <> 0 Then increment = increment / 2 ElseIf increment = 1 increment = 0 Else increment = 1 EndIf Wend End Function Function SelectionSort( Size% ) Local i, j, min, temp For i = 0 To Size min = i For j = i+1 To Size If SortArray( j ) < SortArray( min ) Then min = j Next temp = SortArray( i ) SortArray( i ) = SortArray( min ) SortArray( min ) = temp Next End Function Function BubbleSort( Size% ) Local i, j, temp For i = Size To 0 Step -1 For j = 1 To i If SortArray( j - 1 ) > SortArray( j ) Then temp = SortArray( j - 1 ) SortArray( j - 1 ) = SortArray( j ) SortArray( j ) = temp EndIf Next Next End Function Function QuickSort( L, R, RandomPivot = True ) Local A, B, SwapA#, SwapB#, Middle# A = L B = R If RandomPivot Then Middle = SortArray( Rand(L, R) ) Else Middle = SortArray( (L+R)/2 ) EndIf While True While SortArray( A ) < Middle A = A + 1 If A > R Then Exit Wend While Middle < SortArray( B ) B = B - 1 If B < 0 Then Exit Wend If A > B Then Exit SwapA = SortArray( A ) SwapB = SortArray( A ) SortArray( A ) = SortArray( B ) SortArray( A ) = SortArray( B ) SortArray( B ) = SwapA SortArray( B ) = SwapB A = A + 1 B = B - 1 If B < 0 Then Exit Wend If L < B Then QuickSort( L, B ) If A < R Then QuickSort( A, R ) End Function Function InsertionSort( Size% ) Local i, j, index For i = 1 To Size - 1 index = SortArray( i ) j = i While j > 0 And SortArray( j-1 ) > index SortArray( j ) = SortArray( j - 1 ) j = j - 1 Wend SortArray( j ) = index Next End Function |
Comments
| ||
Hehem guess you got it sorted then Noel ;) good speeds :) |
| ||
You could say that ;) |
| ||
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, |
| ||
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). |
| ||
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. |
| ||
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. |
| ||
Just looking through the code I seeFunction 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. |
| ||
Well spotted Floyd, that changes things. Quicksort is now, er, quicker. The actual swap code does not look right either. |
| ||
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. |
| ||
But when you use them to store integers it is just plain wrong. Numbers bigger than 24 bits will be corrupted. 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. |
| ||
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.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. |
| ||
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 |
| ||
Zombiethread! Here is heapsort in Bmax for anyone interested. 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 |
Code Archives Forum