7.6 Sorting

Learning Objectives

  • Apply selection sort and insertion sort algorithms to sort the elements of array or ArrayList objects.

Essential Knowledge:

  • Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList.

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.

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.

Code Implementation:

import java.util.ArrayList;

public class SelectionSortExample {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>();
        numbers.add(64);
        numbers.add(25);
        numbers.add(12);
        numbers.add(22);
        numbers.add(11);
        
        selectionSort(numbers);
        
        System.out.println("Sorted ArrayList: " + numbers);
    }

    public static void selectionSort(ArrayList<Integer> list) {
        int size = list.size();
        
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < size; j++) {
                if (list.get(j) < list.get(minIndex)) {
                    minIndex = j;
                }
            }

            int temp = list.get(minIndex);
            list.set(minIndex, list.get(i));
            list.set(i, temp);
        }
    }
}

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.

Example:

Code Implementation:

import java.util.ArrayList;

public class InsertionSortExample {
    public static void main(String[] args) {
    
        ArrayList<Integer> numbers = new ArrayList<>();
        numbers.add(64);
        numbers.add(25);
        numbers.add(12);
        numbers.add(22);
        numbers.add(11);
        
   
        insertionSort(numbers);
        

        System.out.println("Sorted ArrayList: " + numbers);
    }

    public static void insertionSort(ArrayList<Integer> list) {
        int size = list.size();
      
        for (int i = 1; i < size; i++) {
            int key = list.get(i);
            int j = i - 1;
            
            while (j >= 0 && list.get(j) > key) {
                list.set(j + 1, list.get(j));
                j--;
            }
            
            list.set(j + 1, key);
        }
    }
}

Extra Sorting Algorithm

Bubble Sort

Process: Repeatedly swap adjacent elements if they are in the wrong order

  • Traverse from left and compare adjacent elements and the higher one is placed at right side.
  • In this way, the largest element is moved to the rightmost end at first.
  • This process is then continued to find the second largest and place it and so on until the data is sorted.

Example:

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSortArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        numbers.add(64);
        numbers.add(34);
        numbers.add(25);
        numbers.add(12);
        numbers.add(22);
        numbers.add(11);
        numbers.add(90);

        System.out.println("Unsorted ArrayList:");
        System.out.println(list);

        bubbleSort(list);

        System.out.println("Sorted ArrayList:");
        System.out.println(list);
    }
}

public static void BubbleSort(ArrayList<Integer> numbers) {
    int n = numbers.size();
    for (int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if (numbers.get(j) > numbers.get(j + 1)) {
                Collections.swap(numbers, j, j+1);
            }
        }
    }
}

Notes:

Some confusing things you may notice is the n-1, n - i - 1, and j + 1

  • “n-1” : After the first iteration of the ArrayList, the largest number will be placed at the end of the list so you dont need to compare all the items in the list(The outer loop runs n-1 times because after n-1 passes, the array is fully sorted)
  • “n - i - 1” : The inner loop shrinks each time because the largest elements “bubble” to the end of the list, and they don’t need to be checked again.
  • “j + 1” : This allows adjacent elements to be compared

Popcorn Hack

Why do we always see “for (int i = 1; i < size; i++)”

It is the classic syntax for a for loop which loops through all elements in an ArrayList

In a bubble sort, why do we add 1 to the j index?

To compare adjacent elements