A Replacement for the Bubble Sort

For reference, here's a listing of the Bubble Sort algorithm in Visual Basic:

' Bubble Sort

    Dim I, J, IntArray(), Temp as Integer ' Declare Variables

    For I = 1 To Length - 1 ' Supposed to be the smaller value
        For J = I To Length ' Supposed to be the larger value
            If IntArray(I) > IntArray(J) Then ' Compare Cells
                Temp = IntArray(I) ' \
                IntArray(I) = IntArray(J) ' | Swap Cells
                IntArray(J) = Temp ' /
            End If
        Next
    Next

There's not much good to say about the Bubble Sort except that it's small and compact size-wise. Performance-wise it's a whole other animal.

So what do you do when you need a sorting algorithm that's comparable to a Quick Sort in terms of performance but still only takes up about as much space as the Bubble Sort? Consider implementing the O-Sort. Here's a listing of the O-Sort in Visual Basic:

' O-Sort   (Oosterwal Sort)  Version 3

    SngPhi = 0.78     ' Define phi value
    SngFib = Length * SngPhi    ' Set initial real step size
    Step = Int(SngFib)     ' Set initial integer step size
    
    While (Step > 0)
        
        For I = 1 To Length - Step   ' Range of lower cell
            If IntArray(I) > IntArray(I + Step) Then ' Compare cells
                Temp = IntArray(I)   ' \
                IntArray(I) = IntArray(I + Step) ' | Swap Cells
                IntArray(I + Step) = Temp  ' /
            End If
        Next
            
        SngFib = SngFib * SngPhi   ' Decrease the Real step size
        Step = Int(SngFib)    ' Set the integer step value
        
    Wend

Here's how it works.

The O-Sort is a type of Comb Sort algorithm. Comb Sort algorithms use a step size or interval between the two values being compared that starts off large, compared to the number of values being sorted, and becomes smaller for each subsequent pass of the data. The idea behind the algorithm is to get chunks of the larger values to the end of the list and chunks of the smaller values to the beginning of the list quickly, then with each subsequent pass of the data look at values that are closer together and moving smaller chunks of data shorter distances until during the last pass neighboring data points are compared.

In practice, with 10,000 elements of completely randomized data the O-Sort takes about 1.6 times longer to sort the data than the Quick Sort. For comparison, the Shell Sort takes 36 times as long and the Bubble Sort takes over 200 times as long.

When you have data that is less randomized, such as what you would get when appending lists of sorted data, the Quick Sort is less quick. When 10% of the data is randomized the O-Sort requires 0.96 as much time to completely sort the data as the Quick Sort. When only 5% of the data is randomized, the O-Sort takes only 0.61 as much time to completely sort the data as the Quick Sort.

When you need a fast in-place sorting algorithm that doesn't require much code space consider using the O-Sort routine.