Quicksort
excerpt: This covers the quicksort inplace implementation and runtime complexity. tags: twopointers divideandconquer
Quick Sort is a divide and conquer algorithm. The goal is to sort a list in ascending order.
Steps
 Pick an element in the array. This is the pivot.
 Partition the list moving the pivot to its correct position making sure that all the lower elements are on its left and all the larger elements are on its right.
 Sort the left part and the right part of the list recursively.
 Keep doing it until there’s nothing left to sort.
Implementation
What do we need to implement this algorithm?
 A method that swaps two elements
 A way to refer to parts of the list
 A method that places the pivot in its correct position and moves the elements around so that all the lower elements are on the left, and all the larger elements are on the right. Call it place_and_divide
 A method that implements the Quick Sort, that is:
 Pick a pivot
 place_and_divide
 quickSort left part
 quickSort right part
What can we use to denote a part of the list?
We can use the same idea used from binary search => keep track of the left and right index denoting where the part begins and ends.
Consider for example the list {5,3,6,1,2}. Then:
 The indices 0 and 4 denote the entire list.
 The indices 0 and 2 denote the part of the list with the 3 left most elements.
 The indices 1 and 3 denote the part of the list with the 3 middle elements.
The quicksort algorithm subdivides an array into two sub arrays and calls itself recursively to sort the subarrays.
 Pick a dividing item from the array. Call it the pivot.
 Move items < pivot to the front of the array.
 Move items >= pivot to the end of the array.
 Let middle be the index between the subarrays where pivot is placed.
 Recursively sor the two halves of the array.


The image shows an array of values to sort. The pivot is picked randomly, in this case, the pivot is the first value 6. In the second image, values less than the pivot have been moved to the beginning of the array and values greater than or equal to pivot have been moved to the end of the array. The pivot element is shaded at index 6. There is one other element with value 6 and it comes after the pivot in the array.
The two recursive calls are made to sort the two sub arrays before and after the pivot element. The result is shown in the third image.
Runtime Analysis
Consider the case in which the pivot element divides the array into two exactly equal halves at every step. The diagram shows this special case.
Each node in the tree represents a recursive call to quicksort. The line in the middle of the node shows how the array was divided into two equal halves. The two arrows out of the node represent the quicksort algorithm making two recursive calls to process the two halves.
The leaves of the tree represent calls to sort a single item. A single item list is already sorted, so these calls return without doing any work. The recursive calls work their way to the bottom of the tree. They return from the leaf nodes to the methods that called them, so control moves back up the tree.
If the array has N items and the items divide exactly evenly, the tree of quicksort calls is log N levels tall. Each call to quicksort must examine all the items in the sub array it is sorting. For example, a call to quicksort consisting of four elements needs to examine the four elements to further divide its values.
All the items in the original array are present at each level of the tree, so each level of the tree contains N items. If you add up the items that each call to quicsort must examine at any level of the tree, you get N items. That means the calls to quicksort on any level require N steps. The tree is log N levels tall and each level requires N steps, so the algorithm’s total run time is O(N log N).
The runtime will be O(N log N) even if the array is not divided exactly by half. The worst case time complexity is quadratic.
Space Complexity
The space used depends partly on the method used to divide parts of the array into halves, but it also depends on the algorithm’s depth of recursion. For the tree shown in the figure the stack grows by the depth of the tree. This means the program’s call stack will be O(log N) levels deep. The worst case occurs when the tree is tall and thin resulting in O(N) space complexity. The worst case scenario can be avoided by picking the pivot carefully.
In Place Quicksort
The items can be split into two groups and quicksort can run inplace without any extra space. The outline of the solution:
 Swap the dividing item to the beginning of the array.
 Remove the dividing item from the array.
 Repeat:
 Search the array from back to front to find the last item in the array less than the pivot element.
 Move that item into the hole.
 Search the array from front to back to find the first item in the array greater than or equal to the pivot element.
 Move that item into the hole.
Continue looking backwards from the end of the array and forwards from the start of the array, moving items into the hole, until the two regions of search meet somewhere in the middle. Place the dividing item in the hole, which is now between the two pieces and recursively call the algorithm to sort the two pieces.
The quicksort algorithm implementation:


The first line checks whether the section of the array contains one or fewer items, if so, it is sorted, so it returns.
If the section of the array contains at least two items, the first item is saved as the pivot element. Swap the pivot element to the beginning of the section so that it can found later.
The variables high and low saves the highest index in the lower part of the array and the lowest index in the upper part of the array. These two variables keep track of which items are placed in the two halves. They also track where the hole is left after each step.
The infinite while loop runs until the lower and upper pieces of the array grow to meet each other. Inside the outer while loop, the index high is used to search the array backwards until an item that should be in the lower part of the array is found. This item is moved into the hole left behind by the pivot element.
The low index is used to search the array forward until it finds an item that should be in the upper part of the array. This item is moved into the hole left behind by the previously moved item.
The search continues backward and forward through the array until the two parts meet. At that point the pivot element is put between the two parts and recursive calls sort the parts of the array.
Quicksort has O(N log N) runtime. In the worst case, it can be quadratic in time complexity. Heapsort has O(N log N) performance in all cases. But in practice quicksort is usually faster than heapsort.
Alternative Implementation

