How to implement Parallel Quick Sort in C#

Parallel Quick Sort in C#

Quick Sort is a popular sorting algorithm that is commonly used due to its performance and simplicity. However, for large data sets, it can become slow as the sorting time increases. To speed up the sorting process, we can use parallelism. In this article, we will explore how to implement a Parallel Quick Sort algorithm in C#.

Parallel Quick Sort Algorithm

The Parallel Quick Sort algorithm is similar to the regular Quick Sort algorithm, but instead of recursively sorting the subarrays one after the other, it sorts them in parallel. This approach can improve the performance of the algorithm by utilizing multiple CPU cores.

Here is the implementation of Parallel Quick Sort algorithm in C#:

class ParallelQuickSort
{
    static void Main()
    {
        int[] arr = { 5, 4, 3, 2, 1 };
        QuickSort(arr, 0, arr.Length - 1);
        Console.WriteLine(string.Join(", ", arr));
    }

    static void QuickSort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int pivotIndex = Partition(arr, left, right);
            Parallel.Invoke(
                () => QuickSort(arr, left, pivotIndex - 1),
                () => QuickSort(arr, pivotIndex + 1, right)
            );
        }
    }

    static int Partition(int[] arr, int left, int right)
    {
        int pivot = arr[right];
        int i = left - 1;

        for (int j = left; j < right; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                Swap(arr, i, j);
            }
        }

        Swap(arr, i + 1, right);
        return i + 1;
    }

    static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

How it works

The QuickSort method takes an array, arr, and two indices, left and right. It first checks if left < right, which means that there are at least two elements in the array that need to be sorted. It then calls the Partition method to partition the array around a pivot element. The Partition method returns the index of the pivot element.

The Parallel.Invoke method is used to sort the left and right subarrays in parallel. This method takes one or more Action delegates that are executed in parallel. In this case, we pass two lambda expressions that call the QuickSort method recursively to sort the left and right subarrays.

The Partition method takes an array, arr, and two indices, left and right. It chooses the pivot element as the rightmost element in the array. It then loops through the array from the left index to the right index - 1. If the current element is less than the pivot, it swaps it with the element at the i index and increments i. Finally, it swaps the pivot element with the element at the i + 1 index and returns i + 1.

The Swap method takes an array, arr, and two indices, i and j. It swaps the elements at the i and j indices.

Conclusion

In this article, we have seen how to implement a Parallel Quick Sort algorithm in C#. We have used the Parallel.Invoke method to sort the subarrays in