# Quick Sort in C

## How Quick Sort works in C

Quick sort is an algorithm of the divide and conquer type. That is,the problem of sorting a set is reduced of the problem of sorting two smaller sets. ## How it works?

Quick sort works in the following way –

• Choose an item from array called as pivot
• Move all the elements smaller than pivot to left partition
• Move all the elements greater than pivot to right partition.

Choose new pivot item in each partition and keep doing the same process again until partition of one element each aren’t formed.

### How to choose Pivot?

These are the following ways you can choose pivot –

• First element as pivot.
• Last element as pivot (We use this in our examples & Code)
• Random element as pivot.
• Median element as pivot. ## Execution of quick sort

Quick sort works recursively, Partitioning moves all smaller elements to left of pivot and greater to right side of pivot, thus each time two sub array partitions are formed. Thus again, we do partitioning in each of these sub arrays individually.

Following code below gives perfect example for this –

### QuickSort Algorithm

```quickSort(arr[], low, high)
{
if (low < high)
{
/* indexPI is partitioning index, partition() function will         return index of partition */
indexPI = partition(arr, low, high);

quickSort(arr, low, indexPI - 1);  // left partition
quickSort(arr, indexPI + 1, high); // right partition
}
}```

### Partition Algorithm

```partition (arr[], low, high)
{
// pivot element selected as right most element in array each time
pivot = arr[high];

swapIndex = (low - 1)  //swapping index

for (j = low; j <= high- 1; j++)
{
// Check if current element is smaller than pivot element
if (arr[j] < pivot)
{
i++;    // increment swapping index
swap arr[j] and arr[swapIndex]
}
}
swap arr[swapIndex + 1] and arr[high])
return (swapIndex + 1)
}```  ### Code of Quick Sort in C

`#include<stdio.h>   // A utility function to swap two elements void swap(int* x, int* y) {     int temp = *x;     *x = *y;     *y = temp; }   /* Partition function to do Partitionelements on the left side of pivot elements would be smaller than pivotelements on the right side of pivot would be greater than the pivot*/int partition (int array[], int low, int high) {     // pivot element selected as right most element in array each time    int pivot = array[high];        int swapIndex  = (low - 1);   //swapping index      for (int j = low; j <= high- 1; j++)     {         // Check if current element is smaller than pivot element        if (array[j] < pivot)         {             swapIndex ++;    // increment swapping index            swap(&array[swapIndex], &array[j]);         }     }     swap(&array[swapIndex + 1], &array[high]);     return (swapIndex + 1); }   //Recursive function to apply quickSortvoid quickSort(int array[], int low, int high) {     if (low < high)     {        /* indexPI is partitioning index, partition() function will         return index of partition */        int indexPI  = partition(array, low, high);           quickSort(array, low, indexPI  - 1);  // left partition        quickSort(array, indexPI  + 1, high); // right partition    } }   /* Function to display the array */void display(int array[], int size) {     int i;     for (i=0; i < size; i++)         printf("%d ", array[i]); }   //Main function to run the programint main() {     int array[] = {70, 90, 10, 30, 50, 20, 60};     int size = sizeof(array)/sizeof(array);     quickSort(array, 0, size-1);     printf("Array after Quick Sorting: ");     display(array, size);     return 0; } `

#### Output

`Array after Quick Sorting: 10 20 30 50 60 70 90 `  