7.6 Sorting

Two of the following sorting algorithms will be on the AP exam.(merge sort is discussed in Unit 10)

Selection sort: Look for the smallest element, swap with first element. Look for the second smallest, swap with second element, etc…

Insertion sort: Build an increasingly large sorted front portion of array.
All sorting algorithms have…

comparison-based sorting, which determines order of elements by comparing them to each other. Ways to compare are:

<, >, compareTo

Selection Sort

Process: Orders a list of values by repeatedly putting the smallest or largest unplaced value into its final position.

Look through the list to find the smallest value.

Swap it so that it is at index 0.

Look through the list to find the second-smallest value.

Swap it so that it is at index 1.

…

Repeat until all values are in their proper places.

Visualize this diagram as you go through the code

Code Implementation:

import java.util.ArrayList;

public static void selectionSort(ArrayList<Integer> elements)
{
    // outer loop to iterate through every element in the ArrayList
    for (int j = 0; j < elements.size() - 1; j++)
    {
        // set the current value being compared 
        int minIndex = j;
        // INNER LOOP TO ITERATE EVERY ELEMENT AFTER THE minIndex VALUE
        for (int k = j + 1; k < elements.size(); k++)
        {
            // FIND THE SMALLEST ELEMENT IN THE LIST AND SET IT TO THE minINDEX
            if (elements.get(k) < elements.get(minIndex))
            {
                minIndex = k;
            }
        }
        // swap minIndex value with new smaller value
        int temp = elements.get(j);
        elements.set(j, elements.get(minIndex));
        elements.set(minIndex, temp);
    }
}

// test cases
ArrayList<Integer> arr1 = new ArrayList<>();
arr1.add(3);
arr1.add(86);
arr1.add(-20);
arr1.add(14);
arr1.add(40);
System.out.println(arr1.toString());
selectionSort(arr1);
System.out.println(arr1.toString());

[3, 86, -20, 14, 40]
[-20, 3, 14, 40, 86]

Insertion Sort

Process: Shift each element into a sorted sub-array.

To sort a list of n elements.

Loop through indices i from 1 to n – 1:

For each value at position i, insert into correct position in the sorted list from index 0 to i – 1.

Visualize this GIF as you go through the code:

Code Implementation:

import java.util.ArrayList;


public static void insertionSort(ArrayList<Integer> elements)
{
    // outer loop to iterate through every element in the list
    // notice how it starts at 1 because the 0 index is considered "sorted"
    for (int j = 1; j < elements.size(); j++) {
        // store  current element in a temporary variable
        int temp = elements.get(j);
        // initialize the possible index where the current element might be inserted
        int possibleIndex = j;
        
        // shift elements to the right until the correct position for temp is found
        while (possibleIndex > 0 && temp < elements.get(possibleIndex - 1)) 
        {
            // move previous element to the right
            elements.set(possibleIndex, elements.get(possibleIndex - 1));
            
            // decrement index to check values to the left
            possibleIndex--;
        }
        
        // insert current element into correct position
        elements.set(possibleIndex, temp);
    }
}

// test cases
ArrayList<Integer> arr1 = new ArrayList<>();
arr1.add(3);
arr1.add(86);
arr1.add(-20);
arr1.add(14);
arr1.add(40);
System.out.println(arr1.toString());
insertionSort(arr1);
System.out.println(arr1.toString());

[3, 86, -20, 14, 40]
[-20, 3, 14, 40, 86]

Helpful Resources

Watch these if you’re still unsure about selection and insertion sort. These helped me a lot.

Homework

You’re a teacher for a computer science class at Rancho Bernardo. You have a list of all the grades of the students in your class but its hard to see who has the highest and lowest grade. Use either insertion sort or selection sort to sort the ArrayList so the grades are easy to see.

import java.util.ArrayList;

public class SortTest {
    public static void insertionSort(ArrayList<Integer> elements) {
        for (int j = 1; j < elements.size(); j++) {
            int temp = elements.get(j);
            int possibleIndex = j;

            while (possibleIndex > 0 && temp < elements.get(possibleIndex - 1)) {
                elements.set(possibleIndex, elements.get(possibleIndex - 1));
                possibleIndex--;
            }
            elements.set(possibleIndex, temp);
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr1 = new ArrayList<>();
        arr1.add(85);
        arr1.add(92);
        arr1.add(76);
        arr1.add(88);
        arr1.add(67);
        arr1.add(94);
        arr1.add(73);
        arr1.add(89);
        arr1.add(91);
        arr1.add(82);
        arr1.add(78);
        arr1.add(88);
        arr1.add(95);
        arr1.add(60);
        arr1.add(84);
        arr1.add(77);
        arr1.add(91);
        arr1.add(68);
        arr1.add(97);
        arr1.add(83);

        insertionSort(arr1);
        
        System.out.println(arr1);
    }
}
SortTest.main(null);

[60, 67, 68, 73, 76, 77, 78, 82, 83, 84, 85, 88, 88, 89, 91, 91, 92, 94, 95, 97]