Quicksort

Given an array of numbers aim is to sort them ascending/descending order using quick sort algorithm.

Quick Sort is the most famous and one of my favorite search algorithm which is used in millions of software applications and systems. C++ programmings default std::sort() uses the quick sorting technique to sort the input. Quicksort algorithm technique is very simple. Initially it takes some element in the array as pivot element. Then the rest of the elements been compared with the pivot element and whatever the elements lesser than the pivot element is moved to the first part. By doing this we can divide the array into two parts based on the chosen pivot element. All left side array elements are lesser than pivot element remaining elements are on the right side. Do the same process for the left and right parts of the array recursively.

Let’s take an example and walk it through with step by step illustration below.

Example:
Input = {12, 8, -7, 10, 4, 2, 9}
Output = {-7, 2, 4, 8, 9, 10, 12}
Above output is in ascending sorted order.

Steps

128-710429

Here pivot is 9, 12 !< 9 so ignore as it is

128-710429

left-index: 0, iter-index: 0

128-710429

Here pivot is 9, 8 < 9 so swap it with left-index element and increment left-index by 1.

812-710429

left-index: 1, iter-index: 1

812-710429

Here pivot is 9, -7 < 9 so swap it with left-index element and increment left-index by 1.

8-71210429

left-index: 2, iter-index: 2

8-71210429

Here pivot is 9, 10 !< 9 so ignore it as it is.

8-71210429

left-index: 2, iter-index: 3

8-71210429

Here pivot is 9, 4 < 9 so swap it with element in left-index and increment left-index by 1.

8-74101229

left-index: 3, iter-index: 4

8-74101229

Here pivot is 9, 2 < 9 so swap it with element in left-index and increment left-index by 1.

8-74212109

left-index: 4, iter-index: 4

8-74212109

Finally swap the pivot element with element in left-index and divide array based on this index.

8-74291012

left-index: 4, iter-index: 4

Now divide the array into two halves based on the index values. And do the same process for each array until every array has only 2 elements in it. Let’s jump into code to quicksort.

“C” Code

#include <iostream>

using namespace std;

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void printArray(int inp[], int len)
{
	for(int i=0; i<len; i++)
		cout<<inp[i]<<" ";
	cout<<endl;
}

int quickSortUtil(int inp[], int start, int end)
{
	int pivot = end - 1;
	int left = start - 1;

	for(int i=start; i<end-1; i++)
	{
		if(inp[i] < inp[pivot])
		{
			left++;
			swap(inp[left], inp[i]);
		}
	}
	swap(inp[left+1], inp[pivot]);
	return left+1;
}

void quickSort(int inp[], int start, int end)
{
	if(start < end)
	{
		int pivot = quickSortUtil(inp, start, end);
		quickSort(inp, start, pivot);
		quickSort(inp, pivot+1, end);
	}
}

int main(int argc, char* argv[])
{
	int inp[] = {12, 8, -7, 10, 4, 2, 9};
	int len = sizeof(inp) / sizeof(inp[0]);

	cout<<"Input Array: "<<endl;	
	printArray(inp, len);

	quickSort(inp, 0, len);
	cout<<"Sorted Array: "<<endl;
	printArray(inp, len);

	return 0;
}
Output:
Input Array: 
12 8 -7 10 4 2 9 
Sorted Array: 
-7 2 4 8 9 10 12

Complexity: O(n*log(n))Space: O(1)

This is it for the QuickSort algorithm, if you find any errors in algorithm or code, please let readers know it by commenting below, Cheer!.

Advertisements