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.
We develop the Python Merge Sort algorithm, one of the most famous sorting algorithms that uses the divide and conquer method, as well as the Quick Sort.
First of all we explain how this algorithm works.
First we divide the list into two sublists and then gradually into even smaller parts. Then we use a recursive function on each sublist and finally we combine the result in order to obtain the solution to the sorting algorithm.
Python Merge Sort – solution
Suppose we have a list of integers:
numbers = [6,12,4,3,7,8]
We indicate the index pointing to the number 6 with p and the index pointing to the number 8 with r.
numbers = [p,…,…, r]
As a first step, therefore, we divide the list in half using another index, for example q:
so we will have numbers_1 = [p,…,…, q] and numbers_2 = [q + 1,…,…, r]
It continues to divide until it can no longer be divided. This condition occurs when the array is empty or there is only one element left (ie 0 elements or 1).
The recursive sorting function is then invoked on each of the two halves. Finally it all comes combine.
In our example we have:
numbers = [6,12,4,3,7,8]
therefore: numbers_1 = [6,12,4,] and numbers_2 = [3,7,8] and so on.
Here, then, is a graphic representation of what happens:
Now that all the elements are divided, let’s use a support list and start sorting.
The second part of the Merge Sort algorithm, therefore, concerns the actual ordering of the elements in an order that can be increasing or decreasing.
We choose an increasing order. We sort and then combine each part of the sublists.
Python Merge Sort – code
Here is therefore a possible solution to the algorithm:
def merge_sort(list):
list_length = len(list)
if list_length == 1:
return list
q = list_length // 2 #calculate the central point
left = merge_sort(list[:q])
right = merge_sort(list[q:])
return merge(left, right)
def merge(left, right):
ordered = []
while left and right:
ordered.append((left if left[0] <= right[0] else right).pop(0))
return ordered + left + right
numbers = [10,5,12,1,9]
print(numbers)
sorted_list = merge_sort(numbers)
print(sorted_list)
Try the code in the compiler below:
Clearly that proposal is a possible solution to the Python Merge Sort algorithm, please implement yours and write it in the comments below.
Let’s study the Python Insertion Sort algorithm, a very simple sorting algorithm to implement.
The algorithm works in a very similar way to the way we arrange playing cards in our hand.
In fact, it is assumed that the first card is ordered, then an unsorted card is taken and placed on its left if it is smaller, on its right if it is greater. This way the unsorted cards will be put in their place.
The Insertion Sort sorting algorithm works in a very similar way.
Suppose the starting list is this:
numbers = [3,6,1,9,2]
The list is scrolled from position i which goes from 1 to n, then from number 6 to number 2.
So if the element of the list in position i is greater than its predecessor it does not move, if instead it is smaller it moves to the left until a smaller predecessor is found or the leftmost position of the array is reached.
Python Insertion Sort – code
We define an insertion_sort function that takes the list as a parameter.
We create a for loop that scrolls the elements of the list from a to 1 up to its length, we store the element to be compared in a temp variable and assign the previous element of index i to j.
Then with a while loop we continue until the element to be compared is smaller than its predecessors or reaches the leftmost position (ie the one with index 0). From time to time we exchange the element and decrease the variable j.
After the while loop, in any case, we assign the value of temp to a [j + 1], even if there have been no exchanges.
So here is our Python Insertion Sort code:
def insertion_sort(a):
for i in range(1, len(a)):
temp = a[i] #first item to compare
j = i-1 #the first time is the first element
while j >= 0 and temp < a[j]:
a[j+1] = a[j]
j -= 1
a[j+1] = temp
a = [3,6,1,9,2]
insertion_sort(a)
print(a)
We could also avoid using the temporary variable by assigning the variable i to j. Here is a possible implementation:
def insertion_sort(a):
for i in range(1, len(a)):
j = i
while j > 0 and a[j - 1] > a[j]:
a[j], a[j - 1] = a[j - 1], a[j]
j -= 1
a = [3,6,1,9,2]
insertion_sort(a)
print(a)
We can try our code in the editor below:
In this lesson we have developed the Python Insertion Sort algorithm, in the next we will study other sorting arlgorithms.
