TOPIC 4.15 · STUDY
Sorting Algorithms
selectionSort finds the smallest remaining value and swaps it into the next left slot. insertionSort takes the next unsorted value and shifts the sorted prefix to insert it. Both work on a 1D array or an ArrayList. Exam items often ask for the list after one or two passes, not only the finished order.
4.15.A
Selection sort and insertion sort
Two classic algorithms rearrange comparable values into order. selectionSort repeatedly scans the unsorted part, finds the smallest remaining value, and swaps that value into the next left slot. After each outer-loop pass, one more index on the left is finished and will not be searched again.
insertionSort treats the left side as a growing sorted prefix. It copies the next unsorted value aside, shifts larger prefix values one index to the right to open a hole, then writes the saved value into that hole. The prefix is ordered among itself, but a later smaller value can still push those entries right.
Either method can run on a 1D array with index assignment or on an ArrayList with get and set. The control flow is the same; only how you read and write each slot changes.
public static void selectionSort(int[] data)
{
for (int i = 0; i < data.length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < data.length; j++)
{
if (data[j] < data[minIndex])
{
minIndex = j;
}
}
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
Trace {6, 3, 8, 1}. Pass 1 finds 1 and swaps it with 6, leaving {1, 3, 8, 6}. Pass 2 looks only from index 1 onward, finds 3 already at index 1, and leaves {1, 3, 8, 6}. The finished sorted list is not required to answer a pass question.
| Moment | Array |
|---|---|
| Start | {6, 3, 8, 1} |
| After pass 1 | {1, 3, 8, 6} |
| After pass 2 | {1, 3, 8, 6} |
Pass 1 of selection sort swaps the smallest remaining value (1) into the leftmost slot, producing {1, 3, 8, 6}.
public static void insertionSort(int[] data)
{
for (int i = 1; i < data.length; i++)
{
int next = data[i];
int j = i - 1;
while (j >= 0 && data[j] > next)
{
data[j + 1] = data[j];
j--;
}
data[j + 1] = next;
}
}
Trace {4, 1, 6, 3}. Pass 1 saves 1, shifts 4 right, and writes 1 at index 0, leaving {1, 4, 6, 3}. Pass 2 inserts 6 with no shift because 4 is already smaller, so the array stays {1, 4, 6, 3}. The sorted prefix now has length 3; 3 is still waiting.
| Moment | Array |
|---|---|
| Start | {4, 1, 6, 3} |
| After pass 1 | {1, 4, 6, 3} |
| After pass 2 | {1, 4, 6, 3} |
On an ArrayList the same passes use get to read and set to write. A swap still exchanges two indexes. An insertion still shifts larger prefix values right, then places next in the open slot. Do not confuse these with merge sort, which splits and merges halves in a later topic.
Key points
- selectionSort finds the smallest remaining value and swaps it into the next left slot.
- insertionSort shifts the sorted prefix right to insert the next unsorted value.
- Both algorithms work on a 1D array or an ArrayList.
- A selection pass locks a finished left index; an insertion pass only orders the current prefix.
- Questions often ask for contents after one or two passes, not only the final sorted list.
selection sort swaps the smallest remaining value into place; insertion sort shifts to open a slot.