Quick Sort

                 Quick Sort is a sorting algorithm, which is commonly used in computer science. Quick Sort is a divide and conquer algorithm. It creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub arrays. There are two basic operations in the algorithm, swapping items in place and partitioning a section of the array.

Quick Sort Algorithm: Steps on how it works:

1. Find a “pivot” item in the array. This item is the basis for comparison for a single round.
2. Start a pointer (the left pointer) at the first item in the array.
3. Start a pointer (the right pointer) at the last item in the array.
4. While the value at the left pointer in the array is less than the pivot value, move the left pointer to the right (add 1). Continue until the value at the left pointer is greater than or equal to the pivot value.
5. While the value at the right pointer in the array is greater than the pivot value, move the right pointer to the left (subtract 1). Continue until the value at the right pointer is less than or equal to the pivot value.
6. If the left pointer is less than or equal to the right pointer, then swap the values at these locations in the array.
7. Move the left pointer to the right by one and the right pointer to the left by one.
8. If the left pointer and right pointer don’t meet, go to step 1.

Below is an image of an array, which needs to be sorted. We will use the Quick Sort Algorithm, to sort this array:

Important Characteristics of Quick Sort:

• Quick Sort is useful for sorting arrays.
• In efficient implementations Quick Sort is not a stable sort, meaning that the relative order of equal sort items is not preserved.
• Overall time complexity of Quick Sort is O(nLogn). In the worst case, it makes O(n2) comparisons, though this behavior is rare.
• The space complexity of Quick Sort is O(nLogn). It is an in-place sort (i.e. it doesn’t require any extra storage)

Quicksort Complexity

Time Complexities

Worst Case Complexity [Big-O]: O(n2)

• It occurs when the pivot element picked is either the greatest or the smallest element.
  This condition leads to the case in which the pivot element lies in an extreme end of the sorted array. One sub-array is always empty and another sub-array contains n - 1 elements. Thus, quicksort is called only on this sub-array.
  However, the quick sort algorithm has better performance for scattered pivots.
• Best Case Complexity [Big-omega]: O(n*log n)
  It occurs when the pivot element is always the middle element or near to the middle element.
• Average Case Complexity [Big-theta]: O(n*log n)
  It occurs when the above conditions do not occur.

Space Complexity

The space complexity for quicksort is O(log n).

Quicksort Applications

Quicksort is implemented when

• the programming language is good for recursion
• time complexity matters
• space complexity matters