# Quick Sort in C Language

**Quick Sort** is a* popular divide-and-conquer sorting algorithm* that uses recursion to sort an array by partitioning it into smaller sub-arrays. In C language, an implementation of the **Quick Sort algorithm** can be as follows:

```
#include <stdio.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If 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);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```

The

function swaps two integer values passed as pointers.**swap**

The

function takes an integer array **partition**

, and two integer values **arr**

and **low**

, which are the indexes of the subarray to be sorted. It selects the last element in the subarray as the pivot and partitions the array into two parts such that elements smaller than or equal to the pivot come before it, and elements larger than the pivot come after it. It returns the index of the pivot element after partitioning.**high**

The `quickSort`

function recursively sorts the array by calling

and then calling itself on the two resulting subarrays until the whole array is sorted.**partition**

The

function creates an integer array and calls the **main**

function to sort it. Finally, it prints the sorted array to the console.**quick Sort**

Note that the *worst-case time complexity of quick sort is O(n^2)*, but its average and

*best-case complexity is*, making it a very efficient algorithm for sorting large arrays.

**O(n log n)**