1// Aim: Program to perform Quick Sort on an array.
2#include <stdio.h>
3
4void printArray(int *A, int n)
5{
6    for (int i = 0; i < n; i++)
7    {
8        printf("%d ", A[i]);
9    }
10    printf("\n");
11}
12
13int partition(int A[], int low, int high)
14{
15    int pivot = A[low];
16    int i = low + 1;
17    int j = high;
18    int temp;
19
20    do
21    {
22        while (A[i] <= pivot)
23        {
24            i++;
25        }
26
27        while (A[j] > pivot)
28        {
29            j--;
30        }
31
32        if (i < j)
33        {
34            temp = A[i];
35            A[i] = A[j];
36            A[j] = temp;
37        }
38    } while (i < j);
39
40    // Swap A[low] and A[j]
41    temp = A[low];
42    A[low] = A[j];
43    A[j] = temp;
44    return j;
45}
46
47void quickSort(int A[], int low, int high)
48{
49    int partitionIndex; 
50
51    if (low < high)
52    {
53        partitionIndex = partition(A, low, high); 
54        quickSort(A, low, partitionIndex - 1);  
55        quickSort(A, partitionIndex + 1, high); 
56    }
57}
58
59
60int main()
61{
62    int n;
63    printf("Enter the number of elements: ");
64    scanf("%d", &n);
65
66    int A[n];
67    printf("Enter the elements: ");
68    for (int i = 0; i < n; i++)
69    {
70        scanf("%d", &A[i]);
71    }
72
73    printArray(A, n);
74    quickSort(A, 0, n - 1);
75    printArray(A, n);
76    return 0;
77}