oaktree

Insertion Sort - C++

Mar 11th, 2016
120
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. bool sorted(vector<char>& vec) {
  8.     for (int i = 1, n = vec.size(); i < n; i++) {
  9.         if (vec[i] < vec[i-1]) return false;
  10.     }
  11.  
  12.     return true;
  13. }
  14. void insertionsort(vector<char>& vec) {
  15.     int n = vec.size();
  16.     /*
  17.     * The first element in the array is treated as sorted,
  18.     * so we go on to the second one, vec[1], which is why
  19.     * the for loop starts at i = 1
  20.     */
  21.     while (!sorted(vec)) {
  22.         for (int i = 1; i < n; i++) {
  23.             // if the element to the left bigger than the element we are looking at, vec[i]
  24.             // we need to put vec[i] where it belongs.
  25.             // and we do this by temporarily storing the value of vec[i] and then shifting
  26.             // all the elements of the array/vec that are bigger than vec[i] to the right
  27.             // until we arrive at vec[i]'s new, rightful place
  28.             if (vec[i-1] > vec[i]) {
  29.                 int hold = vec[i]; // hold value
  30.  
  31.                 int pos = i; // track positive to insert `hold`
  32.                
  33.                 while (pos > 0 && vec[pos - 1] > hold) {
  34.                    
  35.                     vec[pos] = vec[pos - 1];
  36.                     pos--;
  37.  
  38.                     // but, if our original vec[i] is bigger than
  39.                     // the element we shifted in the last iteration,
  40.                     // we can stop shifting
  41.                 }
  42.                 // now we can put the original vec[i] where it belongs by accessing
  43.                 // the pos variable which holds the position we want to INSERT the
  44.                 // original vec[i] into
  45.                 vec[pos] = hold;
  46.             }
  47.         }
  48.     }
  49. }
  50. // BELOW IS JUST INPUT, FEEL FREE TO OVERLOOK
  51. int main() {
  52.     cout << "give me a string" << endl;
  53.     string s; getline(cin, s);
  54.  
  55.     vector<char> vec(s.begin(), s.end());
  56.  
  57.     if (!vec.empty()) insertionsort(vec);
  58.  
  59.     string str(vec.begin(), vec.end());
  60.  
  61.     cout << str << endl;
  62.     return 0;
  63. }
RAW Paste Data