Public App

# 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);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

The `swap` function swaps two integer values passed as pointers.

The `partition` function takes an integer array `arr`, and two integer values `low` and `high`, 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.

The `quickSort` function recursively sorts the array by calling `partition` and then calling itself on the two resulting subarrays until the whole array is sorted.

The `main` function creates an integer array and calls the `quick Sort` function to sort it. Finally, it prints the sorted array to the console.

Note that the worst-case time complexity of quick sort is O(n^2), but its average and best-case complexity is O(n log n), making it a very efficient algorithm for sorting large arrays.