Sort Algorithms

1. Standerd

Running time and memory

2. Types of Data

Any type of data that implements Comparable

public class Data implements Comparable<Data> {
  public int compareTo(Data that) {
    case 1: return + 1;
    case 2: return - 1;
    case 3: return  0;
  }
}

compareTo() must implement a total order

3. Simple sort algorithms

• Selection sort

repeatedly selecting the smallest remaining item

~N^2 / 2 compares
N in place exchange
Insensitive to input
Data movement minimal

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);
     }
  }
}

• Insertion sort