Python Multi-threading and Concurrency: Multi-threaded quicksort implementation

Last update on December 21 2024 07:47:15 (UTC/GMT +8 hours)

Write a Python program to implement a multi-threaded quicksort algorithm.

Sample Solution:

Python Code:

import threading

def partition(nums, low, high):
    i = low - 1
    pivot = nums[high]
  
    for j in range(low, high):
        if nums[j] <= pivot:
            i = i + 1
            nums[i], nums[j] = nums[j], nums[i]
  
    nums[i + 1], nums[high] = nums[high], nums[i + 1]
    return i + 1


def quick_sort(nums, low, high):
    if low < high:
        pi = partition(nums, low, high)
  
        # Create two threads to sort the two halves of the array concurrently
        left_thread = threading.Thread(target=quick_sort, args=(nums, low, pi - 1))
        right_thread = threading.Thread(target=quick_sort, args=(nums, pi + 1, high))
  
        # Start the threads
        left_thread.start()
        right_thread.start()
  
        # Wait for both threads to finish
        left_thread.join()
        right_thread.join()


# Example usage
arr = [4, 5, 8, 3, 0, 5, 3, 9, 4, 3]
print("Original array:", arr)

# Perform multi-threaded quicksort
quick_sort(arr, 0, len(arr) - 1)

print("Sorted array:", arr)

Sample Output:

Original array: [4, 5, 8, 3, 0, 5, 3, 9, 4, 3]
Sorted array: [0, 3, 3, 3, 4, 4, 5, 5, 8, 9]

Explanation:

In the above code, the "partition()" function is used to select a pivot and partition the array into two sub-arrays based on the pivot. The "quick_sort()" function recursively calls itself to sort the sub-arrays. Instead of sequentially executing the recursive calls, this implementation creates two threads to sort the left and right sub-arrays simultaneously.

The program starts two threads using threading.Thread, each targeting the "quicksort()" function with the appropriate sub-array bounds. After starting the threads, it waits for both threads to finish using the join method.

Flowchart:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Multi-threaded merge sort implementation.
Next: Concurrent HTTP requests with threads.