QuickSort.
1 /* Name : Vaibhav Yadav
2
3 Roll No.59
4
5 Implementation on Quick Sort algorithm in C
6
7 C Program to sort an array in ascending order using Quick sort
8
9 */
10 #include <stdio.h>
11
12 // Partition function using simultaneous low and high pointers
13 int partition(int arr[], int low, int high)
14 {
15 int pivot = arr[low]; // Choose the first element as the pivot
16 int i = low - 1; // Start from outside the range
17 int j = high + 1; // Start from outside the range
18
19 while (1)
20 {
21 // Move the low pointer to the right until finding an element >= pivot
22 do
23 {
24 i++;
25 } while (arr[i] < pivot);
26
27 // Move the high pointer to the left until finding an element <= pivot
28 do
29 {
30 j--;
31 } while (arr[j] > pivot);
32
33 // If pointers meet, return the partition index
34 if (i >= j)
35 return j;
36
37 // Swap arr[i] and arr[j]
38 int temp = arr[i];
39 arr[i] = arr[j];
40 arr[j] = temp;
41 }
42 }
43
44 // Quick Sort function
45 void quicksort(int arr[], int low, int high)
46 {
47 if (low < high)
48 {
49 // Partition the array and get the partition index
50 int pi = partition(arr, low, high);
51
52 // Recursively sort the two halves
53 quicksort(arr, low, pi);
54 quicksort(arr, pi + 1, high);
55 }
56 }
57
58 // Main function
59 int main()
60 {
61 int nums;
62 printf("Enter the number of elements in the array: ");
63 scanf("%d", &nums);
64
65 int arr[nums];
66 printf("Enter the array elements:\n");
67 for (int i = 0; i < nums; i++)
68 scanf("%d", &arr[i]);
69
70 // Call Quick Sort
71 quicksort(arr, 0, nums - 1);
72
73 // Print the sorted array
74 printf("Sorted array is:\n");
75 for (int i = 0; i < nums; i++)
76 printf("%d\t", arr[i]);
77
78 return 0;
79 }
80
81 /*
82 Best Case: O(nlogn)
83 Average Case: O(nlogn)
84 Worst Case: O(n^2)
85
86
87 */
