Strand Sort
Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has O(n²) worst time complexity which occurs when the input list is reverse sorted. It has a best case time complexity of O(n) which occurs when the input is a list that is already sorted.
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}
Illustrations:
Let, input[] = {10, 5, 30, 40, 2, 4, 9}
Initialize: output[] = {}, sublist[] = {}
Move first item of input to sublist.
sublist[] = {10}Traverse remaining items of input and if current element is greater than last item of sublist, move this item from input to sublist.
Now, sublist[] = {10, 30, 40}, input[] = {5, 2, 4, 9}Merge sublist into output.
op = {10, 30, 40}Next recursive call: Move first item of input to sublist. sublist[] = {5}
Traverse remaining items of input and move elements greater than last inserted.
input[] = {2, 4}
sublist[] = {5, 9}Merge sublist into op.
output = {5, 9, 10, 30, 40}Last Recursive Call:
{2, 4} are first moved to sublist and then merged into output.
output = {2, 4, 5, 9, 10, 30, 40}
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 in ip)
- Merge sublist into op (output list)
- Recur for remaining items in ip and current items in op.
Below is the implementation of above algorithm in C++ and Javascript. The C++ implementation uses list in C++ STL.
CPP
// 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; } |
Java
// Java Code import java.util.ArrayList; import java.util.List; public class StrandSort { // Define a helper function to merge two sorted lists public static List<Integer> mergeLists(List<Integer> list1, List<Integer> list2) { List<Integer> result = new ArrayList<>(); while (!list1.isEmpty() && !list2.isEmpty()) { if (list1.get( 0 ) < list2.get( 0 )) { result.add(list1.remove( 0 )); } else { result.add(list2.remove( 0 )); } } result.addAll(list1); result.addAll(list2); return result; } // Recursive function to perform strand sort public static List<Integer> strandSort(List<Integer> inputList) { // Base case: if the input list has 1 or fewer elements, it's already sorted if (inputList.size() <= 1 ) { return inputList; } // Initialize a sublist with the first element of the input list List<Integer> sublist = new ArrayList<>(); sublist.add(inputList.remove( 0 )); int i = 0 ; while (i < inputList.size()) { // If the current element in the input list is greater than // the last element in the sublist, // add it to the sublist; otherwise, continue to the next element in the input list. if (inputList.get(i) > sublist.get(sublist.size() - 1 )) { sublist.add(inputList.remove(i)); } else { i++; } } // The sortedSublist contains the sorted elements from the current sublist List<Integer> sortedSublist = new ArrayList<>(sublist); // Recursively sort the remaining part of the input list List<Integer> remainingList = strandSort(inputList); // Merge the sorted sublist and the sorted remainingList return mergeLists(sortedSublist, remainingList); } public static void main(String[] args) { List<Integer> inputList = new ArrayList<>(); inputList.add( 10 ); inputList.add( 5 ); inputList.add( 30 ); inputList.add( 40 ); inputList.add( 2 ); inputList.add( 4 ); inputList.add( 9 ); List<Integer> outputList = strandSort(inputList); for ( int x : outputList) { System.out.print(x + " " ); } } } // This code is contributed by guptapratik |
Python3
def strand_sort(ip): # Define a helper function to merge two sorted lists def merge_lists(list1, list2): result = [] while list1 and list2: if list1[ 0 ] < list2[ 0 ]: result.append(list1.pop( 0 )) else : result.append(list2.pop( 0 )) result + = list1 result + = list2 return result # Base case: if the input list has 1 or fewer elements, it's already sorted if len (ip) < = 1 : return ip # Initialize a sublist with the first element of the input list sublist = [ip.pop( 0 )] i = 0 while i < len (ip): # If the current element in the input list is greater than the last element in the sublist, # add it to the sublist; otherwise, continue to the next element in the input list. if ip[i] > sublist[ - 1 ]: sublist.append(ip.pop(i)) else : i + = 1 # The sorted_sublist contains the sorted elements from the current sublist sorted_sublist = sublist # Recursively sort the remaining part of the input list remaining_list = strand_sort(ip) # Merge the sorted sublist and the sorted remaining_list return merge_lists(sorted_sublist, remaining_list) #Driver code if __name__ = = "__main__" : ip = [ 10 , 5 , 30 , 40 , 2 , 4 , 9 ] op = strand_sort(ip) for x in op: print (x, end = " " ) |
C#
// C# Code using System; using System.Collections.Generic; public class StrandSort { // Define a helper function to merge two sorted lists public static List< int > MergeLists(List< int > list1, List< int > list2) { List< int > result = new List< int >(); while (list1.Count > 0 && list2.Count > 0) { if (list1[0] < list2[0]) { result.Add(list1[0]); list1.RemoveAt(0); } else { result.Add(list2[0]); list2.RemoveAt(0); } } result.AddRange(list1); result.AddRange(list2); return result; } // Recursive function to perform strand sort public static List< int > PerformStrandSort(List< int > inputList) { // Base case: if the input list has 1 or fewer elements, it's already sorted if (inputList.Count <= 1) { return inputList; } // Initialize a sublist with the first element of the input list List< int > sublist = new List< int >(); sublist.Add(inputList[0]); inputList.RemoveAt(0); int i = 0; while (i < inputList.Count) { // If the current element in the input list is greater than the last element in the sublist, // add it to the sublist; otherwise, continue to the next element in the input list. if (inputList[i] > sublist[sublist.Count - 1]) { sublist.Add(inputList[i]); inputList.RemoveAt(i); } else { i++; } } // The sortedSublist contains the sorted elements from the current sublist List< int > sortedSublist = new List< int >(sublist); // Recursively sort the remaining part of the input list List< int > remainingList = PerformStrandSort(inputList); // Merge the sorted sublist and the sorted remainingList return MergeLists(sortedSublist, remainingList); } public static void Main( string [] args) { List< int > inputList = new List< int > { 10, 5, 30, 40, 2, 4, 9 }; List< int > outputList = PerformStrandSort(inputList); foreach ( int x in outputList) { Console.Write(x + " " ); } } } // This code is contributed by guptapratik |
Javascript
// Javascript program to implement Strand Sort // A recursive function to implement Strand sort. // ip is input list of items (unsorted). // op is output list of items (sorted) function strandSort(ip) { // Create a sorted sublist with // first item of input list as // first item of the sublist var sublist=[]; sublist.push(ip[0]); ip.shift(); // Traverse remaining items of ip list var len=ip.length-1; //last index of input list var len2=sublist.length-1; //last index of sublist var it =0; while (it<=len){ // 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 (ip[it] >sublist[len2]) { sublist.push(ip[it]); len2++; // splice(index,1) on list removes an // item and moves "it" to // next of removed item. ip.splice(it,1); } // Otherwise ignore current element else { it++; } } // Merge current sublist into output while (sublist.length>0 && op.length>0){ if (sublist[0]>=op[0]){opp.push(op.shift());} else {opp.push(sublist.shift());} } if (sublist.length==0){ opp=[...opp,...op]; } if (op.length==0){ opp=[...opp,...sublist]; } op=[...opp]; opp.length=0; // Recur for remaining items in input and current items in op. //Added base case if (ip.length>0){ strandSort(ip); } } // Driver code var ip=[10, 5, 30, 40, 2, 4, 9]; // To store sorted output list var op=[]; //list helping in merge operation var opp=[]; // Sorting the list strandSort(ip); // Printing the sorted list console.log(op); |
2 4 5 9 10 30 40
Time complexity: O(N2)
Auxiliary Space: O(N)
Check out DSA Self Paced Course
More Sorting Algorithms :
Practice Problems on Sorting
Contact Us