Quicksort algorithm - the fastest way to currently sort.

0-quicksort.md

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

##Quicksort

####Concept

• we know
  • partitioning places smaller items on the left and larger items on the right of a selected value
  • if we have 2 or 3 values, a partitioning operation will sort them in order
• partition recursively, halving the ranges every time
  • each recursion sorts ranges more and more
  • will eventually lead to ranges of 2 or 3 values
  • will lead to fully sorted array

####Implementation

• shuffle the array to make it randomly distributed (see analysis)
• partition the array
  • creates more ordered ranges
• partition both ordered ranges
• recursion of partitioning new more ordered ranges until all is sorted

####Analysis

• the whole process is done in place which means that it does not take any extra memory
  • no need for auxiliary array like in Mergesort
• the worst case (complexity) is ~N^2
  • this is extrememly unlikely if randomly shuffled
• the average case takes time ~N lgN
  • close to 1.39*N lgN if randomly shuffled
• makes more compares than Mergesort
• takes less time than Mergesort as it does not have to move memory around (Mergesort does and it is costly)

####Minor improvements

• skip small ranges altogether and do a single pass of Insertion sort at the end
  • can also do small ranges one at a time with Insertion sort
• try get partitioning pivots to be near the near the array's median value
  • take a sample of array elements (between 3 and 7)
  • take the median of the sample

####Notes

• not stable in its basic form
• Quicksort is finnicky
  • very sensitive to implementation
  • can quickly run in quadratic time if not implemented properly

1-partitioning.md

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

##Partitioning (Quicksort)

Process of creating an invariant - a condition which always holds as the sort takes place.

In the case of Quicksort the invariant is:

• for an item in the array (only one)
• all items to the left of it of it are smaller (not nec. in order)
• all items to the right of it are greater (not nec. in order)

Partitioning is the process that makes this happen.

####Concept

• pick a random element from the array (lets call this the pivot)
• go through the array from beginning to end and from end to beginning
• exchange larger values than the pivot near the left part of the array with values smaller than the pivot in the right part of the array
  • values smaller than the pivot are placed near the beginning
  • values larger than the pivot are placed near the end
• eventually you have only smaller values on the left part and only larger in the right part
• place thempivot in the middle of the two parts

####Implementation

• a random item is chosen from the array
  • if the array is pre-shuffled, the item can be the first one
• have three pointers i, j and k
  • k holds the position of the randomly chosen element
  • i starts from the beginning of the array and is incremented until it points to an element that is larger than k
  • j starts from the end of the array and is decremented until it points to an element that is smaller than k
• if both i and j have both stopped incrementing/decrementing
  • exchange the elements at i and j
  • this puts elements smaller than k to the left of the array and elements larger than k to the right
• eventually i and j will cross
  • when they do, most of the array should be partitioned
  • only check that k is placed in the middle of the two ranges
  • e.g. if k was the first element, exchange the element at k with the final position of j (which is now smaller than the element at k)

####See Also QuickSort

Quick.java

import java.util.Comparator;

public class Quick {
	public static void sort(Comparable[] a)
	{
		StdRandom.shuffle(a);	
		sort(a, 0, a.length - 1);
	}

	public static void sort(Object[] a, Comparator c)
	{
		StdRandom.shuffle(a);	
		 sort(a, 0, a.length - 1, c);
	}


	public static void sort(Object[] a, int lo, int hi, Comparator c)
	{
		if (hi <= lo) return;
		int mid = partition(a, lo, hi, c);

		/*
		 * must now sort _without_ inlcuding `mid` * else:
		 *  - `mid` will be reshuffled in the next sort 
		 *  - invariant of the higher recursion will be lost
		 *  - can result in infinite recursion
		 *
		 *  so from [lo; mid -1] and [mid + 1; hi]
		 */

		sort(a, lo, mid - 1, c);
		sort(a, mid + 1, hi, c);
	}

	public static void sort(Comparable[] a, int lo, int hi)
	{
		if (hi <= lo) return;
		int mid = partition(a, lo, hi);
		sort(a, lo, mid - 1);
		sort(a, mid + 1, hi);
	}


	public static int partition(Comparable[] a, int lo, int hi)
	{
		int i = lo;
		int j = hi + 1;

		while (true)
		{
			/*
			 * must use ++i and --j, rather than i++ and j--
			 * evaluation of `less` must be done on the same number that
			 * is used in the exchange
			 */

			while (less(a[++i], a[lo]))
				if (i == hi) break;
				
			while (less(a[lo], a[--j]))
				if (j == lo) break;
					
			if (i >= j) break;
			exch(a, i, j);
		}

		exch(a, j, lo);
		return j;
	}

	public static int partition(Object[] a, int lo, int hi, Comparator c)
	{
		int i = lo;
		int j = hi + 1;

		while (true)
		{
			while (less(a[++i], a[lo], c))
				if (i == hi) break;
				
			while (less(a[lo], a[--j], c))
				if (j == lo) break;
					
			if (i >= j) break;
			exch(a, i, j);
		}

		exch(a, j, lo);
		return j;
	}

	// test client
	public static void main(String[] args)
	{
		String[] arraypart = {"Q", "U", "I", "C", "K", "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
		String[] arraysort = new String[arraypart.length];
		System.arraycopy(arraypart, 0, arraysort, 0, arraypart.length);

		System.out.print("Original:\t");
		for (String str : arraypart)
			System.out.print(str);
		System.out.println();

		System.out.print("One partition:\t");
		Quick.partition(arraypart, 0, arraypart.length - 1);
		for (String str : arraypart)
			System.out.print(str);
		System.out.println();

		System.out.print("Full sort:\t");
		Quick.sort(arraysort);
		for (String str : arraysort)
			System.out.print(str);
		System.out.println();


	}

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

	private static boolean less(Object a, Object b, Comparator c)
	{ return c.compare(a, b) < 0; }

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

}