Understanding and Implementing Quick Sort in Python

Last time I covered the theory and implementation of binary search, but now let’s turn to sort algorithms. Before an array can be searched, it must be sorted. One of the most efficient sorting algorithms is Quick Sort, and we’ll be exploring how to implement Quick Sort in Python below. However, let’s go over the theory behind Quick Sort first. 

Quicksort is an example of applying a divide-and-conquer approach to solving a problem. We can make sorting a large array of unsorted value easy by dividing the problem down into smaller steps and just applying these steps again and again until the array is sorted.

The primary concept employed in Quick Sort is partitioning. As we partition, we divide the array into smaller portions and then sort these small chunks. How do we sort the small portions of the array? We do this by first selecting a pivot, or a point in the array that the rest of the array will be shifted around.

After we select the pivot, we need to put the pivot in its correct position in the array. This means making sure that all values in the array smaller than the pivot are to the left and all values that are larger are to the right. We then recur on the right and left half of the array until everything is sorted.

Essentially, we can describe the algorithm as the following steps:

1. Choose a value as the pivot
2. Iterate through the array and  place all values smaller than the pivot the left, while all the values larger are to the right. This is done by comparing every value to the pivot. If a value is found that is out of order, the current value and the last sorted element are swapped.
3. After the above process is completer, the process is carried out on all the values to the left of the pivot value. 
4. The process is carried out again on all values to the right of the pivot.

How do you go about selecting a pivot value? There are multiple ways to select a pivot value. You can select the first value in the array, the last value in the array, the median value, or a random value.

The most common way that Quick Sort is implemented is by using the last value in the array as the pivot. The example implementation below will use the method where the final element in the array is chosen as the pivot.

Now we’ll take a look at how to implement QuickSort in Python.

To begin with, we’ll create a function that partitions the array. We’ll then use this function within another function to carry out the actual sorting. 

def partition(arr, low, high):

    # idx is the current index of the smaller array
    idx = (low - 1)
    pivot = arr[high]

    # c is current value in the loop
    for c in range(low, high):
        if arr[c] < pivot:
            idx = idx + 1

            arr[idx], arr[c] = arr[c], arr[idx]

    arr[idx + 1], arr[high] = arr[high], arr[idx + 1]
    return (idx + 1)

def quick_sort(arr, low, high):

    if low < high:
        p_idx = partition(arr, low, high)

        quick_sort(arr, low, p_idx-1)
        quick_sort(arr, p_idx+1, high)

arr = [12, 28, 33, 11, 38, 49, 36, 19, 100, 21, 5, 15, 3]
length = len(arr)
quick_sort(arr, 0, length - 1)
print("Array after sorting:")
for i in range(length):
    print(arr[i])

Here’s the results of running the program:

Array after sorting:
3
5
11
12
15
19
21
28
33
36
38
49
100

I suggest you experiment with different sorting algorithms as well as see how run times can vary when sorting arrays under different conditions.