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 class SortTest
{
    public static void selectionSort(ArrayList<Integer> elements)
    {
        for (int j = 0; j < elements.size() - 1; j++)
        {
            int minIndex = j;
            for (int k = j + 1; k < elements.size(); k++)
            {
                if (elements.get(k) < elements.get(minIndex))
                {
                    minIndex = k;
                }
            }
            int temp = elements.get(j);
            elements.set(j, elements.get(minIndex));
            elements.set(minIndex, temp);
        }
    }

    public static void main(String[] args)
    {
        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());
    }
}

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 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(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());
    }
}

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.

public class SortTest {
    public static void someSortingAlgorithm(ArrayList<Integer> elements) {
        int n = elements.size();
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (elements.get(j) < elements.get(minIndex)) {
                    minIndex = j; 
                }
            }
            int temp = elements.get(minIndex);
            elements.set(minIndex, elements.get(i));
            elements.set(i, 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);

        someSortingAlgorithm(arr1);
        System.out.println("Sorted grades: " + arr1);
        if (!arr1.isEmpty()) {
            System.out.println("Highest grade: " + arr1.get(arr1.size() - 1));
            System.out.println("Lowest grade: " + arr1.get(0));
        }
    }
}
SortTest.main(null);

Sorted grades: [60, 67, 68, 73, 76, 77, 78, 82, 83, 84, 85, 88, 88, 89, 91, 91, 92, 94, 95, 97]
Highest grade: 97
Lowest grade: 60