Thursday, 2 November 2017

Quick sort algorithm using C++ language

It is an algorithm which is further depend on divide and conquer. It is an algorithm design paradigm based on multi-branched recursion.
   
Program Code of Quick sort algorithm:

//header files required for program implementation

#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

No comments:

Post a Comment

Thanks
Mukesh Rajput