w3resource

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


6. Multi-threaded Quicksort

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:

Flowchart: Python - Multi-threaded quicksort implementation

For more Practice: Solve these Related Problems:

  • Write a Python program to implement quicksort using multiple threads by concurrently sorting the partitions.
  • Write a Python script to develop a multi-threaded quicksort algorithm and print the pivot elements chosen at each recursive level.
  • Write a Python function that performs multi-threaded quicksort on a list of random integers and outputs the sorted list along with thread execution details.
  • Write a Python program to compare the performance of a multi-threaded quicksort with a single-threaded version on a large dataset.

Go to:


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

Python Code Editor :

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

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.