# Write a program to implement quick sort algorithm.

We have given an integer array,we have to sort an array using quick sort algorithm

Example:

``````input:arr[]={1,5,3,2}
output:1,2,3,5``````

Logic:

``````Step 1- pick a pivot.
step 2-element smaller than pivot put them on the left side.
step 3-element greater than pivot put them on right side.
step 4-divide the subpart again and partition them into left and right.
step 5-finally array is sorted.``````

Code-

```#include <iostream>
using namespace std;
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] <= pivot)
{
i++;
swap(&array[i], &array[j]);
}
}

swap(&array[i + 1], &array[high]);
return (i + 1);
}

void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
int main() {
int array[] = {1, 2,3,4,5};
int n = sizeof(array) / sizeof(array[0]);
quickSort(array, 0, n - 1);
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
cout<<endl;

}```

Output:

`1 2 3 4 5`

Time complexity:0(N*N)

Space Complexity:O(1)

Scroll to Top