Chapter 6 - Sorting

Bubble Sort

for i in range(n-1, 1, -1):
    for j in range(i):
        if data[j] > data[j+1]:
            data[j], data[j+1] = data[j+1], data[j]

Insertion Sort

for i in range(1, len(data)):
    key = data[i]
    j = i-1
    while j >= 0 and data[j] > key:
        data[j+1] = data[j]
        j -= 1
    data[j+1] = key

Merge Sort

Quick Sort

Heap Sort

Bin Sort

procedure Bin_sort(m, S):
    input: 
        S is a list of n records r where r.key is an integer
    output:
        The elements of S sorted by their r.key fields

    create Bins[0..m-1] of m first-in-first-out (FIFO) queues

    while S is not empty do:
        r ← DeleteFrom(S)       // Remove a record r from S
        insert r at the back of queue Bins[r.key]  // Add r to the appropriate bucket
    endwhile

    for index ← 0 to m-1 do:
        while Bins[index] is not Nil do:
            r ← Dequeue(Bins[index])  // Remove the front element from the queue
            Append r to the list S    // Add it back to S
        endwhile
    endfor

end Bin_sort

In short, it creates m buckets to allow each element from S to be placed into those buckets, and then since the bucket is already sorted from 1 to m, we can say the whole thing is sorted too

Radix Sort

procedure Radix_Sort(A):
    input: Array A of size n with integers
    output: Sorted array A

    find the maximum value in A to determine the number of digits (d)
    for each digit position i (starting from least significant to most significant):
        create buckets (0 to base-1)
        for each element x in A:
            place x into the appropriate bucket based on its digit at position i
        concatenate all buckets back into A
    endfor
end Radix_Sort