###
**What is Quick Sort algorithm? How to implement Quick Sort in C++?**

- Quick Sort is a sorting algorithm. It is also referred as partition exchange sort.
- In the best/ average case it gives a time complexity of O(nlogn) and worst case time complexity of O(n*n).
- Can be implemented as in-place sorting without need for additional space.
- Quick Sorting involves these steps:
- Pick a pivot element from the input list.
- Perform an input partition operation based on the pivot. Move all elements less than pivot before the pivot element in the list. Move all elements greater than the pivot after the pivot element in the list.
- Recursively sort the left and right sub-lists of the pivot.

###
A simple demonstration of quick sort

```
#include <iostream>
using namespace std;
const int INPUT_SIZE = 10;
// A simple print function
void print(int *input)
{
for ( int i = 0; i < INPUT_SIZE; i++ )
cout << input[i] << " ";
cout << endl;
}
// The partition function
int partition(int* input, int p, int r)
{
int pivot = input[r];
while ( p < r )
{
while ( input[p] < pivot )
p++;
while ( input[r] > pivot )
r--;
if ( input[p] == input[r] )
p++;
else if ( p < r )
{
int tmp = input[p];
input[p] = input[r];
input[r] = tmp;
}
}
return r;
}
// The quicksort recursive function
void quicksort(int* input, int p, int r)
{
if ( p < r )
{
int j = partition(input, p, r);
quicksort(input, p, j-1);
quicksort(input, j+1, r);
}
}
int main()
{
int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
cout << "Input: ";
print(input);
quicksort(input, 0, 9);
cout << "Output: ";
print(input);
return 0;
}
```

OUTPUT:-

```
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000
```

This comment has been removed by the author.

ReplyDeleteCheck out this version of QuickSort Algorithm :)

ReplyDeleteQuick Sort Program in C

Check it out Quick sort in C

ReplyDeletehttp://allprogramsinc.blogspot.com/2013/02/quick-sort-algorithm-program-in-c.html

Checkout other sorting programs here.....

ReplyDeleteHeap Sort in C

Bubble Sort in C

Insertion Sort in C

Selection Sort in C

Quick Sort in C

great example, thanks

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteGreat website!

ReplyDeleteA small query on this article:

Should the pivot be equated to input[r]? Then, will the stmt

"while ( input[r] > pivot) " ever be executed?

I noticed that too, Looks like condition should be ((input[r] >= pivot) && (r > p))

DeleteWow ! look at the code. Beautiful amazing its help for me

ReplyDeletethank you. this really helps me.

ReplyDeletecool :D

ReplyDeleteNICE way of coding....

ReplyDeleteIf you implemented this way then you will never have to use quicksort to the right because j+1 will always be at the pivot.

ReplyDeleteThis comment has been removed by the author.

ReplyDelete