-
Notifications
You must be signed in to change notification settings - Fork 5
/
Strand-Sort.cpp
66 lines (54 loc) · 1.57 KB
/
Strand-Sort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
// A recursive function to implement Strand
// sort.
// ip is input list of items (unsorted).
// op is output list of items (sorted)
void strandSort(list<int> &ip, list<int> &op)
{
// Base case : input is empty
if (ip.empty())
return;
// Create a sorted sublist with
// first item of input list as
// first item of the sublist
list<int> sublist;
sublist.push_back(ip.front());
ip.pop_front();
// Traverse remaining items of ip list
for (auto it = ip.begin(); it != ip.end(); ) {
// If current item of input list
// is greater than last added item
// to sublist, move current item
// to sublist as sorted order is
// maintained.
if (*it > sublist.back()) {
sublist.push_back(*it);
// erase() on list removes an
// item and returns iterator to
// next of removed item.
it = ip.erase(it);
}
// Otherwise ignore current element
else
it++;
}
// Merge current sublist into output
op.merge(sublist);
// Recur for remaining items in
// input and current items in op.
strandSort(ip, op);
}
// Driver code
int main(void)
{
list<int> ip{10, 5, 30, 40, 2, 4, 9};
// To store sorted output list
list<int> op;
// Sorting the list
strandSort(ip, op);
// Printing the sorted list
for (auto x : op)
cout << x << " ";
return 0;
}