MIT OCW - Lecture 4 (Quicksort and Randomized Algorithms)

I completed the 4th Lecture today morning which was on QuickSort and Randomizing QuickSort.Here is what was covered

• How Quick sort fits into Divide and Conquer paradigm
• QuickSort pseudo code and algorithm explanation
• Time analysis of partition method i.e. Theta(n)
• Worst case time analysis of QuickSort i.e. when input is sorted or reverse sorted (Theta (n**2)h
• Best case time analysis of QuickSort when we the pivot always splits the array into two equal halves( Theta(nlg(n))
• Analysis for Average Case time of QuickSort when Pivot splits the array 1/10:9/10 (Theta(nlg(n))
• Time analysis of QuickSort when we alternate between best case and worst case for each recursive partition (Theta(nlg(n))
• Randomized Quicksort - How to overcome worst case by randomly picking a pivot so that the running time is independent of the input array order
• Time analysis of Randomized QuickSort (Theta(nlg(n))
  

This lecture expects a background in basics of probability and random variables(the proof for time analysis of Randomized quick sort uses Indicator random variables)

All in all QuickSort is one of the best practical algorithms available for sorting, of course it may needed to be tuned a little on a case by case basis e.g. if you expect sorted inputs at times, use randomized quick sorts, if the partition array size is say less than 5 elements use some other algorithm to sort it instead of recursively going all the way to one element to partition etc.

Here is a basic implementation of QuickSort in Java