Algorithms: Sorting & Searching

Note the EXIT DO inside the insertion loop: BASIC's AND does not short-circuit, so DO WHILE j >= LBOUND(a) AND a(j) > v would read a(j) out of bounds when j goes below the lower bound.

27.1 Complexity at a glance

great for small or nearly sorted data simple and fast in practice fastest general-purpose in practice needs extra array sorted data only

27.2 Simple sorts

Note the EXIT DO inside the insertion loop: BASIC's AND does not short-circuit, so DO WHILE j >= LBOUND(a) AND a(j) > v would read a(j) out of bounds when j goes below the lower bound. (QB64's _ANDALSO also solves this.)

SUB BubbleSort (a() AS LONG)
    DIM i AS LONG, swapped AS INTEGER, hi AS LONG
    hi = UBOUND(a)
    DO
        swapped = 0
        FOR i = LBOUND(a) TO hi - 1
            IF a(i) > a(i + 1) THEN SWAP a(i), a(i + 1): swapped = -1
        NEXT
        hi = hi - 1                             ' the largest item is now in place
    LOOP WHILE swapped
END SUB

SUB SelectionSort (a() AS LONG)
    DIM i AS LONG, j AS LONG, m AS LONG
    FOR i = LBOUND(a) TO UBOUND(a) - 1
        m = i
        FOR j = i + 1 TO UBOUND(a)
            IF a(j) < a(m) THEN m = j
        NEXT
        IF m <> i THEN SWAP a(i), a(m)
    NEXT
END SUB

SUB InsertionSort (a() AS LONG)
    DIM i AS LONG, j AS LONG, v AS LONG
    FOR i = LBOUND(a) + 1 TO UBOUND(a)
        v = a(i): j = i - 1
        DO WHILE j >= LBOUND(a)
            IF a(j) <= v THEN EXIT DO
            a(j + 1) = a(j): j = j - 1
        LOOP
        a(j + 1) = v
    NEXT
END SUB

27.3 Quicksort (recursive)

Call it as QuickSort arr(), LBOUND(arr), UBOUND(arr). Note: since parameters are passed by reference, pass expressions or separate variables — QuickSort a(), lo, j is fine because the SUB does not modify lo/hi.

SUB QuickSort (a() AS LONG, lo AS LONG, hi AS LONG)
    DIM i AS LONG, j AS LONG, pivot AS LONG
    IF lo >= hi THEN EXIT SUB
    pivot = a((lo + hi) \ 2)
    i = lo: j = hi
    DO WHILE i <= j
        DO WHILE a(i) < pivot: i = i + 1: LOOP
        DO WHILE a(j) > pivot: j = j - 1: LOOP
        IF i <= j THEN SWAP a(i), a(j): i = i + 1: j = j - 1
    LOOP
    IF lo < j THEN QuickSort a(), lo, j
    IF i < hi THEN QuickSort a(), i, hi
END SUB

27.4 Searching

FUNCTION LinearSearch& (a() AS LONG, target AS LONG)
    DIM i AS LONG
    LinearSearch& = -1
    FOR i = LBOUND(a) TO UBOUND(a)
        IF a(i) = target THEN LinearSearch& = i: EXIT FUNCTION
    NEXT
END FUNCTION

FUNCTION BinarySearch& (a() AS LONG, target AS LONG)   ' array must be sorted
    DIM lo AS LONG, hi AS LONG, mid AS LONG
    lo = LBOUND(a): hi = UBOUND(a)
    BinarySearch& = -1
    DO WHILE lo <= hi
        mid = (lo + hi) \ 2
        IF a(mid) = target THEN
            BinarySearch& = mid: EXIT FUNCTION
        ELSEIF a(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
END FUNCTION

27.5 Sorting records by a field

Sort arrays of TYPEs the same way, comparing a field and swapping whole records (SWAP people(i), people(j)). For large records, sort an array of indexes instead and leave the records in place.

FreeBASIC: the C runtime qsort is available via crt.bi with a comparison callback (Function cmp cdecl (a As Any Ptr, b As Any Ptr) As Long). VB.NET: Array.Sort(arr), list.Sort(), list.Sort(Function(a, b) a.Age.CompareTo(b.Age)), LINQ OrderBy, Array.BinarySearch. Write your own only to learn.