Quick Sort Algorithm In C#

Introduction

In this article, I am going to explain about the Quicksort algorithm.This is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.

This algorithm is very common in job interviews.So first, I am going to explain Quick Sort algorithm; then, I will be providing the C# code to execute it.

The Quicksort Algorithm

This Algorithm selects an element as pivot element from the given array and partitions the array around it such that, Left side of pivot contains all the elements that are less than the pivot element. The right side contains all elements that are greater than the pivot element. Let P be the index of pivot after partitioning the array. Then, the left subarray(start to P-1) and right subarray(P+1 to end) are sorted recursively to get the final sorted array as output.

Different versions of Quicksort pick pivot in different ways such as.

1. Always pick the first element as a pivot.
2. Always pick the last element as pivot
3. Pick a random element as pivot.
4. Pick median as pivot.

Selecting a pivot element reduces the space complexity and removes the use of the auxiliary array that is used in merge sort. Selecting a random pivot in an array results in an improved time complexity in most of the cases.

How the array is partitioned around pivot?

1. Assume the last element as pivot .
2. We want larger elements to go to the right and smaller to go to left. We maintain two indexes i and j, whereas i pointing to the leftmost element and j is pointing to last element(pivot).
3. While i is to the left of j, we move i right, skipping all the elements less than the pivot. If an element is found greater than the pivot, i stops
4. While j is to the right of i, we move j left, skipping all the elements greater than the pivot. If an element is found less than the pivot, j stops
5. When both i and j have stopped, the elements are swapped.
6. When i and j have crossed, no swap is performed, scanning stops, and the element pointed to by i is swapped with the pivot.

Let us understand this with the help of an example.

Let us take input array as – 9 7 5 3 10 6

The sorted output for this array is – 3 5 6 7 9 10

Step 1

Select the last element (6) as pivot element and partition the array around 6.

Step 2

After partitioning, we get the following.

Step 3

Now, we will recursively sort the left subarray (5 3).Which gives –

Step 4

Since the left subarray is now sorted, we will recursively sort the right subarray (7 10 9). The last element of right subarray (9) is selected as pivot and right subarray is partitioned around it. Which gives

Step 5

Since the left side of Pivot element(9) has only one element i.e (7) hence it is sorted. Similarly, the right side of pivot has only one element i.e (10) hence that is also sorted.

Hence, we get our sorted array using Quicksort as follows –

Time Complexity