Quick sort is a divide & conquer algorithm and is one of the most efficient sorting algorithms it is performed by splitting an array into small arrays. Quick sort is the fastest internal sorting algorithm it is faster than any common sorting algorithms having time complexity O (n log n)

**Quick sort works in the following manner:**

- Choose an element from the array, that element is called a pivot element.
- Break the unsorted array of elements in two arrays including values smaller than the pivot appears in the first sub array, while all elements with values greater than the pivot appear in the second sub-array (same values can go either approach). This step is called the partition operation.
- Recursively repeat step 2 (until the sub-arrays are sorted) to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values. This same logic we have performed in the following C program. but before that we have a blueprint (Pseudocode) of the program so you understand it easily

#### Pseudocode of Quick Sort Algorithm:

```
/* low --> Starting point or index, high --> Ending point or index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning point or index, arr[pi] is now
at right place in the array */
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
```

#### Actual Program For Quick Sort In C

#include<stdio.h> // to swap two numbers void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition_function (int arr[], int low, int high) { int pivot = arr[high]; // selecting last element as pivot int i = (low - 1); // index of smaller element for (int j = low; j<= high- 1; j++) { // If the current element is smaller than or equal to pivot if (arr[j] <= pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } /* a[] is the array, p is starting point or index, which is 0, and r is the last point or index of array. */ void quicksort_algorithm(int a[], int p, int r) { if(p < r) { int q; q = partition_function(a, p, r); quicksort_algorithm(a, p, q-1); quicksort_algorithm(a, q+1, r); } } // function to print the array void printArray(int a[], int size) { int i; for (i=0; i < size; i++) { printf("%d ", a[i]); } printf("n"); } int main() { int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}; int n = sizeof(arr)/sizeof(arr[0]); // call quickSort Algorithm function quicksort_algorithm(arr, 0, n-1); printf("Sorted array: n"); printArray(arr, n); return 0; }

**Output**

Sorted array:

2 3 5 6 7 9 10 11 12 14

If you like this post, don’t forget to share 🙂

## No Comments

Leave a comment Cancel