Hi-Speed Sorting

[Theo Gottwald]

```
Just a fraction of a second faster on 10 million items! 🕒 On 100 million, you'll notice a few seconds' difference. 🧐 While it might not be a game-changer, it's certainly intriguing.

We're talking about a Quick sort that switches to an alternative method for smaller partitions. 🔄 For partitions of roughly 25 items or less, it's more efficient to use a different sorting technique. Even Bubble sort has its moments, but Selection sort seems to edge it out slightly. 📊

A neat trick: checking for only two items and swapping if needed can give a small but nifty speed boost. 🚀 The impact might seem trivial, but it's more significant than you'd think.

Without the tweaks, the coded Quick sort would lag behind the PB sort, which boasts assembly-level speed. 🏎�💨

🆕 Update:
Insertion sort has been added as the alternative sorting method, raising the bar to 25 items for switching sorts. 🔄 This change alone shaves off about 6 seconds on 100 million items compared to the PB sort. It may not be crucial, but it's definitely cool. 😎

#coding #programming #QuickSort #optimization #codinglife #tech #developers #efficiency #softwareengineering #codingtips #algorithm #speedtest 🖥�🔧📈👨�💻👩�💻💡🚀

```

Code Select Expand

#Option LargeMem32
#Dim All
#Compile Exe "Sort Test.exe"
'public domain, use at own risk

Macro doalternativesort = 25
Macro testcount = 10000000

Function PBMain()
    Register i As Long
    Local pb() As Long
    Local a() As Long
    Local value As Long
    Local s As WString
    Local d As Double

    Randomize

    Dim pb(1 To testcount)
    Dim a(1 To testcount)
    For i = 1 To testcount
        value = Rnd(-29999999, 29999999)
        'value = Rnd(1, 1000)
        'value = i
        'value = testcount - 1
        'value = 9
        pb(i) = value
        a(i) = value
    Next i

    s += "sort test count = " + Format$(testcount,"#,") + $CrLf

    'PB sort
    d = Timer
    Array Sort pb()
    s += "PB sort time = " + Format$(Timer - d,"000.000") + " seconds" + $CrLf

    'code sort
    d = Timer
    CodeSort(a(), 1, testcount)
    s += "code sort time = " + Format$(Timer - d,"000.000") + " seconds" + $CrLf

    For i = 1 To testcount
        If a(i) <> pb(i) Then
            ? "code sort fail"
            Exit Function
        End If
    Next i

    ? s
End Function

Sub CodeSort(a() As Long, ByVal leftindex As Long, ByVal rightindex As Long)
    Register i As Long
    Register j As Long
    Local items, k As Long
    Local value As Long

    items = rightindex - leftindex + 1
    If items > 1 Then
        If items = 2 Then
            'SORT TWO VALUE
            If a(rightindex) < a(leftindex) Then Swap a(rightindex), a(leftindex)
        ElseIf items <= doalternativesort Then
            'DO ALTERNATIVE SORT
            InsertionSort(a(), leftindex, rightindex)
        Else
            'QUICK SORT
            i = leftIndex : j = rightIndex : k = i + j : Shift Right k, 1: value = a(k)
            While i <= j
                While a(i) < value
                    Incr i
                Wend
                While a(j) > value
                    Decr j
                Wend
                If i <= j Then
                    Swap a(i), a(j) : Incr i : Decr j
                End If
            Wend
            If leftIndex < j Then CodeSort(a(), leftIndex, j)
            If i < rightIndex Then CodeSort(a(), i, rightIndex)
        End If
    End If
End Sub

Sub InsertionSort(a() As Long, ByVal leftindex As Long, ByVal rightindex As Long)
    Register i As Long
    Register j As Long
    Local value As Long

    For i = leftindex + 1 To rightindex
        value = a(i)
        j = i - 1
        While j >= leftindex And a(j) > value
            a(j + 1) = a(j)
            Decr j
        Wend
        a(j + 1) = value
    Next i
End Sub

Sub SelectionSort(a() As Long, ByVal leftindex As Long, ByVal rightindex As Long)
    Register i As Long
    Register j As Long

    For i = leftindex To rightindex - 1
        For j = i + 1 To rightindex
            If a(j) < a(i) Then Swap a(j), a(i)
        Next i
    Next i
End Sub

Sub BubbleSort(a() As Long, ByVal leftindex As Long, ByVal rightindex As Long)
    Register i As Long
    Local swapped As Byte

    swapped = 1
    While swapped
        swapped = 0
        For i = leftindex To rightindex - 1
            If a(i + 1) < a(i) Then
                Swap a(i + 1), a(i)
                swapped = 1
            End If
        Next i
    Wend
End Sub

Stable Sorting vs. Unstable Sorting 🔄

In a stable sorting algorithm, data is sorted in such a way that it preserves the original order of elements with equal keys. 📊 This means that if two elements have the same key, the one that appeared first in the input will also appear first in the sorted output. 🛤� For example, if element A and A[j] have the same key and i < j, then A should come before A[j] in the sorted array. 📝

On the other hand, an unstable sorting algorithm sorts data without maintaining the original sequence of elements with equal keys. 🌪� For instance, if element A and A[j] have the same key and i < j, there's a chance that A[j] might be positioned before A after sorting. 🔄

Want to dive deeper into sorting algorithms? Check out this resource: 🔗 https://www.educative.io/answers/stable-and-unstable-sorting-algorithms


#SortingAlgorithms #StableSorting #UnstableSorting #DataStructures #Algorithms #Coding #Programming #ComputerScience #TechTalk 📊🔍👨�💻👩�💻🖥�💾📈🔄🔗