Elementary Sorts

Goal

    - Sort any type of data.

//Comparable interface
public interface Comparable<Item>{
  public int compareTo(item that)
}

//Comparable class implementation
public class X implements Comparable<X>{
  ...
  public int compareTo(X b){
    ...
    return -1; //less

    ...
    return +1; // greater

    ...
    return 0; //equal
  }
}

//Helper functions
//1. less
private static boolean less(Comparable a, Comparable b){
  return a.compareTo(b) < 0;
}

//2. Exchange
private static void exch(Comparable a[], int i, int j){
  Comparable swap = a[i];
  a[i] = a[j];
  a[j] = swap;
}

//3. Test if an array sorted
private static boolean isSorted(Comparable a[]){
  for(int i=1;i<a.length;i++){
    if(less(a[i], a[i-1]))) return false;
  }
  return true;
}

1. Selection Sort
        Steps:
                1. In iteration i, find index min of smallest remaining entry.
                2. Swap a[i] and a[min].            
       Running Time: Quadratic time, even if input array is sorted.
        Data movement is minimal, linear number of exchanges.

public class Selection{
  public static void sort(Comparable a[]){
    int N = a.length;

    for(int i=0;i<a.length;i++){
      int min = i;
      for(int j=i+1;j<a.length;j++){
        if(less(a[j], a[min])) min = j
      }
      
      if(min != i)
        exch(a, i, min);
    }
  }
}

2. Insertion Sort

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

3. ShellSort

public class Shellsort{
 public voic sort(Comparable a[]){
  int h = 1;
  while(h < a.length/3) h = 3*h+1;

  while(h > 0){
   for(int i = h;i<a.length; i++){
    for(int j = i;j >= h && less(a[j], a[j-h]);j-=h){
     exch(a, j, j-h);
    }
   }
   h/=3;
  }
 }
}