Python Quicksort

We implement the Python Quicksort algorithm, also known as the sorting algorithm which is based on the divide and conquer approach!

Its operation is based on the pivot, which is an element that can be selected in various ways. Throughout this guide we will study the various ways. In fact, for example, the pivot can be the first element, or the last or even the middle element and finally it can also be an element chosen at random.

The reasoning behind this algorithm is the partition, or the subdivision of an array into subarray. We will place the smaller elements of the pivot on its left while the larger elements will be positioned on its right.

Python Quicksort – how it work

Starting list:

number_list = [10,5,12,1,9,7]

The steps to sort any list with the quicksort are these:

• Divide – By dividing the list to be sorted, we break down the problem into sub-problems.
• Impera – The algorithm is solved and recursion is applied.
• Combine – Combine the previous outputs obtained from recursive calls.

Let’s start with the first step, which is the partition.

We choose the last element as a pivot: 7. To extract it, I simply use the pop method of Python, so we will have:

pivot = number_list.pop ()

Then we create two empty lists, low and high to contain the smaller and larger elements of the pivot respectively.

low, high = [], []

We compare each element with the pivot and insert it in the appropriate list.

number_list = [10,5,12,1,9,7]
pivot = number_list.pop()
high, low = [], []

for number in number_list:
    if number > pivot:
        high.append(number)
    else:
        low.append(number)

print(number_list)
print(high)
print(low)

In this way, the number_list list will no longer contain the last element because it has been extracted and the two high and low lists are populated with the largest and smallest elements of the pivot, respectively.

The output produced will be this:

number_list: [10, 5, 12, 1, 9] # element 7, or the pivot, is missing
high: [10, 12, 9] #all elements greater than 7
low: [5, 1] ​​#all elements less than or equal to 7

As we can see, the two high and low lists are not sorted. What can we do?

We can certainly apply the same method to these two sub-lists. So we call the function recursively.

Remember to check the length of the list and stop when it has no more elements.

So let’s write all the algorithm that allows us to solve the sorting using the quicksort in Python.

def quick_sort(numbers):
    length = len(numbers)
    if length <= 1:
        return numbers
    
    pivot = numbers.pop()
    high, low = [], []
    for number in numbers:
        if number > pivot:
            high.append(number)
        else:
            low.append(number)
    return quick_sort(low) + [pivot] + quick_sort(high)
number_list = [10,5,12,1,9,7]
print(quick_sort(number_list))

You can try the algorithm in the online compiler below:

Python Quicksort – Another solution

The most classic solution of the quicksort algorithm is this:

def quicksort(numbers, p, r):
    """indichiamo con:
        p - l'indice della sottolista di sinistra
        r - l'indice della sottolista di destra
    """
    if p < r:
        q = partition(numbers, p, r)
        quicksort(numbers, p, q - 1)
        quicksort(numbers, q + 1, r)
def partition(numbers, p, r):
    pivot = numbers[r] #definiamo il pivot assegnando l'ultimo elemento
    i = p - 1 #inizilizziamo l'indice dell'array di sinistra
    for j in range(p, r):
        if numbers[j] <= pivot:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i] #scambio i valori
    numbers[i + 1], numbers[r] = numbers[r], numbers[i + 1] #scambio i valori
    return i + 1
number_list = [10,5,12,1,9,7]
quicksort(number_list,0,len(number_list)-1)
print(number_list)

Clearly there can be many other solutions on the Python quicksort algorithm, try to implement yours and leave it in the comments below.

Useful links

Python Tutorial

1. Introduction to dictionaries in Python
2. Use Python dictionaries
3. Create dictionaries in Python
4. Python get() method
5. keys() method
6. items() method
7. pop() method
8. popitem() method
9. Sort dictionary in Python