# C Program to Implement Quick Sort with Given Complexity Constraint

This is a C Program to implement Quick sort. This program sorts numbers using randomized quick sort.

Here is source code of the C Program to Implement Quick Sort with Given Complexity Constraint. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <stdio.h>`
2. `#include <stdlib.h>`
3. `#define MAX 10`
4. `void random_shuffle(int arr[]) {`
5. `    srand(time(NULL));`
6. `    int i, j, temp;`
7. `    for (i = MAX - 1; i > 0; i--) {`
8. `        j = rand() % (i + 1);`
9. `        temp = arr[i];`
10. `        arr[i] = arr[j];`
11. `        arr[j] = temp;`
12. `    }`
13. `}`
14. ` `
15. `void swap(int *a, int *b) {`
16. `    int temp;`
17. `    temp = *a;`
18. `    *a = *b;`
19. `    *b = temp;`
20. `}`
21. `int partion(int arr[], int p, int r) {`
22. `    int pivotIndex = p + rand() % (r - p + 1); //generates a random number as a pivot`
23. `    int pivot;`
24. `    int i = p - 1;`
25. `    int j;`
26. `    pivot = arr[pivotIndex];`
27. `    swap(&arr[pivotIndex], &arr[r]);`
28. `    for (j = p; j < r; j++) {`
29. `        if (arr[j] < pivot) {`
30. `            i++;`
31. `            swap(&arr[i], &arr[j]);`
32. `        }`
33. ` `
34. `    }`
35. `    swap(&arr[i + 1], &arr[r]);`
36. `    return i + 1;`
37. `}`
38. ` `
39. `void quick_sort(int arr[], int p, int q) {`
40. `    int j;`
41. `    if (p < q) {`
42. `        j = partion(arr, p, q);`
43. `        quick_sort(arr, p, j - 1);`
44. `        quick_sort(arr, j + 1, q);`
45. `    }`
46. `}`
47. `int main() {`
48. `    int i;`
49. `    int arr[MAX];`
50. `    for (i = 0; i < MAX; i++)`
51. `        arr[i] = i;`
52. `    random_shuffle(arr); //To randomize the array`
53. `    quick_sort(arr, 0, MAX - 1); //function to sort the elements of array`
54. `    for (i = 0; i < MAX; i++)`
55. `        printf("%d ", arr[i]);`
56. `    return 0;`
57. `}`

Output:

```\$ gcc QuickSortComplexityConstraint.c
\$ ./a.out

0 1 2 3 4 5 6 7 8 9```

Sanfoundry Global Education & Learning Series – 1000 C Programs.