CS 240: Algorithms and Data Structures
James Madison University, Fall 2024

Insertion Sort

public void insertionSort(T[] items) {

  for (int i = 1; i < items.length; i++) { // Insert i'th record
  
    for (int j = i; (j > 0) && (items[j].compareTo(items[j - 1]) < 0); j--) {
      swap(items, j, j - 1);
    }
    
  }
}







Selection Sort

public void selectionSort(T[] items) {

  for (int i = 0; i < items.length - 1; i++) {  // Select i'th biggest record
  
    int bigindex = 0;                                // Current biggest index
    
    for (int j = 1; j < items.length - i; j++) {     // Find the max value
    
      if (items[j].compareTo(items[bigindex]) > 0) { // Found something bigger
        bigindex = j; // Remember bigger index
      }
      
    }
    
    swap(items, bigindex, items.length - i - 1);     // Put it into place
  }
}