oaktree

Bubble Sort - C++

Mar 6th, 2016
154
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cstdlib>
  5.  
  6. using namespace std;
  7.  
  8. void bubblesort(vector<char>& vec) {
  9.     int n = vec.size();
  10.  
  11.     // nest loops because O(n^2)
  12.     // changes_made is an optimization that can reduce runtime in certain conditions
  13.     bool changes_made = false;
  14.  
  15.     for (int i = 0; i < n - 1; i++) {
  16.  
  17.         for (int j = 0; j < n - 1; j++) {
  18.             if (vec[j] > vec[j+1]) {
  19.  
  20.                 // swap them
  21.                 char temp = vec[j];
  22.                 vec[j] = vec[j+1];
  23.                 vec[j+1] = temp;
  24.  
  25.                 // tell program to run thru vec at least once more
  26.                 changes_made = true;
  27.             }
  28.         }
  29.  
  30.         // optimization to exit loop if no changes made
  31.         if (!changes_made) break;
  32.  
  33.         changes_made = false;
  34.     }
  35. }
  36.  
  37. int main() {
  38.     cout << "give me a string" << endl;
  39.     string s; getline(cin, s);
  40.  
  41.     vector<char> vec(s.begin(), s.end());
  42.  
  43.     if (!vec.empty()) bubblesort(vec);
  44.  
  45.     string str(vec.begin(), vec.end());
  46.  
  47.     cout << str << endl;
  48.     return 0;
  49. }
RAW Paste Data