4.3. Quick Sort

Quick sort is one of the more recently developed sorting algorithms, developed by Tony Hoare in 1959. Much like Merge Sort, Quick Sort is a divide-and-conquer algorithm and is comparison-based. It works by selecting one of the elements in the given list as pivot and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The process is then repeated for the two sublists.

The key process in Quick Sort is partition. The target of partition is to place the pivot (any element can be chosen to be a pivot) at its correct position in the list and put all smaller elements to the left of the pivot, and make sure all greater elements to the right of the pivot.

The process of partition is described in details, with implementation, below:

Partition

The problem of partitition requires placing the pivot (any element can be chosen to be a pivot) at its correct position in the sorted array and put all smaller elements to the left of the pivot, and all greater elements to the right of the pivot.

Although any element in the list can be chosen as the pivot, the most common choice is to choose the last element as the pivot. It makes visualization easier and the implementation of the algorithm simpler.

Once the pivot is chosen, we follow the following steps:

1. Take two variables to point left and right of the list excluding pivot

   • left points to the low index and right points to the highest index

2. While data[left] > pivot, keep moving left towards right

3. While data[right] > pivot, keep moving right towards left

4. If data[left] > data[right] then swap the values

5. Eventually, left >= right, the point where they met is the new location of pivot

Below is visualization of the partition process, annotated with the implementation that follows.

The code for the partition process is as follows:

def partition(data, start, end):

    pivot = data[end]
    left = start
    right = end - 1

    while left < right:

        # move left towards right
        while data[left] < pivot:
            left = left + 1

        # move right towards left
        while right > 0 and data[right] > pivot:
            right = right - 1

        if left < right:
            data[left], data[right] = data[right], data[left]
	
    # insert pivot into its correct place
    data[left], data[end] = data[end], data[left]

    return left

Now that we have the partition process, we can implement the Quick Sort algorithm by calling the partition process repeatedly on ever smaller sublists.

Fig. 4.6 Animation of an example of Quick Sort algorithm.
Note that the element with black background is the pivot element at current step.

4.3.1. Algorithm

The steps of the iterative QuickSort algorithm are:

1. Call partition on the entire array. This will place the pivot element in its correct position in the sorted array, and place all smaller elements to the left of the pivot, and all greater elements to the right of the pivot.

2. Call partition on the left sublist and right sublists.

3. Repeat the process for the left and right sublists until the base case is reached, i.e. the sublist has only one element.

Note that the sublists are not created explicitly. Instead, the algorithm uses the indices to keep track of the sublists.

4.3.2. Implementation

def partition(data, start, end):

    pivot = data[end]
    left = start
    right = end - 1

    while left < right:

        # move left towards right
        while data[left] < pivot:
            left = left + 1

        # move right towards left
        while right > 0 and data[right] > pivot:
            right = right - 1

        if left < right:
            data[left], data[right] = data[right], data[left]
	
    # insert pivot into its correct place
    data[left], data[end] = data[end], data[left]

    return left

def quick_sort(data):

    sublists = [(0, len(data) - 1)]

    while len(sublists) > 0:
        
        start, end = sublists[-1]
        sublists.remove((start, end))

        pivot_loc = partition(data, start, end)

        # If there are elements on left side of pivot,
        # then add them to the stack
        if pivot_loc - start > 1:
            sublists.append((start, pivot_loc - 1))

        # If there are elements on right side of pivot,
        # then add them to the stack
        if end - pivot_loc > 1:
            sublists.append((pivot_loc + 1, end))

a = [5, 4, 3, 2, 1]
quick_sort(a)
print(a)

[1, 2, 4, 3, 5]

4.3.3. Recursive Implementation

For recursive implementation, go to Section 5.6.1