Sorting: the Swap, Selection Sort, and Insertion Sort

Where you are: Week 0 review > Sorting

Try This First

To exchange xs[i] and xs[j], a classmate writes xs[i] = xs[j]; xs[j] = xs[i];. Decide what goes wrong before reading on.

Before You Start

Check each box you can do from memory. A box you cannot check yet is not a problem; it points you to a quick refresher, not a grade.

• I can describe what a linear search does at each step of an array.
• I can state what must be true of an array before a binary search will work.
• I can read and write a Java for loop that iterates over array indices.

See also: Searching an Array: Linear and Binary

What You Need To Walk In With

Walk into the next class able to state these:

• Swapping two slots takes three statements with a temporary. A two-statement swap loses one value.
• Selection sort tracks the index of the minimum of the unsorted part, then makes one swap per pass.
• Insertion sort shifts larger elements right and inserts the current value into the gap; it must save the current value before shifting, or that value is overwritten.

You should be able to: write the three-statement swap, and trace selection or insertion sort pass by pass.

How It Works

The three-statement swap

int t = xs[i];
xs[i] = xs[j];
xs[j] = t;

The temporary holds the first value while the assignment overwrites it, so nothing is lost. Every sort that exchanges elements is built on this.

Selection sort

Find the index of the smallest element in the unsorted part, then swap it into place. One swap per pass:

for (int i = 0; i < xs.length - 1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < xs.length; j++) {
        if (xs[j] < xs[minIdx]) { minIdx = j; }
    }
    int t = xs[i]; xs[i] = xs[minIdx]; xs[minIdx] = t;
}

Track the index minIdx, not the value. The index says which slot to swap; the value alone does not, and looking the value back up fails on duplicates.

Insertion sort

Take each element and slide it left past larger neighbors into its place:

for (int i = 1; i < xs.length; i++) {
    int current = xs[i];               // save before shifting
    int j = i - 1;
    while (j >= 0 && xs[j] > current) {
        xs[j + 1] = xs[j];             // shift right
        j = j - 1;
    }
    xs[j + 1] = current;               // drop into the gap
}

Saving current first matters: the first shift writes into position i, which would overwrite the value being inserted.

Worked Example: Predict, Then Check

int[] xs = {3, 1, 2};
// selection sort, pass i=0: smallest of {3,1,2} is at index 1 -> swap xs[0], xs[1]

Predict the array after the first selection-sort pass.

A Common Mistake

Tracking the minimum value instead of its index breaks selection sort. The value does not say which slot to pull from, and a second pass to find the slot fails on duplicates by matching the wrong occurrence. Track minIdx and swap by index. (Source: BJP (Reges and Stepp), Ch 13.)

Go Deeper (optional)

For the curious: both sorts are correct but slow, taking on the order of n squared comparisons for n elements, because each builds the order one element at a time. The library Arrays.sort uses faster methods (on the order of n times the logarithm of n). Writing these two by hand first makes the faster algorithms, and why they are faster, easier to understand later.

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.