Quick Sort Program in Cpp

Quicksort is a divide and conquer algorithm.

This Sorting algorithm that picks an element (“the pivot”) and reorders the array forming two partitions such that all elements less than the pivot come before it and all elements greater come after. The algorithm is then applied recursively to the partitions until the list is sorted.

Algorithm Steps

1. Pick an element from the array, this element is called as pivot element.
2. Divide the unsorted array of elements in two arrays with values less than the pivot come in the first sub array.
3. while all elements with values greater than the pivot come in the second sub-array (equal values can go either way).
4. This step is called the partition operation.
5. Recursively repeat the step 2(until the sub-arrays are sorted) to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Algorithm
partition(Array, low, high) is
pivot = A[high]
i = low
for j = low to high – 1 do
if A[j] ≤ pivot then
swap A[i] with A[j]
i = i + 1
swap A[i] with A[high]
return i

Program

//Quick Sort
#include<iostream.h>
#include<conio.h>
// Display For Array
void display(int number[],int size){
for(int i=0;i<size;i++){
cout<<" "<<number[i];
(size==i+1)? cout<<".": cout<<",";
}
}
//Swap Function
void swap(int array[],int left,int right) {
int temp = array[right];
array[right] = array[left];
array[left] = temp;
}
//Quick Sort Function
void quicksort(int array[],int left,int right) {
if(left < right) {
int boundary = left;
for (int i = left + 1; i < right; i++) {
if (array[i] < array[left]) {
swap(array, i, ++boundary);
}
}
swap(array,left,boundary);
quicksort(array, left, boundary);
quicksort(array, boundary + 1, right);
}
}

void main(){
clrscr();
int size = 8;
int array[10];
array[0] = 34;
array[1] = 304;
array[2] = 302;
array[3] = 745;
array[4] = 91;
array[5] = 5;
array[6] = 704;
array[7] = 200;
cout<<"\n ------Quick Sort------";
cout<<"\n Before Sorting \n";
display(array,size);
cout<<"\n After Sorting \n";
//Quick Sort
quicksort(array,0,size);
display(array,size);
getch();
}

Output

Live Demo