• Selection Sort
  • Insertion Sort
  • Helpful Resources
  • Homework
  • 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

    • Selection Sort GIF

    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:

    • Insertion Sort GIF

    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]