Unit 4.15: Sorting

Iterative Sorting Algorithms

Selection sort and insertion sort are iterative algorithms used to sort collections. They typically use nested loops to organize data in ascending or descending order.

Exclusion Statement: Sorting algorithms other than selection, insertion, and merge sort are outside the scope of the AP Computer Science A course and exam.

Selection Sort

Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it into its correct position.

Search and Swap

Pass 1: Find the minimum in arr[0...n-1] and swap with arr[0].
Pass 2: Find the minimum in arr[1...n-1] and swap with arr[1].
This continues until the entire array is sorted.

Task: Sorting an array in ascending order using Selection Sort.

// In the main method ...
for (int i = 0; i < arr.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    // Swap the found minimum element with the current position
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

Diagram: Selection Sort

Insertion Sort

Insertion sort builds the final sorted array one item at a time by taking each new item and inserting it into its correct position among the already-sorted elements.

Shift and Insert

Take the next unsorted element and compare it to its neighbors on the left.
Shift all larger elements one position to the right to create a "gap."
Insert the element into the correct gap.

Task: Sorting an array in ascending order using Insertion Sort.

// In the main method ...
for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;
    
    // Shift elements that are greater than key to the right
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key; // Insert key into the gap
}

Diagram: Insertion Sort