Quick-sort with Hungarian folk dance

This totally made my day.




Hungarian dancers shows the sorting algorithms

Divide-and-Conquer Algorithms: QuickSort

What is QuickSort?

An efficient algorithm based on a Divide-and-Conquer principle for solving a problem efficiently. It is usually the algorithm of choice in most situations as it consumes relatively fewer resources during execution, and not too difficult to implement.

How does QuickSort work?

  • Divide the given array into two non-empty sub-arrays A[p…q] and A[q+1…r] such that every key in A[p…q] is less than or equal to every key in A[q+1…r].
  • Recursively, sort the two sub-arrays by calling Quicksort.
  • Conquer and combine all the results from all subproblems to merge them into one solution for the given problem.

QuickSort’s Advantages:

  1. In-place sorting, uses small stack.
  2. Takes nlogn time to sort n items on average.
  3. Short inner loop.

QuickSort’s Disadvantages:

  1. Depends on recursion, therefore when recursion is not available, the implementation tends to become a lot more complicated.
  2. Requires a quadratic time in the worst-case O(n^2).

Best Case Analysis:

Best Case situation is when QuickSort divides the array exactly in half. In other words, the best to be a median of the keys in A[p…r] every time partitioning is done.

Recurrence relation in this case is:

T(n) = T(n/2) + T(n/2) + O(n)

T(n) = 2T(n/2) + O(n)

T(n) = O(nlogn)

Worst Case Analysis:

Worst Case situation is when QuickSort is called on an already sorted array A[1…n]. The algorithm will partition the array into two unequal sizes (one large subarray yet to be divided recursively many times, and another small subarray possibly of size 1).

Therefore the running time will be proportional to:

T(n) = n + (n - 1) + (n - 2) + (n - 3) + … + 2

T(n) = [ (n + 2) ( n - 1) ] / 2

T(n) = O(n^2)