QuickSort is a popular sorting technique based on divide and conquer algorithm. In this technique, an element is chosen as a pivot and the array is partitioned around it. The target of partition is, given an array and an element x of the array as a pivot, put x at its correct position in a sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
Multi-threading allows concurrent execution of two or more parts of a program for maximum utilization of CPU. Each part of such program is called a thread. So, threads are light-weight processes within a process.
Examples:
Input: arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Output: 1 2 3 4 5 6 7 8 9 10
Input: arr[] = {54, 64, 95, 82, 12, 32, 63}
Output: 12 32 54 63 64 82 95
Approach: The main idea of the approach is:
- The main thread calls the quicksort method.
- The method partitions the array and checks for the number of current threads.
- New threads is called for next step using the same parallel method.
- Use the single normal quicksort method.
Below is the program uses ForkJoinPool thread pool to keep number of thread same as the number of CPUs and reuse the threads:
C++
#include <iostream>#include <vector>#include <algorithm>#include <cstdlib>#include <ctime>#include <omp.h>using namespace std;class QuickSortMultiThreading {public: QuickSortMultiThreading(int start, int end, vector<int>& arr) : start_(start), end_(end), arr_(arr) {} // Finding random pivoted and partition // array on a pivot. // There are many different // partitioning algorithms. int partition(int start, int end, vector<int>& arr) { int i = start; int j = end; // Decide random pivot int pivoted = rand() % (j - i + 1) + i; // Swap the pivoted with end // element of array int t = arr[j]; arr[j] = arr[pivoted]; arr[pivoted] = t; j--; // Start partitioning while (i <= j) { if (arr[i] <= arr[end]) { i++; continue; } if (arr[j] >= arr[end]) { j--; continue; } t = arr[j]; arr[j] = arr[i]; arr[i] = t; j--; i++; } // Swap pivoted to its // correct position t = arr[j + 1]; arr[j + 1] = arr[end]; arr[end] = t; return j + 1; } // Function to implement // QuickSort method void operator() () { // Base case if (start_ >= end_) { return; } // Find partition int p = partition(start_, end_, arr_); // Divide array QuickSortMultiThreading left(start_, p - 1, arr_); QuickSortMultiThreading right(p + 1, end_, arr_); // Left subproblem as separate thread #pragma omp parallel sections { #pragma omp section { left(); } #pragma omp section { right(); } } }private: int start_; int end_; vector<int>& arr_;};int main() { int n = 7; vector<int> arr = {54, 64, 95, 82, 12, 32, 63}; srand(time(NULL)); QuickSortMultiThreading(0, n - 1, arr)(); for (int i = 0; i < n; i++) { // Print sorted elements cout << arr[i] << " "; } cout << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.Random;import java.util.concurrent.ForkJoinPool;import java.util.concurrent.RecursiveTask;public class QuickSortMutliThreading extends RecursiveTask<Integer> { int start, end; int[] arr; /** * Finding random pivoted and partition * array on a pivot. * There are many different * partitioning algorithms. * @param start * @param end * @param arr * @return */ private int partition(int start, int end, int[] arr) { int i = start, j = end; // Decide random pivot int pivoted = new Random() .nextInt(j - i) + i; // Swap the pivoted with end // element of array; int t = arr[j]; arr[j] = arr[pivote]; arr[pivote] = t; j--; // Start partitioning while (i <= j) { if (arr[i] <= arr[end]) { i++; continue; } if (arr[j] >= arr[end]) { j--; continue; } t = arr[j]; arr[j] = arr[i]; arr[i] = t; j--; i++; } // Swap pivoted to its // correct position t = arr[j + 1]; arr[j + 1] = arr[end]; arr[end] = t; return j + 1; } // Function to implement // QuickSort method public QuickSortMutliThreading(int start, int end, int[] arr) { this.arr = arr; this.start = start; this.end = end; } @Override protected Integer compute() { // Base case if (start >= end) return null; // Find partition int p = partition(start, end, arr); // Divide array QuickSortMutliThreading left = new QuickSortMutliThreading(start, p - 1, arr); QuickSortMutliThreading right = new QuickSortMutliThreading(p + 1, end, arr); // Left subproblem as separate thread left.fork(); right.compute(); // Wait until left thread complete left.join(); // We don't want anything as return return null; } // Driver Code public static void main(String args[]) { int n = 7; int[] arr = { 54, 64, 95, 82, 12, 32, 63 }; // Forkjoin ThreadPool to keep // thread creation as per resources ForkJoinPool pool = ForkJoinPool.commonPool(); // Start the first thread in fork // join pool for range 0, n-1 pool.invoke( new QuickSortMutliThreading( 0, n - 1, arr)); // Print shorted elements for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); }} |
Python3
# Python3 program for the above approachimport randomfrom concurrent.futures import ThreadPoolExecutorclass QuickSortMultiThreading: def __init__(self, start, end, arr): self.start = start self.end = end self.arr = arr # Finding random pivoted and partition # array on a pivot. # There are many different # partitioning algorithms. # @param start # @param end # @param arr # @return def partition(self, start, end, arr): i = start j = end # Decide random pivot pivoted = random.randint(i, j) # Swap the pivoted with end # element of array t = arr[j] arr[j] = arr[pivoted] arr[pivoted] = t j -= 1 # Start partitioning while i <= j: if arr[i] <= arr[end]: i += 1 continue if arr[j] >= arr[end]: j -= 1 continue t = arr[j] arr[j] = arr[i] arr[i] = t j -= 1 i += 1 # Swap pivoted to its # correct position t = arr[j + 1] arr[j + 1] = arr[end] arr[end] = t return j + 1 # Function to implement # QuickSort method def __call__(self): # Base case if self.start >= self.end: return # Find partition p = self.partition(self.start, self.end, self.arr) # Divide array left = QuickSortMultiThreading(self.start, p - 1, self.arr) right = QuickSortMultiThreading(p + 1, self.end, self.arr) # Left subproblem as separate thread with ThreadPoolExecutor(max_workers=2) as executor: futures = [executor.submit(left), executor.submit(right)] for future in futures: future.result()# Driver Codeif __name__ == '__main__': n = 7 arr = [54, 64, 95, 82, 12, 32, 63] QuickSortMultiThreading(0, n - 1, arr)() for i in range(n): # Print shorted elements print(arr[i], end=' ') |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Threading.Tasks;class QuickSortMultiThreading { private int start; private int end; private int[] arr; private Random random; public QuickSortMultiThreading(int start, int end, int[] arr) { this.start = start; this.end = end; this.arr = arr; random = new Random(); } // Finding random pivoted and partition // array on a pivot. // There are many different // partitioning algorithms. // @param start // @param end // @param arr // @return private int Partition(int start, int end, int[] arr) { int i = start; int j = end; // Decide random pivot int pivoted = random.Next(i, j + 1); // Swap the pivoted with end // element of array int t = arr[j]; arr[j] = arr[pivoted]; arr[pivoted] = t; j -= 1; // Start partitioning while (i <= j) { if (arr[i] <= arr[end]) { i += 1; continue; } if (arr[j] >= arr[end]) { j -= 1; continue; } t = arr[j]; arr[j] = arr[i]; arr[i] = t; j -= 1; i += 1; } // Swap pivoted to its // correct position t = arr[j + 1]; arr[j + 1] = arr[end]; arr[end] = t; return j + 1; } // Function to implement // QuickSort method public void Sort() { if (start >= end) { return; } int p = Partition(start, end, arr); QuickSortMultiThreading left = new QuickSortMultiThreading(start, p - 1, arr); QuickSortMultiThreading right = new QuickSortMultiThreading(p + 1, end, arr); List<Task> tasks = new List<Task>(); tasks.Add(Task.Run(() => left.Sort())); tasks.Add(Task.Run(() => right.Sort())); Task.WaitAll(tasks.ToArray()); }}// Driver Codeclass Program { static void Main(string[] args) { int n = 7; int[] arr = { 54, 64, 95, 82, 12, 32, 63 }; QuickSortMultiThreading quickSort = new QuickSortMultiThreading(0, n - 1, arr); quickSort.Sort(); for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } }}// This code is contributed by shivhack999 |
Javascript
class QuickSortMultiThreading { constructor(start, end, arr) { this.start = start; this.end = end; this.arr = arr; } // Finding random pivoted and partition // array on a pivot. // There are many different // partitioning algorithms. partition(start, end, arr) { let i = start; let j = end; // Decide random pivot const pivoted = Math.floor(Math.random() * (j - i + 1)) + i; [arr[j], arr[pivoted]] = [arr[pivoted], arr[j]]; j--; // Start partitioning while (i <= j) { if (arr[i] <= arr[end]) { i++; continue; } if (arr[j] >= arr[end]) { j--; continue; } [arr[j], arr[i]] = [arr[i], arr[j]]; j--; i++; } [arr[j + 1], arr[end]] = [arr[end], arr[j + 1]]; return j + 1; } // Function to implement // QuickSort method operator() { if (this.start >= this.end) { return; } const p = this.partition(this.start, this.end, this.arr); const left = new QuickSortMultiThreading(this.start, p - 1, this.arr); const right = new QuickSortMultiThreading(p + 1, this.end, this.arr); const numThreads = 2; // Number of threads for parallel sections const promises = [ new Promise(resolve => resolve(left.compute())), new Promise(resolve => resolve(right.compute())) ]; return Promise.all(promises); }}const n = 7;const arr = [54, 64, 95, 82, 12, 32, 63];const mainInstance = new QuickSortMultiThreading(0, n - 1, arr);await mainInstance.operator();console.log(arr.join(' ')); |
Output
12 32 54 63 64 82 95
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
