# Quick Sort

Sorting Algorithm

Share

In this tutorial we will learn about Quick sort algorithm.

This sorting algorithm uses the idea of divide and conquer. It finds the element called pivot which divides the array into two halves in such a way that elements in the left half are smaller than pivot and elements in the right half are greater than pivot.

• Find pivot that divides the array into two halves.
• Quick sort the left half.
• Quick sort the right half.

## Algorithm

``````/**
* a[0:n-1] is an array of n elements.
* beg = first index of array
* end = last index of array
*/
QuickSort(a, beg, end)
Begin
if beg < end then
Call PartitionArray(a, beg, end, pivotLoc);    //this will find pivot location
Call QuickSort(a, beg, pivotLoc - 1 );   //Quick sort left sub array
Call QuickSort(a, pivotLoc + 1, end);    //Quick sort right sub array
endif
End
``````

## Code in C

``````#include <stdio.h>
#define SIZE 6  //array size

void partitionArray(int *a, int beg, int end, int *pivotLoc);
void quickSort(int *a, int beg, int end);

int main(){
int a[SIZE] = {5,2,6,1,3,4};  //unsorted array
int i;

quickSort(a, 0, SIZE-1);  //beg = 0 start index of array end = 5 last index of array

//printing sorted element of array
for(i = 0; i < SIZE; i++){
printf("%d\t", a[i]);
}
return 0;
}//main() ends here

void quickSort(int *a, int beg, int end){
int pivotLoc;
if(beg < end){
partitionArray(a, beg, end, &pivotLoc);  //this will find the pivot location and partition the array
quickSort(a, beg, pivotLoc - 1);  //quick sort the left sub array
quickSort(a, pivotLoc + 1, end);  //quick sort the right sub array
}
}//quickSort() ends here

void partitionArray(int *a, int beg, int end, int *pivotLoc){
int left = beg;    //initially left point to the first element of the array
int right = end;  //initially right point to the last element of the array
*pivotLoc = left;  //initially pivot point to first element of the array
int tmp;  //used for swapping values

while(1){

//pivot pointing at left
while(a[*pivotLoc] <= a[right] && *pivotLoc != right){  //pivot element <= right element
right--;  //move right one position towards left
}

if(*pivotLoc == right){  //both left and right pointing at same element of the array
break;
}else if(a[*pivotLoc] > a[right]){
//pivot element greater than right element. swap pivot and right element.
tmp = a[right];
a[right] = a[*pivotLoc];
a[*pivotLoc] = tmp;
*pivotLoc = right;  //pivot is now pointing to right
}

//pivot pointing to right
while(a[*pivotLoc] >= a[left] && *pivotLoc != left){  //pivot element >= left element
left++;    //move left one position towards right
}

if(*pivotLoc == left){  //both left and right pointing at the same element of the array
break;
}else if(a[*pivotLoc] < a[left]){
//pivot element smaller than left element. swap pivot and left element.
tmp = a[left];
a[left] = a[*pivotLoc];
a[*pivotLoc] = tmp;
*pivotLoc = left;  //pivot is now pointing to left
}
}
}//partitionArray() ends here
``````

## Time Complexity

For an array of n elements order of Quick Sort is O(nlog2n)

Share