-
Sorting Algorithms - A Concise Look
Sorting algorithms are some of the most useful structures for applications of all types in information technology. After studying these algorithms in great detail, in addition to their relative orders of asymptotic complexity, I thought it would be an extremely useful addition to this site - especially programming students doing the degree programs at any of the major universities in the island.
The next few posts will attempt to illustrate how the most common sorting algorithms can be implemented using Visual Basic. Please note that the syntax will most readily work in Visual Basic .NET. This is especially true with respect to using the ReDim commmand. If you are going to be using Visual Basic 6, please remove the Preserve command after each ReDim instance.
If you are going to be copy / pasting this code, ensure that you change the variable names (lecturers do read the code) and make reference to this website. You are sure to get extra credit for doing so. Furthermore, I would strongly recommend that you abstain from using arrays as I have done here. That was done only for illustration of concept. Use a DataGrid object bound to either an Active Data Object (Visual Basic 6) or a DataSet generated from an OleDbDataAdapter object (Visual Basic .NET) to visually illustrate how these algorithms work.
I have chosen Visual Basic as the language to display these algorithms as unlike most other programming languages, Visual Basic is the easiest to read, and is by far, the one closest to Standard English. Additionally, programmers in other languages can easily adapt Visual Basic code to other more cryptic languages like C/C++ and Java, and basically any other, using their relative idiosyncratic syntatic construct.
The sorts illustrated here are as follows:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
- Merge Sort
- Heap Sort
- Shell Sort
- Radix Sort
-
Re:Sorting Algorithms - A Concise Look
Definition of Terms:
Asymptotic Complexity is the amount of work done by an algorithm as measured using mathematical notation. By definition, the larger the Asymptotic complexity of an algorithm, the slower and more inefficient it is. This does not necessarily mean however, that it uses the largest amount of memory.
Rankings of Asymptotic Complexity (Fastest to slowest):
All algorithms rated according to logarithmic complexities are recursive, meaning that they repeatedly call themselves until some base condition is met (usually when the array size is 1 or 2). Usually such algorithms consume vast amounts of memory directly proportional to the size of the array being sorted. Logarithmic arrays tend to recursively split the array size in half, until there are only two elements left.
Algorithms rated according to exponential complexities are nested loops, meaning they have loops within loops (usually to a depth of 2). These algorithms are typically slower than those with logarithmic complexities. Their performance deteriorates as arrays become larger. Logarithmic arrays however, tend to become faster as array size grows larger.
Ok, enough definitions. On to the Algorithms ;D
-
Re:Sorting Algorithms - A Concise Look
Bubble Sort
Synopsis:
The Bubble Sort is perhaps one of the most simplistic of all sorting algorithms and is a subset of a larger family of sorting algorithms known as MaxSorts. The bubble sort essentially moves through each element in the array, comparing each element individually with all the other elements in the array, and switching positions with those that are smaller than the current element. This way, the larger elements in the array "bubble" up to the top, while the smaller ones, sink to the bottom. The Bubble sort is also known as the Sink Sort for the same reason.
Asymptotic Complexity: n2
How it Works:
[hr]
Array of data [6,7,9,3,2,5]
Bubbling pass 1
[ 6,7,9,3,2,5]
[6,7,9,3,2,5]
[6,7,9,3,2,5]
[6,7,3,9,2,5]
[6,7,3,2,9,5 ]
Bubbling pass 2
[ 6,7,3,2,5,9]
[6,7,3,2,5,9]
[6,3,7,2,5,9]
[6,3,2,7,5,9]
Bubbling pass 3
[ 6,3,2,5,7,9]
[3,6,2,5,7,9]
[3,2,6,5,7,9]
Bubbling pass 4
[ 3,2,5,6,7,9]
[2,3,5,6,7,9]
Bubbling pass 5
[ 2,3,5,6,7,9]
Finish [2,3,5,6,7,9]
[hr]
Code:
Public Sub BubbleSort(ByRef lngArray() As Long)
Dim iOuter As Long
Dim iInner As Long
Dim iLBound As Long
Dim iUBound As Long
Dim iTemp As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
'Which bubbling pass
For iOuter = iLBound To iUBound - 1
'Which comparison
For iInner = iLBound To iUBound - iOuter - 1
'Compare this item to the next item
If lngArray(iInner) > lngArray(iInner + 1) Then
'Swap
iTemp = lngArray(iInner)
lngArray(iInner) = lngArray(iInner + 1)
lngArray(iInner + 1) = iTemp
End If
Next iInner
Next iOuter
End Sub
-
Re:Sorting Algorithms - A Concise Look
Selection Sort
Synopsis:
The Selection Sort is the second member of the MaxSorts family. It goes through each array position and loops through the remainder of the array, looking for the value that best fits the current position. When it finds that value, it is swapped with the one at the current position. By the time it has ran out of array positions for comparison, the array is already sorted.
Asymptotic Complexity: n2
How it Works:
[hr]
Array of data [6,7,9,3,2,5]
[6,7,9,3,2,5]
^ Which element goes here?
[6,7,5,3,2,9]
^ Which element goes here?
[ 6,2,5,3,7,9]
^ Which element goes here?
[3,2,5,6,7,9]
^ Which element goes here?
[ 3,2,5,6,7,9]
^ Which element goes here?
Finish [2,3,5,6,7,9]
[hr]
Code:
Public Sub SelectionSort(ByRef lngArray() As Long)
Dim iOuter As Long
Dim iInner As Long
Dim iLBound As Long
Dim iUBound As Long
Dim iTemp As Long
Dim iMax As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
For iOuter = iUBound To iLBound + 1 Step -1
iMax = 0
'Find the largest value in the subarray
For iInner = iLBound To iOuter
If lngArray(iInner) > lngArray(iMax) Then iMax = iInner
Next iInner
'Swap with last slot of the subarray
iTemp = lngArray(iMax)
lngArray(iMax) = lngArray(iOuter)
lngArray(iOuter) = iTemp
Next iOuter
End Sub
-
Re:Sorting Algorithms - A Concise Look
Insertion Sort
Synopsis:
Insertion sort is the third major member of the MaxSorts family. It works in the exact opposite manner of the Selection sort. Instead of finding an array value that matches a position, it finds a position for an array value and swaps the values at those positions. The Sorted half of the array will continue to grow until there are no more unsorted elements in the array. This is an example of an In-Position sorting algorithm. It doesn't make use of additional arrays or memory locations. The Selection sort is a similar type of algorithm.
How it Works:
[hr]
Array of data [6,7,9,3,2,5]
[6][ 7,9,3,2,5]
^ Where does this value go in [6]?
[6,7][ 9,3,2,5]
^ Where does this value go in [6,7]?
[ 6,7,9][3,2,5]
^ Where does this value go in [6,7,9]?
[ 3,6,7,9][2,5]
^ Where does this value go in [3,6,7,9]?
[2,3,6,7,9][5]
^ Where does this value go in [2,3,6,7,9]?
Finish [2,3,5,6,7,9]
[hr]
Code:
Public Sub InsertionSort(ByRef lngArray() As Long)
Dim iOuter As Long
Dim iInner As Long
Dim iLBound As Long
Dim iUBound As Long
Dim iTemp As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
For iOuter = iLBound + 1 To iUBound
'Get the value to be inserted
iTemp = lngArray(iOuter)
'Move along the already sorted values shifting along
For iInner = iOuter - 1 To iLBound Step -1
'No more shifting needed, we found the right spot!
If lngArray(iInner) <= iTemp Then Exit For
lngArray(iInner + 1) = lngArray(iInner)
Next iInner
'Insert value in the slot
lngArray(iInner + 1) = iTemp
Next iOuter
End Sub
-
Re:Sorting Algorithms - A Concise Look
Quick Sort
Synopsis:
This is a somewhat more complicated sorting algorithm, but it is incredibly faster than the others mentioned above. Before delving into the actual intricacies of this algorithm, we must understand the concept of recursive calling. This is where a function continuously calls itself until a base condition is established.
For the Quick Sort, a pivot value is selected (usually the first element in the array). After a pivot is selected, all values less than the pivot are placed to its left, and all values greater than the pivot, to its right. After this has been done, the program calls itself again, for each subset of the array to the left and right of the pivot (i.e., two recursive calls, one for the left, and one for the right). The process then repeats itself until the array size for each recursive called is only two elements.
At this point, the last instance of the recursive call passes up to its parent caller, its sorted array. The process continues all the way up to the first caller which will, by the time all recursive calls are complete, have the entire sorted array. The example below has the pivot values for each array instance underlined.
Asymptotic Complexity: nlgn
How it Works:
[hr]
Array of data [2,8,4,9,3,5,7,1,0,6]
[ 5,8,3,9,4,1,7,0,2,6]
| Recursive step
[ 2,3,0,4,1] [5] [ 7,9,8,6]
| | Recursive step
[1,0][2][4,3] [6][7][8,9]
| | | | Recursive step
[0,1] [3,4] [6] [8,9]
| | | |
[0,1,2,3,4] [6,7,8,9]
| |
[0,1,2,3,4,5,6,7,8,9]
Finish [0,1,2,3,4,5,6,7,8,9]
[hr]
Code:
Public Sub QuickSort(ByRef lngArray() As Long)
Dim iLBound As Long
Dim iUBound As Long
Dim iTemp As Long
Dim iOuter As Long
Dim iMax As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
'Dont want to sort array with only 1 value
If (iUBound - iLBound) Then
'Move the largest value to the rightmost position, otherwise
'we need to check that iLeftCur does not exceed the bounds of the
'array on EVERY pass (time consuming)
For iOuter = iLBound To iUBound
If lngArray(iOuter) > lngArray(iMax) Then iMax = iOuter
Next iOuter
iTemp = lngArray(iMax)
lngArray(iMax) = lngArray(iUBound)
lngArray(iUBound) = iTemp
'Start quicksorting
InnerQuickSort lngArray, iLBound, iUBound
End If
End Sub
Private Sub InnerQuickSort(ByRef lngArray() As Long, ByVal iLeftEnd As Long, ByVal iRightEnd As Long)
Dim iLeftCur As Long
Dim iRightCur As Long
Dim iPivot As Long
Dim iTemp As Long
If iLeftEnd >= iRightEnd Then Exit Sub
iLeftCur = iLeftEnd
iRightCur = iRightEnd + 1
iPivot = lngArray(iLeftEnd)
'Arrange values so that < pivot are on the left and > pivot
'are on the right
Do
'Find >= value on left side
Do
iLeftCur = iLeftCur + 1
Loop While lngArray(iLeftCur) < iPivot
'Find <= value on right side
Do
iRightCur = iRightCur - 1
Loop While lngArray(iRightCur) > iPivot
'No more swapping to do
If iLeftCur >= iRightCur Then Exit Do
'Swap
iTemp = lngArray(iLeftCur)
lngArray(iLeftCur) = lngArray(iRightCur)
lngArray(iRightCur) = iTemp
Loop
'Call quicksort recursively on left and right subarrays
lngArray(iLeftEnd) = lngArray(iRightCur)
lngArray(iRightCur) = iPivot
InnerQuickSort lngArray, iLeftEnd, iRightCur - 1
InnerQuickSort lngArray, iRightCur + 1, iRightEnd
End Sub
-
Re:Sorting Algorithms - A Concise Look
Merge Sort
Synopsis:
This is very similar to the Quick Sort in construct, with the only difference being that it uses no Pivot value. Instead, the array is subdivided as usual, until there are only two elements remaining. They are sorted, and passed back up the recursive tree of calls. What happens in the end however, is that since each recursive instance will have two halves of the subdivided array, the values from each side are compared, one to the other, and placed in the sorted array in ascending order, since each recursive call had already sorted their respective sub-portions of the array.
Asymptotic Complexity: nlgn
How it Works:
[hr]
Array of data [2,8,4,9,3,5,7,1,0,6]
[2,8,4,9,3,5,7,1,0,6]
| | Recursive step
[2,8,4,9,3] [5,7,1,0,6]
| | | | Recursive step
[2,8] [4,9,3] [5,7] [1,0,6]
| | | | | | Recursive step
[2,8] [4][3,9] [5,7] [1][0,6]
| | | | | | Merge step
[2,8] [3,4,9] [5,7] [0,1,6]
| | | | Merge step
[2,3,4,8,9] [0,1,5,6,7]
| | Merge step
[0,1,2,3,4,5,6,7,8,9]
Finish [0,1,2,3,4,5,6,7,8,9]
[hr]
Code:
Public Sub MergeSort(ByRef lngArray() As Long)
Dim arrTemp() As Long
Dim iSegSize As Long
Dim iLBound As Long
Dim iUBound As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
ReDim Preserve arrTemp(iLBound To iUBound)
iSegSize = 1
Do While iSegSize < iUBound - iLBound
'Merge from A to B
InnerMergePass(lngArray, arrTemp, iLBound, iUBound, iSegSize)
iSegSize = iSegSize + iSegSize
'Merge from B to A
InnerMergePass(arrTemp, lngArray, iLBound, iUBound, iSegSize)
iSegSize = iSegSize + iSegSize
Loop
End Sub
Private Sub InnerMergePass(ByRef lngSrc() As Long, ByRef lngDest() As Long, ByVal iLBound As Long, iUBound As Long, ByVal iSegSize As Long)
Dim iSegNext As Long
iSegNext = iLBound
Do While iSegNext <= iUBound - (2 * iSegSize)
'Merge 2 segments from src to dest
InnerMerge(lngSrc, lngDest, iSegNext, iSegNext + iSegSize - 1, iSegNext + iSegSize + iSegSize - 1)
iSegNext = iSegNext + iSegSize + iSegSize
Loop
'Fewer than 2 full segments remain
If iSegNext + iSegSize < iUBound Then
'2 segs remain
InnerMerge(lngSrc, lngDest, iSegNext, iSegNext + iSegSize - 1, iUBound)
Else
'1 seg remains, just copy it
For iSegNext = iSegNext To iUBound
lngDest(iSegNext) = lngSrc(iSegNext)
Next iSegNext
End If
End Sub
Private Sub InnerMerge(ByRef lngSrc() As Long, ByRef lngDest() As Long, ByVal iStartFirst As Long, ByVal iEndFirst As Long, ByVal iEndSecond As Long)
Dim iFirst As Long
Dim iSecond As Long
Dim iResult As Long
Dim iOuter As Long
iFirst = iStartFirst
iSecond = iEndFirst + 1
iResult = iStartFirst
Do While[/color] (iFirst <= iEndFirst) And (iSecond <= iEndSecond)
'Select the smaller value and place in the output
'Since the subarrays are already sorted, only one comparison is needed
If lngSrc(iFirst) <= lngSrc(iSecond) Then
lngDest(iResult) = lngSrc(iFirst)
iFirst = iFirst + 1
Else
lngDest(iResult) = lngSrc(iSecond)
iSecond = iSecond + 1
End If
iResult = iResult + 1
Loop
'Take care of any leftover values
If iFirst > iEndFirst Then
'Got some leftover seconds
For iOuter = iSecond To iEndSecond
lngDest(iResult) = lngSrc(iOuter)
iResult = iResult + 1
Next iOuter
Else
'Got some leftover firsts
For iOuter = iFirst To iEndFirst
lngDest(iResult) = lngSrc(iOuter)
iResult = iResult + 1
Next iOuter
End If
End Sub
-
Re:Sorting Algorithms - A Concise Look
Heap Sort
This is the most unique sort we have seen so far. But before I explain how this works, I will assume that readers don't know what a heap is.
A heap is a binary tree (that you will have to lookup yourself) in which all parent nodes are greater than their child nodes and usually consists of n levels on the left hand side, and n-1 elements on the right (See How it works below).
A Heap sort consists of two phases:
1) - Arranging the elements so that they are a heap. This involves going through the array and ensuring that all child nodes are smaller than parent nodes. This may involve some shifting of array values between child and parent nodes.
2) - Reading off the values from the original array, into a separate array, deleting the value read from the heaped array. After this is done, the previous step outlined in number 1 is repeated.
Asymptotic Complexity: nlgn
How it Works:
[hr]
Array of data [2,8,4,9,3,5,7,1,0,6]
As it stands, the data, when viewed as a tree, looks like this:
2
/ \
8 4
/ \ / \
9 3 5 7
/ \ /
1 0 6
First, we restore the heap properties by shuffling children up and parents down:
9
/ \
8 7
/ \ / \
6 3 5 4
/ \ /
1 0 2
Now we read off the top value and remove it, placing the last value at the top:
2
/ \
8 7
/ \ / \
6 3 5 4
/ \
1 0
Restore the heap properties:
8
/ \
6 7
/ \ / \
2 3 5 4
/ \
1 0
Continue until the heap is empty.
Finish [0,1,2,3,4,5,6,7,8,9] (place the items in the array in reverse order)
[hr]
Code:
Public Sub HeapSort(ByRef lngArray() As Long)
Dim iLBound As Long
Dim iUBound As Long
Dim iArrSize As Long
Dim iRoot As Long
Dim iChild As Long
Dim iElement As Long
Dim iCurrent As Long
Dim arrOut() As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
iArrSize = iUBound - iLBound
ReDim Preserve arrOut(iLBound To iUBound)
'Initialise the heap
'Move up the heap from the bottom
For iRoot = iArrSize \ 2 To 0 Step -1
iElement = lngArray(iRoot + iLBound)
iChild = iRoot + iRoot
'Move down the heap from the current position
Do While iChild < iArrSize
If iChild < iArrSize Then
If lngArray(iChild + iLBound) < lngArray(iChild + iLBound + 1) Then
'Always want largest child
iChild = iChild + 1
End If
End If
'Found a slot, stop looking
If iElement >= lngArray(iChild + iLBound) Then Exit Do
lngArray((iChild \ 2) + iLBound) = lngArray(iChild + iLBound)
iChild = iChild + iChild
Loop
'Move the node
lngArray((iChild \ 2) + iLBound) = iElement
Next iRoot
'Read of values one by one (store in array starting at the end)
For iRoot = iUBound To iLBound Step -1
'Read the value
arrOut(iRoot) = lngArray(iLBound)
'Get the last element
iElement = lngArray(iArrSize + iLBound)
iArrSize = iArrSize - 1
iCurrent = 0
iChild = 1
'Find a place for the last element to go
Do While iChild <= iArrSize
If iChild < iArrSize Then
If lngArray(iChild + iLBound) < lngArray(iChild + iLBound + 1) Then
'Always want the larger child
iChild = iChild + 1
End If
End If
'Found a position
If iElement >= lngArray(iChild + iLBound) Then Exit Do
lngArray(iCurrent + iLBound) = lngArray(iChild + iLBound)
iCurrent = iChild
iChild = iChild + iChild
Loop
'Move the node
lngArray(iCurrent + iLBound) = iElement
Next iRoot
'Copy from temp array to real array
For iRoot = iLBound To iUBound
lngArray(iRoot) = arrOut(iRoot)
Next iRoot
End Sub
-
Re:Sorting Algorithms - A Concise Look
Shell Sort
Synopsis:
The Shell Sort, developed by computer scientist Donald Shell, is one of the most amazingly efficient sorts ever developed. To this day, its efficiency is still boggling mathematicians and computer scientists the world over.
The Shell Sort works by using gap sequences in an array. That is, it takes the first element in the array, skips n number of elements (gap size n) takes another element, skips another n number of elements, takes the next array element, and so on, until it reaches the end of the array. The elements taken out at each gap sequence are sorted recursively, and replaced in the array in the gaps from which they were taken. Then the process repeats itself, recursively, reducing the gap size n by 1 until n = 1.
This is done for each element in the array, up to position n in the array, where n represents the gap size.
Asymptotic Complexity: As of this writing, no accurate order of complexity can be determined, as it varies significantly with the size of the array.
How it Works:
[hr]
Array of data [6,7,9,3,2,5]
Shell with spacing of 4
[6,7,9,3,2,5]
^ Where does this fit in [6]?
Shell with spacing of 3
[2,7,9,3,6,5]
^ Where does this fit in [2]?
Shell with spacing of 2
[2,7,9,3,6,5]
^ Where does this fit in [2]?
[2,7,9,3,6,5]
^ Where does this fit in [2,9]?
Shell with spacing of 1
[2,7,6,3,9,5]
^ Where does this fit in [2]?
[2,7,6,3,9,5]
^ Where does this fit in [2,7]?
[2,6,7,3,9,5]
^ Where does this fit in [2,6,7]?
[2,3,6,7,9,5]
^ Where does this fit in [2,3,6,7]?
[2,3,6,7,9,5]
^ Where does this fit in [2,3,6,7,9]?
Finish [2,3,5,6,7,9]
[hr]
Code:
Public Sub ShellSort(ByRef lngArray() As Long)
Dim iSpacing As Long
Dim iOuter As Long
Dim iInner As Long
Dim iTemp As Long
Dim iLBound As Long
Dim iUBound As Long
Dim iArrSize As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
'Calculate initial sort spacing
iArrSize = (iUBound - iLBound) + 1
iSpacing = 1
If iArrSize > 13 Then
Do While iSpacing < iArrSize
iSpacing = (3 * iSpacing) + 1
Loop
iSpacing = iSpacing \ 9
End If
'Start sorting
Do While iSpacing
For iOuter = iLBound + iSpacing To iUBound
'Get the value to be inserted
iTemp = lngArray(iOuter)
'Move along the already sorted values shifting along
For iInner = iOuter - iSpacing To iLBound Step -iSpacing
'No more shifting needed, we found the right spot!
If lngArray(iInner) <= iTemp Then Exit For
lngArray(iInner + iSpacing) = lngArray(iInner)
Next iInner
'Insert value in the slot
lngArray(iInner + iSpacing) = iTemp
Next iOuter
'Reduce the sort spacing
iSpacing = iSpacing \ 3
Loop
End Sub
-
Dec 5, 2003, 01:23 AM
#10
Re:Sorting Algorithms - A Concise Look
Radix Sort
Synopsis:
The Radix Sort (or Histogram Sort) is a very new sorting algorithm that is being used by today's fastest and most powerful RDBMS systems such as MS SQL 2000, MySQL, Oracle 9i and just about every new Relational Database management system out there. Furthermore, for all you Linux gurus out there, this sorting algorithm is how Linux organises its file indexing structure.
Radix Sort is relatively simple and quite easy to follow. This sort makes use of buckets. Each iteration of the sort, progresses through each number in an array value that has one or more digits, and sorts the values in the array each time, according to the nth digit in the number. Each time it sorts the array's values according to a specific digit in the number, all related values are placed in a bucket. The sort ends when all of the array values have been sorted according to the last digit in the numbers in the array.
Asymptotic Complexity: As of this writing, no accurate order of complexity can be determined, as it varies with the size of the values in the array.
How it Works:
[hr]
Array of data [5,530,64,203,99,331,4,692,362,34]
Radix with right-most digit
Bucket [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ]
530 331 692 203 64 5 99
362 4
34
Array now [530,331,692,362,203,64,4,34,5,99]
Radix with middle digit
Bucket [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ]
203 530 362 692
4 331 64 99
5 34
Array now [203,4,5,530,331,34,362,64,692,99]
Radix with left-most digit
Bucket [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ]
4 203 331 530 692
5 362
34
64
99
Array now [4,5,34,64,99,203,331,362,530,692]
Finish [4,5,34,64,99,203,331,362,530,692]
[hr]
Code:
Public Sub RadixSort(ByRef lngArray() As Long)
Dim arrTemp() As Long
Dim iLBound As Long
Dim iUBound As Long
Dim iMax As Long
Dim iSorts As Long
Dim iLoop As Long
iLBound = LBound(lngArray)
iUBound = UBound(lngArray)
'Create swap array
ReDim Preserve arrTemp(iLBound To iUBound)
iMax = &H80000000
'Find largest
For iLoop = iLBound To iUBound
If lngArray(iLoop) > iMax Then iMax = lngArray(iLoop)
Next iLoop
'Calculate how many sorts are needed
Do While[/color] iMax
iSorts = iSorts + 1
iMax = iMax \ 256
Loop
iMax = 1
'Do the sorts
For iLoop = 1 To iSorts
If iLoop And 1 Then
'Odd sort -> src to dest
InnerRadixSort lngArray, arrTemp, iLBound, iUBound, iMax
Else
'Even sort -> dest to src
InnerRadixSort arrTemp, lngArray, iLBound, iUBound, iMax
End If
'Next sort factor
iMax = iMax * 256
Next iLoop
'If odd number of sorts we need to swap the arrays
If (iSorts And 1) Then
For iLoop = iLBound To iUBound
lngArray(iLoop) = arrTemp(iLoop)
Next iLoop
End If
End Sub
Private Sub InnerRadixSort(ByRef lngSrc() As Long, ByRef lngDest() As Long, ByVal iLBound As Long, ByVal iUBound As Long, ByVal iDivisor As Long)
Dim arrCounts(255) As Long
Dim arrOffsets(255) As Long
Dim iBucket As Long
Dim iLoop As Long
'Count the items for each bucket
For iLoop = iLBound To iUBound
iBucket = (lngSrc(iLoop) \ iDivisor) And 255
arrCounts(iBucket) = arrCounts(iBucket) + 1
Next iLoop
'Generate offsets
For iLoop = 1 To 255
arrOffsets(iLoop) = arrOffsets(iLoop - 1) + arrCounts(iLoop - 1) + iLBound
Next iLoop
'Fill the buckets
For iLoop = iLBound To iUBound
iBucket = (lngSrc(iLoop) \ iDivisor) And 255
lngDest(arrOffsets(iBucket)) = lngSrc(iLoop)
arrOffsets(iBucket) = arrOffsets(iBucket) + 1
Next iLoop
End Sub
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules