SHARE
TWEET

Untitled

a guest Apr 23rd, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* C implementation QuickSort */
  2. #include<stdio.h>
  3. #include<iostream>
  4. #include<algorithm>
  5. using namespace std;
  6.  
  7. const int MAX_SIZE = 1000;
  8. int arr[MAX_SIZE];
  9.  
  10. /* This function takes last element as pivot, places
  11. the pivot element at its correct position in sorted
  12.     array, and places all smaller (smaller than pivot)
  13. to left of pivot and all greater elements to right
  14. of pivot */
  15.  
  16. int partition_arr( int lft, int rgt )
  17. {
  18.     int mid = (lft + rgt)/2;
  19.     swap( arr[lft], arr[rgt] );
  20.     int pivot = arr[lft];
  21.     int lo = lft + 1;
  22.     int hi = rgt;
  23.  
  24.     while( lo <= hi ){
  25.         while( arr[hi] > pivot ) hi--;
  26.         while( lo <= hi && arr[lo] <= pivot ) lo++;
  27.         if( lo <= hi ){
  28.             swap( arr[lo], arr[hi] );
  29.             lo++;
  30.             hi--;
  31.         }
  32.     }
  33.     swap( arr[lft], arr[hi] );
  34.     return hi;      // Return the index of the pivot
  35. }
  36.  
  37. /* The main function that implements QuickSort
  38. arr[] --> Array to be sorted,
  39. low --> Starting index,
  40. high --> Ending index */
  41. void quickSort( int low, int high)
  42. {
  43.     if (low < high)
  44.     {
  45.         /* pi is partitioning index, arr[p] is now
  46.         at right place */
  47.         int pi = parti( low, high );
  48.  
  49.         // Separately sort elements before
  50.         // partition and after partition
  51.         quickSort(low, pi - 1);
  52.         quickSort( pi + 1, high);
  53.     }
  54. }
  55.  
  56. /* Function to print an array */
  57. void print_arr( int n )
  58. {
  59.     for( int i = 0; i < n; i++ )
  60.         cout << arr[i] << " ";
  61.     cout << endl;
  62. }
  63.  
  64. // Driver program to test above functions
  65. int main()
  66. {
  67.     int n;
  68.     cin>>n;
  69.     for(int i=0;i<n;i++)
  70.         cin>>arr[i];
  71.    
  72.     quickSort( 0, n-1);
  73.    
  74.     printf("Sorted array: ");
  75.     print_arr(n);
  76.  
  77.  
  78.     return 0;
  79. }
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