Page 1 of 2 12 LastLast
Results 1 to 10 of 15

Thread: Sorting Algorithms - A Concise Look

  1. #1
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  2. #2
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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):
    • lg
    • lg n
    • n lg n
    • nn
    • n!

    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

  3. #3
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  4. #4
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  5. #5
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  6. #6
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  7. #7
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  8. #8
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  9. #9
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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

  10. #10
    Join Date
    Mar 2003
    Posts
    1,700
    Rep Power
    0

    Default 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
  •