Sorting: bubble, selection, and insertion

Putting an array in order

• Sorting rearranges an array so the items go from smallest to largest.
• We sort in place: we move items around inside the same array, with no return value.
• Three classic methods do this: bubble, insertion, and selection sort.

Swapping two elements

• Every sort needs to swap two items. Save one in a temporary, then overwrite.
• int t = a[i]; a[i] = a[j]; a[j] = t; exchanges positions i and j.
• Forgetting the temporary loses one of the values — always keep it.

Bubble sort

• Go through the array and compare each pair of neighbours: a[j] and a[j + 1].
• If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
• Repeat the passes until the whole array is in order.

Insertion sort

• Treat the left part of the array as already sorted, and grow it one item at a time.
• Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
• This is how many people sort playing cards in their hand.

#include <stdio.h>

int main(void) {
    int a[] = {3, 1, 2};
    // one bubble pass: compare neighbours and swap if out of order
    for (int j = 0; j < 2; j++) {
        if (a[j] > a[j + 1]) {
            int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
        }
    }
    printf("%d %d %d\n", a[0], a[1], a[2]);   // 1 2 3
    return 0;
}

Common mistakes

• Bubble, selection and insertion sort are all O(n²).
• Trace a small array by hand to check your sort.

Now you try

• Sort ascending (smallest first), in place, with no return value.
• The checker tries several arrays, including negatives and an already-sorted one.
• Do not write a main — the checker provides one.