Another versatile and widely used algorithm that uses the Divide and Conquer strategy like Merge Sort is known as Quick Sort. It breaks down a larger array into smaller, more manageable sub-arrays and sorts them recursively. Practically, it is highly efficient and is used in numerous software applications to quickly sort the data in ascending or descending orders, especially for large datasets.
In this article, we will learn about the Quick Sort algorithm and implement it in C# using recursion.
Quick Sort: Divide and Conquer Strategy
The main idea behind the divide and conquer rule is to divide a major problem into multiple smaller problems unless they become small enough to be resolved directly. The individual solutions to all the subproblems are then combined together to form a bigger solution. The Quick sort algorithm implements the divide and conquer rule as follows:
1. Divide (Partitioning): In this phase, the algorithm selects a pivot element and divides the remaining collection into 2 equal halves, one containing the elements lesser than the pivot element and the other containing the elements higher than the pivot element. The elements that are equal to the pivot element can go in any sub-array.
3. Combine: The sorted sub-arrays are then combined to form the final sorted array.
Demonstration
The Quick Sort algorithm partitions the collection and finds a pivot element. The pivot element significantly impacts the algorithm performance. Once the pivot element has been chosen, all the elements lesser than the pivot element are arranged on the left side, and the elements greater than the pivot element are arranged on the right side. The pivot element automatically ends up in its final sorted position.
Let's try to sort an unsorted array using the Quick Sort algorithm and understand its functionality more:
Consider we have an array [6, 3, 7, 1, 8, 2, 9, 0]. Now, the quick sort first picks a pivot, say 6 at index 0. Once the pivot has been picked, the elements less than 6 are moved to its left, and higher than that are moved to its right. So, we get [3, 1, 2, 0], 6, [7, 8, 9]. Although it is not fully sorted, but 6 is at its correct position. Now, let's take the left sub array, i.e. [3, 1, 2, 0]. Pick a pivot, say 3. Move smaller elements to the left and bigger ones to the right. We get [1, 2, 0], 3. Again, pick the left subarray, i.e., [1, 2, 0]. Pick a pivot, i.e., 1, and move the smaller elements to the left and the bigger ones to the right. We get, [0], 1, [2]. By combining the left sub-arrays, we get [0, 1, 2, 3], 6, [7, 8, 9].
The algorithm also repeats the above steps for the right sub-array unless the final sorted array is not formed.
Implementing Quick Sort in C#
Hopefully, you will understand how quick sorting works practically. Now, let's implement it programmatically and see how it works:
using System;
using System.Collections.Generic;
class Sorting {
public static void QuickSort(int[] numbers, int low, int high) //takes the collection, low index and high index
{
if (low < high)
{
int pivotElement = Partition(numbers, low, high); //partitioning the array into sub arrays
// Recursively sort the sub-arrays
QuickSort(numbers, low, pivotElement - 1); //sorting arrays in left and right side of the pivot
QuickSort(numbers, pivotElement + 1, high);
}
}
private static int Partition(int[] numbers, int low, int high) //divides the array into partitions
{
int pivot = numbers[high]; //Selectig the last element as pivot
int i = (low - 1); // Getting the index of the smaller element
for (int j = low; j < high; j++) //iterating through the array
{
if (numbers[j] <= pivot)//if the current element is smaller than or equal to the pivot element
{
i++; //the smaller element is shifted to the left
int temp = numbers[i]; //swapping the positions of the elements
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
int temp2 = numbers[i + 1]; //swapping i+1 and pivoting
numbers[i + 1] = numbers[high];
numbers[high] = temp2;
return (i + 1);
}
static void Main() {
int[] nums = {2, 4, 1, 6, 5, 7};
QuickSort(nums, 0, nums.Length-1);
for(int i=0; i<nums.Length; i++)
{
Console.Write(nums[i] + " ");
}
}
}
Pivot Selection Strategies
The selection of the pivot significantly impacts the algorithm's performance. There are various strategies that are considered while choosing a pivot, such as,
1. Selecting the First Element: It is a simple approach but leads to poor performance for presorted or reverse-sorted collections.
2. Selecting the Last Element: This is similar to choosing the first element and leads to the same results.
3. Selecting a Random Element: Provides better performance while avoiding the worst-case scenarios for reverse-sorted or presorted arrays.
4. Selecting a Median of Three: Choosing the median of the first, last, and middle elements as the pivot gives the most optimal results.
Advantages of Quick Sort Algorithm
The Quick Sort algorithm is often preferred over other similar algorithms due to various factors, such as:
- It performs the partitioning in place, reducing the need for extra memory.
- It has a good cache locality since the elements are accessed in a relatively localized manner during the partitioning process.
Although the Merge Sort provides stability, the Quick Sort offers better average-case performance and in-place sorting. This makes it a better choice for many standard library implementations.
