Log of Vic
Toggle Dark/Light/Auto modeToggle Dark/Light/Auto modeToggle Dark/Light/Auto modeBack to homepage

Selection Sort

  • In iteration i, find index min of smallest reamining entry.
  • Swap a[i] and a[min]

quick-find-example

Template for sort classes

public class Example
{
  public static void sort(Comparable[] a) {
    /* sort algorithms need to implement */
  }
  private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
  }
  private int compareTo(Comparable v, Comparable w) {
    if(v > w) {
      return 1;
    }
    if(v < w) {
      return -1;
    }
    return 0;
  }
  private static void exch(Comparable[] a, int i, int j) {
    Comparable swap = a[i];
    a[i] = j;
    a[j] = swap;
  }
  public static boolean isSorted(Comparable[] a) {
    // Test whether the array entries are in order.
    for (int i = 1; i < a.length; i++) {
      if (less(a[i], a[i-1])) {
        return false;
      }
    }
    return true;
  }
}

Selection sort: Java implementation

public class Selection
{
  public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
      int min = i;
      for(int j = i + 1; j < N; j++) {
        if (less(a[j], a[min])) {
          min = j;
        }
      }
      exch(a, i, min);
    }
  }
}

Mathematical analysis

O(N^2)

Reference

[1] Algorithms in Java, Lecture slide