Advertisement
oaktree

Quick Sort (In-Place) - C++

Mar 24th, 2016
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cstdlib>
  5. #include <iterator>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. void swap(vector<char>::iterator a, vector<char>::iterator b) {
  11.     char tmp = *a;
  12.     *a = *b;
  13.     *b = tmp;
  14. }
  15. void quicksort(vector<char>::iterator begin, vector<char>::iterator end) {
  16.     if (distance(begin,end) <= 1) return;
  17.  
  18.     vector<char>::iterator a, b;
  19.  
  20.     char pivot = *(end - 1);
  21.  
  22.     a = begin; b = end - 1;
  23.  
  24.     while(b > a) {
  25.         if ( *(b-1) > pivot) {
  26.             *b = *(b-1);
  27.             b--;
  28.         } else {
  29.             swap(b-1, a);
  30.             a++;
  31.         }
  32.     }
  33.  
  34.     *b = pivot;
  35.  
  36.     quicksort(begin, b);
  37.     quicksort(b + 1, end);
  38. }
  39.  
  40.  
  41. int main() {
  42.  
  43.     cout << "give me a string" << endl;
  44.     string s; getline(cin, s);
  45.  
  46.     vector<char> vec(s.begin(), s.end());
  47.  
  48.     quicksort(vec.begin(), vec.end());
  49.  
  50.     string str(vec.begin(), vec.end());
  51.  
  52.     cout << str << endl;
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement