Quicksort algorithm

Implementation of Quicksort algorithm using C++ language

It is an algorithm which further depends on divide and conquers. It is an algorithm design paradigm based on multi-branched recursion.

   

Program Code:

#include<iostream>

using namespace std;

// function declaration which is used to swap two numbers

void swap(int* a, int* b)

{

int t = *a;

*a = *b;

*b = t;

}

// function declaration which is used to partition given array according to selected pivot element

int partition (int arr[], int low, int high)

{

int pivot = arr[high]; 

int i = (low - 1);

for (int j = low; j <= high- 1; j++)

{

if (arr[j] <= pivot)

{

 i++;   

swap(&arr[i], &arr[j]);

}

}

swap(&arr[i + 1], &arr[high]);

return (i + 1);

}

// function declaration which recursively call quicksort function untill low<high

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}

// function declaration which is used to display the element of the given array

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

cout<<arr[i]<<"\t";

cout<<endl;

}

// main() function declaration with different function call

int main()

{

int arr[] = {2,8,9,13,6,5,4};

int n = sizeof(arr)/sizeof(arr[0]);

cout<<"Array entered by the user for sorting :";

cout<<endl;

printArray(arr, n);

quickSort(arr, 0, n-1);

cout<<"After apply Quciksort algorithm on entered array :";

cout<<endl;

printArray(arr, n);

return 0;

}

The program output is tested on www.jdoodle.com

Output:

Array entered by the user for sorting :

2 8 9 13 6 5 4

After apply Quciksort algorithm on entered array :

2 4 5 6 8 9 13

Thanks

Mukesh Rajput