Quicksort

excerpt: This covers the quicksort inplace implementation and runtime complexity. tags: two-pointers divide-and-conquer

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.

1
2
3
4
5
6
def quicksort(array, start, stop)
  # The 5 steps outlined above goes here
  
  quicksort(array, start middle - 1)
  quicksort(array, middle + 1, stop)
end

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def quicksort(array, start, stop)
  # If the list has no more than one element, it is sorted
  if start >= stop
    return
  end
  
  # Pick a random index for the pivot element
  index = rand(start..stop)
  pivot = array[index]
  
  # Move items < pivot to the front of array and
  # items >= pivot to the end of the array
  
  low = start
  high = stop
  
  while true
    # Search the array from back to front starting at high
    # to find the last item where value < pivot
    # Move that item into the hole
    while array[high] >= pivot 
      high = high - 1
      
      # break from inner loop
      if high <= low
        break
      end
      
      if high <= low
        # The left and right pieces have met in the middle
        # so we are done. Put the pivot here and break out
        # of the outer while loop
        array[low] = pivot

        break
      end
      
      # Move the value we found to the lower half
      array[low] = array[high]
      
      # Search the array from front to back starting at low
      # to find the first item where value >= pivot
      # Move that item into the hole
      low = low + 1
      while array[low] < pivot
        low = low + 1
        
        # break out of this while loop
        if low >= high
          break
        end
      end

      if low >= high
        # The left and right pieces have met in the middle
        # so we are done. Put the pivot here and break out
        # of the outer while loop
        low = high
        array[high] = pivot

        break      
    end
    
    # Move the value we found to the upper half
    array[high] = array[low]
  end
  
  # recursively sort the two halves
  quicksort(array, start, low - 1)
  quicksort(array, low + 1, stop)
end

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def quick_sort(array, first, last)
  if first < last
    index = partition(array, first, last)
    quick_sort(array, first, index)
    quick_sort(array, index+1, last)
  end

  array
end

def partition(array, low, high)
  i = low - 1
  j = high + 1
  pivot = array[low]
  
  loop do
    begin
      i += 1
      break if i == high
    end until array[i] >= pivot
    
    begin
      j -= 1
      break if j == low
    end until array[j] <= pivot
    
    # break the loop if pointers cross
    break if i >= j
    array[i], array[j] = array[j], array[i]
  end
  
  return j
end

array = [7, 3, 11, 1, 2, 6, 10, 8, 9, 4, 5]
low = 0
high = array.size - 1

p quick_sort(array, low, high)