Quick Sort using Multi-threading

0 0 7 minutes read

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 approach
import 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 approach
import random
from concurrent.futures import ThreadPoolExecutor
 
class 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 Code
if __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 approach
using 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 Code
class 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(' '));