Advertisement
4da

painfully written quicksort

4da
Nov 21st, 2011
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void swap(vector<int> &a, int e1, int e2)
  6. {
  7.     int tmp = a[e1];
  8.     a[e1] = a[e2];
  9.     a[e2] = tmp;
  10. }
  11.  
  12. void pvec(vector<int> &v)
  13. {
  14.     for (int i = 0; i < v.size(); i++)
  15.         cout << v[i] << " ";
  16.     cout << endl;
  17. }
  18.  
  19. int partition(vector<int> &a, int p, int l, int r)
  20. {
  21.     // move pivot to the right
  22.     swap(a, p, r);
  23.  
  24.     p = r;
  25.     int P = a[p];
  26.    
  27.     int sidx = l;
  28.  
  29.     for (int i = l; i < r; i++)
  30.     {
  31.         if (a[i] < P) {
  32.             swap(a, sidx, i);
  33.             sidx++;
  34.         }
  35.     }
  36.    
  37.     swap(a, r, sidx);
  38.     return sidx;
  39. }
  40.  
  41. void quick_sort(vector<int> &a, int l, int r)
  42. {
  43.     if (l >= r)
  44.         return;
  45.  
  46.     int pind = partition (a, l, l, r);
  47.  
  48.     quick_sort(a, l, pind-1);
  49.     quick_sort(a, pind+1, r);
  50. }
  51.  
  52. int main()
  53. {
  54.     int arr[9] = {11, 7, 4, 1, 14, 31, 9, 5, 24};
  55.     vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );
  56.    
  57.     quick_sort(vec, 0, vec.size() - 1);
  58.     pvec(vec);
  59. }
  60.  
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement