SHARE
TWEET

Quicksort

Maruf_Hasan Jun 26th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2.  
  3. void swap(int* a, int* b)
  4. {
  5.     int t = *a;
  6.     *a = *b;
  7.     *b = t;
  8. }
  9.  
  10. int partition (int arr[], int low, int high)
  11. {
  12.     int pivot = arr[high];    // pivot
  13.     int i = (low);  // Index of smaller element
  14.  
  15.     for (int j = low; j <= high- 1; j++)
  16.     {
  17.         // If current element is smaller than or
  18.         // equal to pivot
  19.         if (arr[j] <= pivot)
  20.         {// increment index of smaller element
  21.             swap(&arr[i], &arr[j]);
  22.             i++;
  23.         }
  24.     }
  25.     swap(&arr[i], &arr[high]);
  26.     return (i);
  27. }
  28.  
  29. /* The main function that implements QuickSort
  30.  arr[] --> Array to be sorted,
  31.   low  --> Starting index,
  32.   high  --> Ending index */
  33. void quickSort(int arr[], int low, int high)
  34. {
  35.     if (low < high)
  36.     {
  37.         /* pi is partitioning index, arr[p] is now
  38.            at right place */
  39.         int pi = partition(arr, low, high);
  40.  
  41.         // Separately sort elements before
  42.         // partition and after partition
  43.         quickSort(arr, low, pi - 1);
  44.         quickSort(arr, pi + 1, high);
  45.     }
  46. }
  47.  
  48. /* Function to print an array */
  49. void printArray(int arr[], int size)
  50. {
  51.     int i;
  52.     for (i=0; i < size; i++)
  53.         printf("%d ", arr[i]);
  54.     //printf("n");
  55. }
  56.  
  57. // Driver program to test above functions
  58. int main()
  59. {
  60.     int arr[] = {10, 7, 8, 9, 1, 5};
  61.     int n = sizeof(arr)/sizeof(arr[0]);
  62.     quickSort(arr, 0, n-1);
  63.     printf("Sorted array: ");
  64.     printArray(arr, n);
  65.     return 0;
  66. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top