What is Parallel Count Sort?
Parallel count sort is an efficient algorithm that sorts an array of elements in a parallel manner. It is a variation of the classic count sort algorithm which is used to sort a collection of objects based on their frequency. The algorithm is based on the idea of counting the number of elements in a particular range and then sorting the elements according to their frequency.
Parallel count sort is a fast and efficient sorting algorithm that is suitable for applications that require a large amount of data to be sorted. It is especially useful for sorting large datasets. The algorithm is based on the idea of counting the number of elements in a particular range and then sorting the elements according to their frequency. The main advantage of the parallel count sort is that it can be implemented in a distributed system and can be used to sort large amounts of data quickly.
Example:
Input: arr[] =[ 5, 3, 4, 6, 1, 2, 7, 9, 8 ]
Output: sorted array: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
Assumptions for the Algorithm:
The algorithm makes some assumptions about the data that is being sorted. These assumptions are:
- The data is discrete and can be represented as integers.
- The data is distributed uniformly across the range of values that are being sorted.
- The data is evenly distributed across the range of values that are being sorted.
- The data is sorted in ascending order.
Algorithmic Approach:
The algorithm works by counting the number of elements in a particular range and then sorting the elements according to their frequency. The algorithm starts by counting the number of elements in a particular range and then sorting the elements according to their frequency.
Illustrations:
Consider an array arr[] = { 5, 3, 4, 6, 1, 2, 7, 9, 8};
Follow the below steps to solve the above approach:
- Count the number of elements in each range.
- For example, in the above array, the number of elements in the range 1 to 3 is 3 (1, 2, 3). The number of elements in the range 3 to 5 is 2 (4, 5). The number of elements in the range 6 to 8 is 3 (6, 7, 8). The number of elements in the range of 9 to 10 is 1 (9).
- Sort the elements in each range according to their frequency.
- For example, in the above array, the elements in the range 1 to 3 will be sorted in ascending order (1, 2, 3). The elements in the range 3 to 5 will be sorted in ascending order (4, 5). The elements in the range 6 to 8 will be sorted in ascending order (6, 7, 8). The element in the range 9 to 10 will be sorted in ascending order (9).
- Merge the sorted elements in each range.
- For example, in the above array, the sorted elements in the range 0 to 2 will be merged with the sorted elements in the range 3 to 5 (1, 2, 3, 4, 5). The sorted elements in the range 6 to 8 will be merged with the sorted elements in the range 9 to 10 (6, 7, 8, 9).
- The merged elements are now sorted in ascending order.
- The merged elements will be sorted in ascending order (1, 2, 3, 4, 5, 6, 7, 8, 9).
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <iostream> #include <omp.h> #include <vector> using namespace std; // Function to find maximum value in array int getMax(vector<int> arr, int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // Count sort of arr[] void countSort(vector<int>& arr, int n, int exp) { // Output array int output[n]; int i, count[10] = { 0 }; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0; i < n; i++) arr[i] = output[i]; } // Parallel count sort void parallelCountSort(vector<int>& arr, int n) { int m = getMax(arr, n); // Do counting sort for every digit. Note that instead // of passing digit number, exp is passed. exp is 10^i // where i is current digit number for (int exp = 1; m / exp > 0; exp *= 10) { for (int i = 0; i < n; i++) countSort(arr, n, exp); } } // Driver program to test above functions int main() { vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.size(); cout << "Array before sorting: \n"; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << "\n"; parallelCountSort(arr, n); cout << "Array after sorting: \n"; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { // Function to find maximum value in array public static int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // Count sort of arr[] public static void countSort(int arr[], int n, int exp) { // Output array int output[] = new int[n]; int i; int count[] = new int[10]; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current // digit for (i = 0; i < n; i++) arr[i] = output[i]; } // Parallel count sort public static void parallelCountSort(int arr[], int n) { int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp > 0; exp *= 10) { for (int i = 0; i < n; i++) countSort(arr, n, exp); } } // Driver Code public static void main(String[] args) { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.length; System.out.print("Array before sorting: \n"); for (int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } System.out.println(); parallelCountSort(arr, n); System.out.print("Array after sorting: \n"); for (int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } } } // This code is contributed by Rohit Pradhan |
Python3
# python implementation from typing import List def get_max(arr: List[int]) -> int: mx = arr[0] for i in range(1, len(arr)): if arr[i] > mx: mx = arr[i] return mx def count_sort(arr: List[int], exp: int): output = [0] * len(arr) count = [0] * 10 # Store count of occurrences in count[] for i in range(len(arr)): count[(arr[i] // exp) % 10] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output[] for i in range(1, 10): count[i] += count[i - 1] # Build the output array for i in range(len(arr) - 1, -1, -1): output[count[(arr[i] // exp) % 10] - 1] = arr[i] count[(arr[i] // exp) % 10] -= 1 # Copy the output array to arr[], so that arr[] now # contains sorted numbers according to current digit for i in range(len(arr)): arr[i] = output[i] def parallel_count_sort(arr: List[int]): m = get_max(arr) # Do counting sort for every digit. Note that instead # of passing digit number, exp is passed. exp is 10 ^ i # where i is current digit number exp = 1 while m // exp > 0: for i in range(len(arr)): count_sort(arr, exp) exp *= 10 # Driver program to test above functions def main(): arr = [170, 45, 75, 90, 802, 24, 2, 66] print("Array before sorting:") print(arr) parallel_count_sort(arr) print("Array after sorting:") print(arr) if __name__ == "__main__": main() # This code is contributed by ksam24000 |
C#
// C# code for the above approach: using System; public class GFG { // Function to find maximum value in array public static int getMax(int[] arr, int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // Count sort of arr[] public static void countSort(int[] arr, int n, int exp) { // Output array int[] output = new int[n]; int i; int[] count = new int[10]; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current // digit for (i = 0; i < n; i++) arr[i] = output[i]; } // Parallel count sort public static void parallelCountSort(int[] arr, int n) { int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp > 0; exp *= 10) { for (int i = 0; i < n; i++) countSort(arr, n, exp); } } // Driver Code static public void Main() { int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.Length; Console.Write("Array before sorting: \n"); for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } Console.Write("\n"); parallelCountSort(arr, n); Console.Write("Array after sorting: \n"); for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } } } // This code is contributed by Pushpesh Raj |
Javascript
// Javascript code for the above approach. // Function to find maximum value in array function getMax(arr, n) { let mx = arr[0]; for (let i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // Count sort of arr[] function countSort(arr, n, exp) { // Output array let output=new Array(n); let count=new Array(10).fill(0); let x = Math.floor(arr[i] / exp); // Store count of occurrences in count[] for (let i = 0; i < n; i++) count[x % 10]++; // Change count[i] so that count[i] now contains actual // position of this digit in output[] for (let i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (let i = n - 1; i >= 0; i--) { output[count[x % 10] - 1] = arr[i]; count[x % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (let i = 0; i < n; i++) arr[i] = output[i]; } // Parallel count sort function parallelCountSort(arr, n) { let m = getMax(arr, n); // Do counting sort for every digit. Note that instead // of passing digit number, exp is passed. exp is 10^i // where i is current digit number for (let exp = 1; m / exp > 0; exp *= 10) { for (let i = 0; i < n; i++) countSort(arr, n, exp); } } // Driver program to test above functions let arr = [ 170, 45, 75, 90, 802, 24, 2, 66 ]; let n = arr.length; console.log("Array before sorting: <br>"); for (let i = 0; i < n; i++) { console.log(arr[i] + " "); } console.log("<br>"); parallelCountSort(arr, n); console.log("Array after sorting: <br>"); for (let i = 0; i < n; i++) { console.log(arr[i] + " "); } // This code is contributed by Aman Kumar. |
Output
Array before sorting: 170 45 75 90 802 24 2 66 Array after sorting: 2 24 45 66 75 90 170 802
Time Complexity: O(NlogN)
Auxiliary space: O(N)
The difference with Sequential Count Sort:
- The main difference between the parallel count sort and the sequential count sort is that the parallel count sort is much faster than the sequential count sort. This is because the parallel count sort is able to process large amounts of data in parallel. The sequential count sort, on the other hand, can only process data sequentially.
- Another difference between the two algorithms is that the parallel count sort is more suitable for distributed systems, while the sequential count sort is better suited for single-machine systems.
- The parallel count sort is also more suitable for sorting large datasets as it can process data in parallel.
Conclusion:
In conclusion, the parallel count sort is a fast and efficient sorting algorithm that is suitable for applications that require a large amount of data to be sorted. It is especially useful for sorting large datasets. The algorithm is based on the idea of counting the number of elements in a particular range and then sorting the elements according to their frequency. The main advantage of the parallel count sort is that it can be implemented in a distributed system and can be used to sort large amounts of data quickly.
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
