In this tutorial, we will write a C program to implement quick sort. Before that, you may go through the following topics in C.
Quick Sort Algorithm
Quicksort algorithm is a way of rearranging the elements in an array in ascending or descending order. Quicksort is another Divide and Conquer algorithm.
It takes two empty arrays to hold elements, the first is less than the pivot value and the second element greater than the pivot value, and then sort the element around it or inside it. It involves Swapping and partitioning a section of the array.
Implementation of Quick SortAlgorithm in C
Question: C program to implement Quick sort using function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | // implementation of quick sort in C program #include <stdio.h> // function prototype void quickSort(int a[], int start, int end); int partitionFunc(int a[], int start, int end); int main() { int arr[30], n, i; printf("Enter the number of elements: "); scanf("%d", &n); printf("Enter %d Elements:\n", n); for (i = 0; i < n; i++) scanf("%d", &arr[i]); //calling sorting function quickSort(arr, 0, n - 1); //Display the result printf("\nArray after sorting: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } int partitionFunc(int a[], int start, int end) { int pivot = a[end]; // pivot element int i = (start - 1); for (int j = start; j <= end - 1; j++) { // If current is smaller than the pivot if (a[j] < pivot) { i++; //swap int t = a[i]; a[i] = a[j]; a[j] = t; } } //swap int t = a[i + 1]; a[i + 1] = a[end]; a[end] = t; return (i + 1); } //quickSort Function void quickSort(int a[], int start, int end) { if (start < end) { //p_index is the partitioning index int p_index = partitionFunc(a, start, end); quickSort(a, start, p_index - 1); quickSort(a, p_index + 1, end); } } |
Output:
Enter the number of elements: 6
Enter 6 Elements:
12
65
5
224
68
45
Array after sorting:
5 12 45 65 68 224
Time Complexity of Quick Sort:
- Best case:
0(n log n) - Average case:
0(n log n) - Worst case:
0(n^2)