# C++ Example – Quick Sort Algorithm

Basic Idea

• Pick one element in the array, which will be the pivot.
• Make one pass through the array, called a partition step, re-arranging the entries so that:
• entries smaller than the pivot are to the left of the pivot.
• entries larger than the pivot are to the right
• Recursively apply quicksort to the part of the array that is to the left of the pivot, and to the part on its right.
• No merge step, at the end all the elements are in the proper order

In this lesson we will learn how to write a source code in C++ programming language for doing simple quick sort using array in ascending order.

Quick Sort Example :

```/**
Quick Sort Algorithm C++ Example by Codebind.com
*/
#include <iostream>

void PrintArray(int *array, int n) {
for (int i = 0; i < n; ++i)
std::cout << array[i] << " " << std::flush;
std::cout << std::endl;
}

inline void Swap(int &a, int &b){
int k = a;
a = b;
b = k;
}

//reload rand to produce random number in a fixed range
inline int rand(int p, int q){
int size = q - p + 1;
//    srand(time(NULL));
return (p + rand() % size);
}
int Partition(int arr[], int lo, int hi){
//produce ramdom subscript
int t = rand(lo, hi);
Swap(arr[t], arr[hi]);

int index = lo - 1;
int key = arr[hi];
for(int i = lo ; i < hi; i++){
if(arr[i] <= key)
Swap(arr[++index], arr[i]);
}
Swap(arr[++index], arr[hi]);
return index;
}
void QuickSortHelper(int arr[], int lo, int hi){
if(lo < hi){
int index = Partition(arr, lo, hi);
QuickSortHelper(arr, lo, index-1);
QuickSortHelper(arr, index+1, hi);
}
}

void QuickSort(int arr[], int arr_size){
QuickSortHelper(arr, 0, arr_size-1);
}

int main() {
int array[] = {94, 42, 50, 95, 333, 65, 54, 456, 1, 1234};
int n = sizeof(array)/sizeof(array[0]);

std::cout << "Before Quick Sort :" << std::endl;
PrintArray(array, n);

QuickSort(array, n);

std::cout << "After Quick Sort :" << std::endl;
PrintArray(array, n);
return (0);
}

/*
OUTPUT
Before Quick Sort :
94 42 50 95 333 65 54 456 1 2325
After Quick Sort :
1 42 50 54 65 94 95 333 456 2325
*/
```