oaktree

Bubble Sort - C++

Mar 6th, 2016
167
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×