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;
// Define the selection sort method
public static void selectionSort(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++) {
// Find the minimum element in remaining unsorted array
if (elements.get(j) < elements.get(minIndex)) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = elements.get(minIndex);
elements.set(minIndex, elements.get(i));
elements.set(i, temp);
}
}
// Create and populate the ArrayList
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);
// Call the selection sort method
selectionSort(arr1);
// Print the sorted grades and the highest and lowest grades
System.out.println("Sorted Grades: " + arr1);
System.out.println("Highest Grade: " + arr1.get(arr1.size() - 1));
System.out.println("Lowest Grade: " + arr1.get(0));
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