Quick Sort In C++ With Example

Quick Sort Algorithm

Quick sort is invented by C.A.R Hoare and its very useful sorting algorithm. This algorithm has two parts 1st is partition part and 2nd is sorting part. In the first part most of the work is done where it divide the work and the 2nd part simple sort the problems.

It use divide and conquer to get the result same like the marge sort without using extra storage. In the quick sort we have to select a value, which is called pivot value. There are different ways to select the pivot value(first value, last, middle, it has no criteria ), here I will select the first value in the list and it is also called the split point. After selecting pivot value we will select two value leftmark and rightmark from start and end of the remaining elements. The role of the partition is to move the element those are out of order. 

From the leftmark we will locate a value which is greater then the pivot value and on the other hand from the rightmark we decrements until we find a value which is less then pivot value. Pivot value is 54, leftmark is 26 and rightmark is 20 so leftmark is not greater then pivot value so we will move to next element of the list and rightmark is less then the pivot value so it will not move. Now left mark is on 93 and rightmark is on 20, both elements are out of order so we will swap them and repeat the process. When rightmark is less then leftmark we will stop and replace rightmark with pivot.

Now we have small number on the left and greater number on the right side of the pivot value. The list can be divided and the quick sort invoked on the both half. 

C++ Code Of Quick Sort With Out Put

#include<iostream.h>

void quickSort (int *arr, int left, int right);

void print (int *arr);

void main ()

{

int arr[10];

cout<<"Enter Ten Unsorted Numbers";

for(int i=0;i<=9;i++)

{

cout<<"Enter Number "<<i+1<<":";

cin>>arr[i];

}

int left=0; // left is the start of the array

int right=9; // right is the end of the array 

quickSort(arr,left,right);

//After Sorting

print(arr);

}

void quickSort (int *arr, int left, int right)

{

int leftmark=left, rightmark=right, temp;

// selecting pivot 

int pivot=arr[0];

// Partition 

while(leftmark<=rightmark)

{

while(leftmark<pivot)

leftmark++;

while(rightmark>pivot)

rightmark--;

if(leftmark<=rightmark)

{

temp=arr[leftmark];

arr[leftmark]=arr[rightmark];

arr[rightmark]=temp;

leftmark++;

rightmark--;

}

};

if(left<rightmark)

quickSort(arr, left, rightmark);

if(leftmark<right)

quickSort(arr,leftmark,right);

}

void print (int *arr)

{

for ( int i = 0; i < 10; i++ )

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

   cout << endl;

}