Given a list of items, sort them in increasing order.
Examples:
Input : ip[] = {10, 5, 30, 40, 2, 4, 9} Output : op[] = {2, 4, 5, 9, 10, 30, 40} Input : ip[] = {1, 10, 7} Output : op[] = {1, 7, 10}
Strand Sort is a sorting algorithm that works in O(n) time if list is already sorted and works in O(n*n) in worst case.
Below are simple steps used in the algorithm.
- Let ip[] be input list and op[] be output list.
- Create an empty sublist and move first item of ip[] to it.
- Traverse remaining items of ip. For every item x, check if x is greater than last inserted item to sublist. If yes, remove x from ip and add at the end of sublist. If no, ignore x (Keep it it in ip)
- Merge sublist into op (output list)
- Recur for remaining items in ip and current items in op.
Illustration :
Let ip[] = {10, 5, 30, 40, 2, 4, 9} Initialize : op[] = {} sublist[] = {} Move first item of ip to sublist. sublist[] = {10} Traverse remaining items of ip and if current element is greater than last item of sublist, move this item from ip to sublist. Now sublist[] = {10, 30, 40} ip[] = {5, 2, 4, 9} Merge sublist into op. op = {10, 30, 40} Next recursive call: Move first item of ip to sublist. sublist[] = {5} Traverse remaining items of ip and move elements greater than last inserted. ip[] = {2, 4} sublist[] = {5, 9} Merge sublist into op. op = {5, 9, 10, 30, 40} Last Recursive Call: {2, 4} are first moved to sublist and then merged into op. op = {2, 4, 5, 9, 10, 30, 40}
Below is the implementation of above algorithm. The C++ implementation uses list in C++ STL.
// CPP program to implement Strand Sort #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; } |
Output:
2 4 5 9 10 30 40
More Sorting Algorithms :
- Bitonic Sort
- Cocktail Sort
- Pancake sorting
- Binary Insertion Sort
- BogoSort or Permutation Sort
- Gnome Sort
- Sleep Sort – The King of Laziness / Sorting while Sleeping
- Structure Sorting (By Multiple Rules) in C++
- Stooge Sort
- Tag Sort (To get both sorted and original)
- Tree Sort
- Cartesian Tree Sorting
- Odd-Even Sort / Brick Sort
- QuickSort on Singly Linked List
- QuickSort on Doubly Linked List
- 3-Way QuickSort (Dutch National Flag)
- Merge Sort for Linked Lists
- Merge Sort for Doubly Linked List
- 3-way Merge Sort
leave a comment
0 Comments