Selection sort.

0-selection-sort.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Selection Sort

####Concept

• iterate through all items to find the smallest
• swap the found item with the front-most item | Repeat
• iterate through all remaining items to find the smallest |

####Analysis

    iterate N times     one less item each time
          |                   |
      (c1 * N) * c2 + (c1 * N-1) * c2 + (c1 * N-2) * c2 + ... + c1 * c2
                |
            perform swap

    = c2 * (N - 1) + c1 * (1 + 2 + 3 + ... + N)
    = c2 * (N - 1) + c1 * N*(N + 1)/2
    ~ 1/2 * N^2

TLDR Selection sort takes time:

    ~N-1 compares and ~1/2 * N^2 exchanges

Selection sort is independent of input order - it will always take the same amount of time for a given input size.

Selection.java

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

	public static boolean less(Comparable v, Comparable w)
	{
		return v.compareTo(w) < 0;
	}

	public static void exch(Comparable[] a, int i, int j)
	{
		Comparable tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	public static boolean isSorted(Comparable[] a)
	{
		for (int i = 1; i < a.length; i++)
			if(less(a[i], a[i-1]))
				return false;
		return true;
	}

	public static void main(String[] args){

		int N = Integer.parseInt(args[0]);
		Integer[] array = new Integer[N];

		for (int i = 0; i < array.length; i++) {
			array[i] = (int)(Math.random() * 100);
			System.out.print(array[i] + " ");
		}

		Selection.sort(array);


		for (int i : array)
			System.out.print(i + " ");
		
		System.out.println(Selection.isSorted(array));
	}
	
}