 # 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, 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