Introduction: 7.6.0

  • There are many algorithms to sort an array
    • There are 3 to know for the CS A exam
  1. Selection sort
    1. Select the smallest item in the unsorted section of the array; move it to the front
      1. This value is now “sorted”
    2. Repeat until you are at the second to last value
  2. Insertion sort
    1. Work left to right; from the second item
    2. If an item is larger than the item below it, move it down until arr[i] >= arr[i-1]
  3. Merge sort
    1. Break each array down into individual components
    2. Continually merge components together, sorting along the way
      1. Groups of 1, 2, 4, 8, 16, etc.
    3. Uses recursion

Selection sort

To identify selection sort:

  • look for a nested loop
    • outer loop starts at 0; ends at length - 1
  • inner loop starts at the outer loop + 1
  • if the value of the inner loop index is less than the smallest index, the smallest index swaps
  • swap the value at the outer loop and the smallest value
public static void selectionSort(int[] elements)
{
   for (int j = 0; j < elements.length - 1; j++)
   {
      int minIndex = j;
      for (int k = j + 1; k < elements.length; k++)
      {
         if (elements[k] < elements[minIndex])
         {
            minIndex = k;
         }
      }
      int temp = elements[j];
      elements[j] = elements[minIndex];
      elements[minIndex] = temp;
      }
}

Insertion sort

  • starts at index 1
  • inserts the value at index 1 into the correct place on the sorted part of the list
    • moves the value left as long as there are larger values below it

To identify an insertion sort:

  • look for an outer loop that starts at 1 and loops through the whole array
  • storing the element value and possible index
  • an inner while loop
    • loops while possible index is positive and index value is less than the value below it
  • when the inner loop ends, set the possible index to the value
public static void insertionSort(int[] elements)
{
   for (int j = 1; j < elements.length; j++)
   {
      int temp = elements[j];
      int possibleIndex = j;
      while (possibleIndex > 0 && temp < elements[possibleIndex - 1])
      {
         elements[possibleIndex] = elements[possibleIndex - 1];
         possibleIndex--;
      }
      elements[possibleIndex] = temp;
   }
}

Summary: 7.6.4

  • selection sort and insertion sort are iterative sorting algorithms which sort elements in an array or ArrayList
  • informal run-time comparisons of code and algorithms can be made using the number of statements executed