ElementarySort

//Selection sort: java implementation   O(1/2N^2+N)
/* In iteration i, find index min of smallest remaining entry and swap a[i] and a[min].*/
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);
			}
		}
	}
	private static boolean less (Comparable v, Comparable w) {
		return v.compareTo(w) < 0;
	}
	private static void exch (Comparable [] a, int i , int j) {
		Comparable swap = a[i];
		a[i] = a[j];
		a[j] = swap;
	}
}

// Insertion sort: java implementation   on average O(1/2 N^2)
/*partially-sorted arrays(sorted arrays (N) appended some numbers) insertion sort runs in linear time. Number of exchanges equals the number of inversions. Number of compares equals number of exchanges + (N-1)*/
/* In iteration i, swap a[i] with each larger entry to its left*/
public class Insertion {
	public static void sort (Comparable[] a) {
		int N = a.length;
		for (int i = 0 ; i<N; i ++ ){
			for (int j = i ; j > 0 ; j- - ) {
				if (less (a[j], a[ j-1]))
					exch (a, j, j-1);
				else break;
			}
		}
	}
	private static boolean less (Comparable v, Comparable w) {
		return v.compareTo(w) < 0;
	}
	private static void exch (Comparable [] a, int i , int j) {
		Comparable swap = a[i];
		a[i] = a[j];
		a[j] = swap;
	}
}

// Shellsort: Java implementation
//Number of conpares used by shellsort with the 3X+1 increments is at most by a small multiple of N times the number of increments used.
/*Insertion sort with stride length h*/
public class Shell {
	public static void sort (Comparable [] a) {
		int N = a.length;
		int h = 1;
		while (h< N/3) h= 3*h + 1;
		while (h>=1) {
			for (int i = h; i <N ; i ++ ) {
				for ( int j = i ; j >= h && less (a[j], a[j-h]);j-=h)
					exch (a, j, j-h);
			}
			h=h/3;
		}
	}
	private static boolean less (Comparable v, Comparable w) {
		return v.compareTo(w) < 0;
	}
	private static void exch (Comparable [] a, int i , int j) {
		Comparable swap = a[i];
		a[i] = a[j];
		a[j] = swap;
	}
}

// shuffling 
// in iteration i, pick integer r between 0 and i uniformly at random and swap a[i] and a[r]
public class StdRandom {
.......
	public static void shuffle (Object [] a) {
		int N = a.length;
		for (int i = 0; i<N ; i++) {
			int r = StdRandom.uniform (i+1); // between o and i
			exch (a, i ,r);
		}
	}
}

// Graham scan: implementation
/* choose point p with smallest y-coordinate; sort points by polar angle with p; consider point in oreder and discard unless it create a ccw turn */
public class Point2D {
	private final double x;
	private final double y;
	public Point2D ( double x, double y) {
		this.x = x;
		this.y = y;
	}
	public static int ccw (Point2D a, Point2D b, Point2D c ) {
		double area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
		if (area2<0) return -1; //cw
		else if (area2 > 0) return +1; //ccw
		else return 0; //collinear
	}
}
Stack < Point2D> hull = new Stack <Point> ();
Array.sort (p, Point2D.Y_ORDER); //p[0] now is the point with lowest y_coordinate
Array.sort (p, p[0].BY_POLAR_OERDER); // sort by polar angle with respect to p[0]
hull.push (p[0]); //definitely on  hull
hull.push (p[1]);
for (int i= 2; i<N; i++){
	Point2D top = hull.pop();
	while (Point2D.ccw(hull.peek(), top, p[i] <=0)//discard points that would create cw turn
		top = hull.pop();
	hull.push (top);
	hull.push(p[i]); // add p[i] to putative hull
}