Quick Sort is also based on the concept of Divide and Conquer, just like merge sort. But in quick sort all the heavy lifting(major work) is done while dividing the array into subarrays, while in case of merge sort, all the real work happens during merging the subarrays. In case of quick sort, the combining step does absolutely nothing.
It is also called partition-exchange sort. This algorithm divides the list into three main parts:
1. Elements less than the Pivot element
2. Pivot element(Central element)
3. Elements greater than the pivot element
Pivot element can be any element from the array, it can be the first element, the last element or any random element. In this tutorial, we will take the rightmost element or the last element as a pivot.
How Quick Sort work
Following is the unsorted array
7
|
2
|
1
|
6
|
8
|
5
|
3
|
4
|
In quick sort what we do is that 1st we select an element from the list, lets we take an element as 4 and we call this select number as Pivot 4.
7
|
2
|
1
|
6
|
8
|
5
|
3
|
4
|
Now we Re-arrange the list in such a way that all the element lesser than pivot are in left side and higher element in right side so the list will be like following
2
|
1
|
3
|
4
|
8
|
5
|
7
|
6
|
Now break this problem in the segment like following
2
|
1
|
3
|
8
|
5
|
7
|
6
|
For two new segment pivot will be as 3 and 6 and will break 1st segment as following
2
|
1
|
3
|
Now we Re-arrange the list in such a way that all the element lesser than pivot 3 are in left side and higher element in right side so, in this case, there will be one segment because they're not an element is greater than 3 and select another pivot from a new segment
And new pivot is 1
2
|
1
|
1
|
2
|
Same we will do for the Right segment Split earlier with Pivot 4
C# program
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace sortQuickAlgorithm
{
class quickSortAlgorithm
{
private int[] array = new int[20];
private int len;
public void QuickSortAlgorithm()
{
sort(0, len - 1);
}
public void sort(int left, int right)
{
int pivot, leftend, rightend;
leftend = left;
rightend = right;
pivot = array[left];
while (left < right) { while ((array[right] >= pivot) && (left < right))
{
right--;
}
if (left != right)
{
array[left] = array[right];
left++;
}
while ((array[left] >= pivot) && (left < right))
{
left++;
}
if (left != right)
{
array[right] = array[left];
right--;
}
}
array[left] = pivot;
pivot = left;
left = leftend;
right = rightend;
if (left < pivot) { sort(left, pivot - 1); } if (right > pivot)
{
sort(pivot + 1, right);
}
}
public static void Main()
{
quickSortAlgorithm q_Sort = new quickSortAlgorithm();
int[] array = { 7,2,1,6,8,5,3,4};
q_Sort.array = array;
q_Sort.len = q_Sort.array.Length;
q_Sort.QuickSortAlgorithm();
for (int j = 0; j < q_Sort.len; j++)
{
Console.WriteLine(q_Sort.array[j]);
}
Console.ReadKey();
}
}
}
|
Using Recursion:
class Program
{
static public int Partition(int[] numbers, int left, int right)
{
int pivot = numbers[left];
while (true)
{
while (numbers[left] < pivot)
left++;
while (numbers[right] > pivot)
right--;
if (left < right)
{
int temp = numbers[right];
numbers[right] = numbers[left];
numbers[left] = temp;
}
else
{
return right;
}
}
}
static public void QuickSort_Recursive(int[] arr, int left, int right)
{
// For Recusrion
if (left < right)
{
int pivot = Partition(arr, left, right);
if (pivot > 1)
QuickSort_Recursive(arr, left, pivot - 1);
if (pivot + 1 < right)
QuickSort_Recursive(arr, pivot + 1, right);
}
}
static void Main(string[] args)
{
int[] numbers = { 7,2,1,6,8,5,3,4};
int len = numbers.Length;
Console.WriteLine("QuickSort By Recursive Method");
QuickSort_Recursive(numbers, 0, len - 1);
for (int i = 0; i < len; i++)
Console.WriteLine(numbers[i]);
Console.WriteLine();
}
}
|
Complexity Analysis of Quick Sort
For an array, in which partitioning leads to unbalanced subarrays, to an extent where on the left side there are no elements, with all the elements greater than the pivot, hence on the right side.
And if keep on getting unbalanced subarrays, then the running time is the worst case, which is O(n2)
Whereas if partitioning leads to almost equal subarrays, then the running time is the best, with time complexity as O(n*log n).
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n*log n)
Average Time Complexity [Big-theta]: O(n*log n)
Space Complexity: O(n*log n)
As we know now, that if subarrays partitioning produced after partitioning are unbalanced, quick sort will take more time to finish. If someone knows that you pick the last index as pivot all the time, they can intentionally provide you with an array which will result in worst-case running time for quicksort.
To avoid this, you can pick random pivot element too. It won't make any difference in the algorithm, as all you need to do is, pick a random element from the array, swap it with the element at the last index, make it the pivot and carry on with quick sort.
- Space required by quick sort is very less, only O(n*log n) additional space is required.
- Quick sort is not a stable sorting technique so it might change the occurence of two similar elements in the list while sorting.
EmoticonEmoticon