C Program to Sort an Array using Randomized Quick Sort Technique

«
»
This C program sorts a given array of integer numbers using randomized Quick sort technique.

It is comparison sort which works on divide and conquer technique. It is in-place partitioning algorithm and one of the fastest sorting techniques available till date. Average Time Complexity of this algorithm is O(nlog(n)).

Here is the source code of the C program to sort integers using randomized Quick sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

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

$ gcc randomizedquicksort.c -o randomizedquicksort
$ ./randomizedquicksort
 
 
Sorted array is : 0 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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.