Implement a Multi-threaded Quicksort Algorithm in Python

In this article, we will learn about, The Multi-threaded Quicksort Algorithm. And how to implement it in Python.

What is the Quicksort Algorithm?

It is an algorithm that is used for sorting the elements of an array. It is more fast and efficient than other sorting methods. It is one of the comparison-based sorting methods. The important term in quicksort algorithms is the ‘pivot’ element. This can be chosen from the array and then we divide the remaining elements in the array into two subarrays. To divide the arrays into two subarrays, we consider whether the element is less than or greater than the pivot element.

What is a multithreaded Quicksort Algorithm?

It is an extension of the quicksort algorithm. It uses the mechanism of multithreading. It uses parallel processing for sorting which makes sorting faster. The regular quicksort algorithm uses sequential processing.

How to implement a multithreading Quicksort Algorithm in Python?

Importing the required libraries:

from threading import Thread
import concurrent.futures

In the above code, We are importing the libraries that we will be using for processing the code. the ‘threading’ module is used to manage threadings. The concurrent. futures helps us to manage the parallelization of tasks.

Define quicksort function:

def quicksort(array, first_element, last_element):
    if first_element < last_element:
        pi = partition(array, first_element, last_element)
        if (pi - first_element) > threshold and (last_element - pi) > threshold:
            with concurrent.futures.ThreadPoolExecutor(max_workers=2) as executor:
                executor.map(quicksort, [array, array], [first_element, pi + 1], [pi - 1, last_element])
        else:
            quicksort(array, first_element, pi - 1)
            quicksort(array, pi + 1, last_element)

In the above code, In the function named quicksort(), we are taking three arguments,i.e. ‘array’,’first_element’, and last_element’. Where array means, actual array, first_element, is the starting index of the portion of the array to be sorted, and last_element is the index of the last element of the array to be sorted.

The condition first_element < last_element, checks whether there are at least two elements in the array to sort or not. In the function, partition(), we are calling the partition function that we defined. The ‘if’ condition checks, whether the size of each partitioned array is greater than the predefined threshold or not. Based on this the program decides whether to create new threads or not. It varies based on the size of the array.

The line,’ with concurrent. futures.ThreadPoolExecutor(max_workers=2) as executor:’, we use, for parallel processing. With this, we suggest a system, to manage threads concurrently. max_workers=2 indicates at most two threads we are using for processing. Using, executor.map(), we are applying the map function to map the quicksort function to a given iterable, which is in zipped format.[first_element, pi + 1], indicating subarray from the left of the pivot, [pi – 1, last_element], indicating subarray from the right of the pivot. The else statement at the end indicates if the conditions of the ‘if’ are not satisfied then apply the quicksort function directly to given values.

Define partition function:

def partition(array, first_element, last_element):
    i = first_element - 1
    pivot = array[last_element]

    for j in range(first_element, last_element):
        if array[j] <= pivot:
            i = i + 1
            array[i], array[j] = array[j], array[i]

    array[i + 1], array[last_element] = array[last_element], array[i + 1]
    return i + 1

In the above code, under the function named partition(array, first_element, last_element): We are taking three arguments, ‘array’,’first_element’, and last_element.The ‘i’ value indicates the start index, where we start at the index just before the subarray that we are going to proceed.

Pivot is the last element we pick from the array. Inside the for loop, we are comparing each jth element from the array with the ith element, and then based on it we are swapping the elements at the end using (array[i], array[j] = array[j], array[i]). Using code, array[i + 1], array[last_element] = array[last_element], array[i + 1], we are sorting the values, so that the pivot element will move at the end of the segments to its position where it should be, i.e. just after the ith position.. Finally, we are returning the position of the pivot element.

Calling the  quicksort function to sort custom array:

arr = [50,45,34,10, 7, 8, 9, 1, 5,6,77,89]
threshold = 2 
quicksort(arr, 0, len(arr) - 1)
print(arr)

In the above code, first, we are defining the custom array with the name ‘arr’. Then we set a threshold that indicates the maximum that will be used for parallel processing. Finally, we are using the quicksort function and supplying parameters to it. Then finally printing value at the end.

Output:

[1, 5, 6, 7, 8, 9, 10, 34, 45, 50, 77, 89]