Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has O(n2) worst time complexity which occurs when the input list is reverse sorted.[1] It has a best case time complexity of O(n) which occurs when the input is a list that is already sorted.[citation needed]
The algorithm first moves the first element of a list into a sub-list.[1] It then compares the last element in the sub-list to each subsequent element in the original list.[1] Once there is an element in the original list that is greater than the last element in the sub-list, the element is removed from the original list and added to the sub-list.[1] This process continues until the last element in the sub-list is compared to the remaining elements in the original list.[1] The sub-list is then merged into a new list.[1] Repeat this process and merge all sub-lists until all elements are sorted.[1] This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time.[1] This algorithm is also used in J Sort for fewer than 40 elements.[2]
YouTube Encyclopedic
-
1/3Views:3 26013 3447 164
-
Sorting: Ep 10 - Strand Sort
-
Sorting: Ep 05 - Insertion Sort
-
Sorting: Ep 04 - Cocktail Sort
Transcription
Hello YouTube, and welcome to sorting algorithms. Today we will cover the Strand Sort. In the previous episode we looked at Merge Sort and today's sorting algorithm is actually a variation of that. Similarly to the Merge Sort, Strand Sort attempts to break down a list into smaller sublists so that it can eventually merge these smaller sublists into one entire sorted list However, Strand sort takes a slightly more elegant approach to creating its sublists. Here is our unsorted list. Strand sort works by lifting sorted strands out of the unsorted list. To do that, it starts by picking out the first item. Do note that the first item is always picked out for sure. Remember that our strand of items must be sorted. trand sort looks at the second item in the list, and considers - If it were to add this to the strand, would the strand still be sorted? Clearly, if this value was smaller than the last value already in the strand, then the sublist will no longer be sorted. Consider the demonstration - We've already pulled out "4" to form the first item in our strand. We want an ascending order. If we were to add "2" to the strand, there would no longer be an ascending order. For an ascending order to still exist, only a value larger than "4" can be added. And that's why we skip over "2", and move on to "6". Now clearly, "6" is larger than "4" and can be added to the strand. from this point on, in order to maintain the ascending order, the next item must be larger than "6" instead. That explains why we skip over "1" and "3", but go on to add "7" to the strand. Similarly, the next item must be greater than "7" now. So we skip over "5", and add "8" to the strand. Now, what we have here is a single, complete strand. Since there is nothing in the sorted list yet, the strand becomes the sorted list for now. And the process repeats itself - We create another strand from the existing items. Now we want to add the contents of the strand to the sorted list. Of course, we do this by merging. Since there are still items in the unsorted list, strand sort must run again, and extract another strand for merging. Since only "1" is left, the algorithm will form a strand with just "1", and merge that into the sorted list, creating our final sorted list. While this may look a lot more efficient than Merge Sorting, this is actually less efficient in the worst case. You see, in Merge Sort, we know lists will be seperated into two at all times and we know that is the most efficient form of divide and conquer algorithms. If you were to give strand sort an inversely sorted list for input it cannot effectively create sorted strands - In other words, it is unable to split the list into half each time. Thus, in the worst case, Strand sort actually has an O(n²) timing. However, if given random or real world data, Strand sort fares with O(n log n) time on average. Now, if we were to compare Merge Sort and Strand Sort head to head using real-world data Strand sort will probably fare better, because Merge sort must divide a list into sublists of size one no matter what while Strand sort divides the list only as much as necessary. Well, that's all there is for this episode. In fact, that's all there is for this series because I've intended to stop it here. However, I think I'll have one more episode, just to let you in on a special sorting secret... I'll see you again for the secret final episode of sorting algorithms. You're watching 0612 TV.
Example
This example is based on the description of the algorithm provided in the book, IT Enabled Practices and Emerging Management Paradigms.[1]
Step 1: Start with a list of numbers: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7 }
Step 2: Next move the first element of the list into a new sub-list: sub-list contains {5}
Step 3: Then iterate through the original list and compare each number to 5 until there is a number greater than 5.
- 1 < 5 so 1 is not added to the sub-list.
- 4 < 5 so 4 is not added to the sub-list.
- 2 < 5 so 2 is not added to the sub-list.
- 0 < 5 so 0 is not added to the sub-list.
- 9 > 5 so 9 is added to the sub-list and removed from the original list.
Step 4: Now compare 9 with the remaining elements in the original list until there is a number greater than 9.
- 6 < 9 so 6 is not added to the sub-list.
- 3 < 9 so 3 is not added to the sub-list.
- 8 < 9 so 8 is not added to the sub-list.
- 7 < 9 so 7 is not added to the sub-list.
Step 5: Now there are no more elements to compare 9 to so merge the sub-list into a new list, called solution-list.
After step 5, the original list contains {1, 4, 2, 0, 6, 3, 8, 7}
The sub-list is empty, and the solution list contains {5, 9}
Step 6: Move the first element of the original list into sub-list: sub-list contains {1}
Step 7: Iterate through the original list and compare each number to 1 until there is a number greater than 1.
- 4 > 1 so 4 is added to the sub-list and 4 is removed from the original list.
Step 8: Now compare 4 with the remaining elements in the original list until there is a number greater than 4.
- 2 < 4 so 2 is not added to the sub-list.
- 0 < 4 so 0 is not added to the sub-list.
- 6 > 4 so 6 is added to the sub-list and is removed from the original list.
Step 9: Now compare 6 with the remaining elements in the original list until there is a number greater than 6.
- 3 < 6 so 3 is not added to the sub-list.
- 8 > 6 so 8 is added to the sub-list and is removed from the original list.
Step 10: Now compare 8 with the remaining elements in the original list until there is a number greater than 8.
- 7 < 8 so 7 is not added to the sub-list.
Step 11: Since there are no more elements in the original list to compare {8} to, the sub-list is merged with the solution list. Now the original list contains {2, 0, 3, 7}, the sub-list is empty and the solution-list contains: {1, 4, 5, 6, 8, 9}.
Step 12: Move the first element of the original list into sub-list. Sub-list contains {2}
Step 13: Iterate through the original list and compare each number to 2 until there is a number greater than 2.
- 0 < 2 so 0 is not added to the sub-list.
- 3 > 2 so 3 is added to the sub-list and is removed from the original list.
Step 14: Now compare 3 with the remaining elements in the original list until there is a number greater than 3.
- 7 > 3 so 7 is added to the sub-list and is removed from the original list.
Step 15: Since there are no more elements in the original list to compare {7} to, the sub-list is merged with the solution list. The original list now contains {0}, the sub-list is empty, and solution list contains: {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Step 16: Move the first element of the original list into sub-list. Sub-list contains {0}.
Step 17: Since the original list is now empty, the sub-list is merged with the solution list. The solution list now contains: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. There are now no more elements in the original list, and all of the elements in the solution list have successfully been sorted into increasing numerical order.
Implementation
Since Strand Sort requires many insertions and deletions, it is best to use a linked list when implementing the algorithm.[3] Linked lists require constant time for both insertions and removals of elements using iterators. The time to traverse through the linked list is directly related to the input size of the list.[4] The following implementation is done in Java 8 and is based on the description of the algorithm from the book, IT Enabled Practices and Emerging Management Paradigms.[1]
package strandSort;
import java.util.*;
public class strandSort {
static LinkedList<Integer> solList = new LinkedList<Integer>();
static int k = 0;
/**
* This is a recursive Strand Sort method. It takes in a linked list of
* integers as its parameter. It first checks the base case to see if the
* linked list is empty. Then proceeds to the Strand sort algorithm until
* the linked list is empty.
*
* @param origList:
* a linked list of integers
*/
public static void strandSortIterative(LinkedList<Integer> origList) {
// Base Case
if (origList.isEmpty()) {
return;
}
else {
// Create the subList and add the first element of
// The original linked list to the sublist.
// Then remove the first element from the original list.
LinkedList<Integer> subList = new LinkedList<Integer>();
subList.add(origList.getFirst());
origList.removeFirst();
// Iterate through the original list, checking if any elements are
// Greater than the element in the sub list.
int index = 0;
for (int j = 0; j < origList.size(); j++) {
if (origList.get(j) > subList.get(index)) {
subList.add(origList.get(j));
origList.remove(j);
j = j - 1;
index = index + 1;
}
}
// Merge sub-list into solution list.
// There are two cases for this step/
// Case 1: The first recursive call, add all of the elements to the
// solution list in sequential order
if (k == 0) {
for (int i = 0; i < subList.size(); i++) {
solList.add(subList.get(i));
k = k + 1;
}
}
// Case 2: After the first recursive call,
// merge the sub-list with the solution list.
// This works by comparing the greatest element in the sublist (which is always the last element)
// with the first element in the solution list.
else {
int subEnd = subList.size() - 1;
int solStart = 0;
while (!subList.isEmpty()) {
if (subList.get(subEnd) > solList.get(solStart)) {
solStart++;
} else {
solList.add(solStart, subList.get(subEnd));
subList.remove(subEnd);
subEnd--;
solStart = 0;
}
}
}
strandSortIterative(origList);
}
}
public static void main(String[] args) {
// Create a new linked list of Integers
LinkedList<Integer> origList = new LinkedList<Integer>();
// Add the following integers to the linked list: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7}
origList.add(5);
origList.add(1);
origList.add(4);
origList.add(2);
origList.add(0);
origList.add(9);
origList.add(6);
origList.add(3);
origList.add(8);
origList.add(7);
strandSortIterative(origList);
// Print out the solution list
for (int i = 0; i < solList.size(); i++) {
System.out.println(solList.get(i));
}
}
}
References
- ^ a b c d e f g h i j IT enabled practices and emerging management paradigms. Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research. (1st ed.). Indore: Prestige Institute of Management and Research. 2008. ISBN 9788174466761. OCLC 641462443.
{{cite book}}: CS1 maint: others (link) - ^ Sudipta., Mukherjee (2008). Data structures using C : 1000 problems and solutions. New Delhi: Tata McGraw-Hill. ISBN 9780070667655. OCLC 311311576.
- ^ "strand sort". xlinux.nist.gov. Retrieved 2018-11-06.
- ^ "LinkedLists". www.cs.cmu.edu. Retrieved 2018-11-06.
This page was last edited on 5 May 2022, at 19:28