# Programming Videos

## Search

### Quicksort Program in C, C++

Write a program to implement QuickSort algorithm in C,C++. Quicksort algorithm is mostly asked in interviews. To implement this algorithm efficiently, you need a good understanding of recursion.

Time complexity of sorting algorithms

QuickSort

QuickSort is a divide and conquer algorithm.  It divides large array into smaller sub-arrays and then recursively sort the smaller sub-arrays.

Quicksort algorithm is efficient than other sorting algorithm such as bubble sortinsertion sortselection sort etc.

QuickSort Time Complexity -

Average Case  - O(nlogn)

Best Case - O(nlogn)

Worst Case - O(n2)

## QuickSort Program in C

```#include <stdio.h>

void quick(int arr[],int low,int high){

int pivloc;

if(low >= high) {

return;

}

pivloc = partition(arr,low,high);

quick(arr,low,pivloc-1);
quick(arr,pivloc+1,high);

}

int partition(int arr[],int low,int high){

int i,j,temp,pivot;

i = low +1;
j = high;

pivot = arr[low];

while(i<=j){

while((arr[i]<pivot) && (i<high)){

i++;

}

while(arr[j]>pivot){

j--;
}

if(i<j){

temp = arr[i];
arr[i] = arr[j];
arr[j]=temp;

i++;
j--;

} else {

i++;
}

}

arr[low] = arr[j];
arr[j] = pivot;

return j;

}

int main(){

int k;

int arr[]={6,8,2,5,7,3};

quick(arr,0,5);

for(k=0;k<6;k++){

printf("%d ",arr[k]);

}

return 0;
}

```