Quick Sort Algorithm in C
Quick Sort algorithm is a divide-and-conquer sorting algorithm that works by selecting a "pivot" element and then partitioning the array around that pivot. It efficiently sorts an array by recursively applying the same logic to smaller sub-arrays.You can get the complete code from Github
Below is a detailed explanation of how QuickSort works:
1. Choose a Pivot:
Select an element from the list to serve as a pivot. There are different strategies for choosing the pivot, like picking the first element, the last element, a random element, or the median.
2. Partition the Array:
Rearrange the array such that all elements less than the pivot are on its left, and all elements greater than the pivot are on its right. The pivot itself will be placed in its correct position (sorted).
3. Recursively Apply:
Recursively apply the same process to the sub-arrays (left of the pivot and right of the pivot).
quicksort.c
1 #include<stdio.h>
2 int Arr[] = {43,45,98,23,21,5,1,8,2,6,77,18,4};
3
4 int pivot(int *Arr,int low,int high) {
5 int v = Arr[high];
6 int i, s, j = low;
7 for(i = low;i < high;i++) {
8 if(Arr[i] <= v) {
9 s = Arr[j];
10 Arr[j] = Arr[i];
11 Arr[i] = s;
12 j = j+1;
13 }
14 }
15 s = Arr[j];
16 Arr[j] = Arr[high];
17 Arr[high] = s;
18 return j;
19 }
20
21 void quicksort(int *Arr,int low,int high) {
22 if(low < high) {
23 int p = pivot(Arr,low,high);
24 quicksort(Arr,low,p - 1);
25 quicksort(Arr,p + 1, high);
26 }
27 }
28
29 int main() {
30 int i, n = sizeof(Arr)/sizeof(Arr[0]);
31 printf("Before Sort:\n");
32 for(i = 0;i < n;i++) {
33 printf("%d ",Arr[i]);
34 }
35 printf("\n");
36
37 quicksort(Arr,0,n-1);
38
39 printf("After Sort:\n");
40 for(i = 0;i < n;i++) {
41 printf("%d ",Arr[i]);
42 }
43 printf("\n");
44 return 0;
45 }