# Quick Sort

Quick sort is a divide and conquer based algorithm like merge sort. I provide my implementation of quick sort which is implemented recursively.

```#include <iostream>
#include <cstring>

using namespace std;

void display(int* arr, size_t size)
{
for (int i = 0; i < size; ++i) {
cout << arr[i] << endl;
}
}

int partition(int pivot, int* arr, size_t size, int left, int right)
{
int pivotIndex = left;
left++;

while (left < right) {
while(pivot > arr[left] && left < size)
left++;

while(pivot < arr[right] && right > 0)
right--;

if (left >= right)
break;

swap(arr[left], arr[right]);
}

swap(arr[pivotIndex], arr[right]);

return right;
}

void quick_sort(int* arr, size_t size, int left, int right)
{
if (right-left <= 0)
return;

int pivot = arr[left];

int newPivotIndex = partition(pivot, arr, size, left, right);

quick_sort(arr, size, left, newPivotIndex-1);
quick_sort(arr, size, newPivotIndex+1, right);
}

int main() {
int A[] = {20,10,30,50,100,60,40,90,80,70};

display(A, 10);

cout << endl;

quick_sort(A, 10, 0, 9);

display(A, 10);

return 0;
}```