Strand sort: Difference between revisions

Revision as of 17:08, 6 November 2018

Latest revision as of 06:34, 30 November 2024

(24 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Sorting algorithm}}

Strand sort is a very simple [[Recursion (computer science)|recursive]] [[sorting algorithm]] that sorts items of a list into increasing order. It works by moving the first element of a list into a sub-list. Then comparing each subsequent element in the sub-list to the original list and moving each element in the original list that is greater than the element in the sub-list to the sub-list. Then the sub-list is merged into a new list. Repeat this process and merge all sub-lists until all elements are sorted.<ref name=":0">{{Cite book|url=https://www.worldcat.org/oclc/641462443|title=IT enabled practices and emerging management paradigms|date=2008|publisher=Prestige Institute of Management and Research|others=Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research.|isbn=9788174466761|edition=1st ed|___location=Indore|oclc=641462443}}</ref> This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time.<ref name=":1">{{Cite web|url=https://xlinux.nist.gov/dads/HTML/strandSort.html|title=strand sort|website=xlinux.nist.gov|language=en-US|access-date=2018-11-06}}</ref> This algorithm is also comparison [[sorting algorithm]] because elements of the sub-list are compared to elements of the original list.  This algorithm is also used in [[J Sort]] for fewer than 40 elements.<ref>{{Cite book|url=https://www.worldcat.org/oclc/311311576|title=Data structures using C : 1000 problems and solutions|last=Sudipta.|first=Mukherjee,|date=2008|publisher=Tata McGraw-Hill|isbn=9780070667655|___location=New Delhi|oclc=311311576}}</ref>

[[File:StrandSort.gif|thumb|220x220px|Strand Sort Animation]]

'''Strand sort''' is a [[Recursion (computer science)|recursive]] [[sorting algorithm]] that sorts items of a list into increasing order. It has {{math|1=[[Big O notation|''O'']](''n''²)}} worst-case [[time complexity]], which occurs when the input list is reverse sorted.<ref name=":0">{{Cite book|title=IT enabled practices and emerging management paradigms|date=2008|publisher=Prestige Institute of Management and Research|others=Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research.|isbn=9788174466761|edition=1st|___location=Indore|oclc=641462443}}</ref> It has a best-case time complexity of {{Math|''O''(''n'')}}, which occurs when the input is already sorted.{{Citation needed|reason=The previously given citation does not mention performance|date=May 2022}}

The algorithm first moves the first element of a list into a sub-list.<ref name=":0" /> It then compares the last element in the sub-list to each subsequent element in the original list.<ref name=":0" /> 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.<ref name=":0" /> This process continues until the last element in the sub-list is compared to the remaining elements in the original list.<ref name=":0" /> The sub-list is then merged into a new list.<ref name=":0" /> Repeat this process and merge all sub-lists until all elements are sorted.<ref name=":0" /> This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time.<ref name=":0" /> This algorithm is also used in [[J Sort]] for fewer than 40 elements.<ref>{{Cite book|title=Data structures using C : 1000 problems and solutions|last=Sudipta.|first=Mukherjee|date=2008|publisher=Tata McGraw-Hill|isbn=9780070667655|___location=New Delhi|oclc=311311576}}</ref>

== Performance ==

Strand sort has a worst case [[time complexity]] of O(n²) which occurs when the input list is reverse sorted.<ref name=":0" /> Where n represents the total number of elements being sorted. Strand sort has a best case [[time complexity]] of O(n) which occurs when the input is a list that is already sorted.<ref name=":1" /> Its average case complexity is O(n log n).<ref name=":0" /> Compared to other [[Sorting algorithm|sorting algorithms]], strand sort is on the slower side.<ref name=":0" />Strand sort is [[Stable algorithm|stable]] due to the fact that the relative order of the elements of the same value does not change. Strand sort is not [[In-place algorithm|in-place]] because it’s space complexity is O(n).<ref name=":0" />

== Example ==

BasedThis offexample ofis based on the description of the algorithm provided in the book ''IT enabledEnabled practicesPractices and emergingEmerging managementManagement paradigmsParadigms''.<ref name=":0" />

'''Step 1:''' Start with a list of numbers: {135, 71, 194, 62, 250, 299, 16, 43, 8, 7}.

'''Step 2:''' Next, move the first element of the list into a new sub-list:  sub-list contains {135}.

'''Step 3:''' Then, iterate through the original list and compare each number to 135 until there is a number greater than 135.

2* 1 < 135, so 71 is not added to the sub-list.
* 194 >< 135, so 194 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 199 with the remaining elements in the original list until there is a number greater than 199.  

* 6 < 199, so 6 is not added to the sub-list.
* 253 >< 199, so 253 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 comparethere 25are tono the remainingmore elements into thecompare original9 listto, untilso theremerge the sub-list isinto a numbernew greaterlist, thancalled 25solution-list.

After step 5, the original list contains {1, 4, 2, 0, 6, 3, 8, 7}.

29 > 25 so 29 is added to the sub-list.

The sub-list is empty, and the solution list contains {5, 9}.

'''Step 6:''' Now compare 29 to the remaining elements in the original list until there is a number greater than 29.

29'''Step >6:''' 1Move sothe 1first iselement notof addedthe tooriginal thelist into sub-list. 29 > 4 so 4 is not added to the: sub-list contains {1}.

'''Step 7:''' MergeIterate through the sub-original list intoand compare each number to 1 until there is a newnumber list,greater calledthan solution-list1.

* 4 > 1, so 4 is added to the sub-list and 4 is removed from the original list.

After step 7, the original list contains {7, 6, 1, 4}

'''Step 8:''' Now compare 4 with the remaining elements in the original list until there is a number greater than 4.

The sub-list is empty, and the solution list contains {13, 19, 25, 19}

'''Step* 8:'''2 Move< the4, firstso element2 ofis thenot originaladded listto intothe sub-list: sub-list contains {7}.

* 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:''' IterateNow throughcompare the6 originalwith listthe andremaining compareelements eachin numberthe tooriginal 7list until there is a number greater than 76.  

6* 3 < 76, so 63 is not added to the sub-list.
* 18 <> 76, so 18 is not added to the sub-list. 4 < 7 so 4and is notremoved added tofrom the suboriginal list.

'''Step 10:''' MergeNow sub-listcompare 8 with solution-list.the Nowremaining sub-listelements isin emptythe andoriginal solution-list contains:until there is {7,a 13,number 19,greater 25,than 19}8.

'''Step* 11:'''7  Move< the8, firstso element7 ofis thenot originaladded listto intothe sub-list. Sub-list contains {6}

'''Step 1211:''' IterateSince throughthere are no more elements in the original list andto compare each number{8} to, 6the untilsub-list thereis merged with the solution list. Now the original list contains {2, 0, 3, 7}, the sub-list is aempty, numberand greaterthe thansolution-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}.

1 < 6 so 1 is not added to the sub-list. 4 < 6 so 4 is not added to the sub-list.

'''Step 13:''' SinceIterate there are no more elements inthrough the original list toand compare {6}each number to, the2 sub-listuntil there is mergeda withnumber thegreater solutionthan list2.

* 0 < 2, so 0 is not added to the sub-list.

The solution list now contains: {6, 7, 13, 19, 25, 19}.

* 3 > 2, so 3 is added to the sub-list and is removed from the original list.

'''Step 14:'''  MoveNow compare 3 with the firstremaining elementelements ofin the original list intountil sub-list.there Sub-listis containsa {1}number greater than 3.

* 7 > 3, so 7 is added to the sub-list and is removed from the original list.

'''Step 15:'''  Iterate through the original list and compare each number to 1 until there is a number greater than 1.

'''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}.

4 > 1 so 4 is added to the sub-list.

'''Step 16:'''  SinceMove therethe arefirst noelement more elements inof the original list to compare {4} to, theinto sub-list. isSub-list mergedcontains with the solution list{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,4 2, 63, 74, 135, 196, 7, 258, 199}. 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 ==

{{AFC submission|t||ts=20181106150605|u=Heldw|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

Since Strand Sort requires many insertions and deletions, it is best to use a linked list when implementing the algorithm.<ref name=":1">{{Cite web|url=https://xlinux.nist.gov/dads/HTML/strandSort.html|title=strand sort|website=xlinux.nist.gov|language=en-US|access-date=2018-11-06}}</ref> 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.<ref>{{Cite web|url=https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html|title=LinkedLists|website=www.cs.cmu.edu|access-date=2018-11-06}}</ref> 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''.<ref name=":0" /><syntaxhighlight lang="java" line="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));

}

}

}

</syntaxhighlight>

== References ==

<!-- Inline citations added to your article will automatically display here. See https://en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->

{{reflist}}

[[Category:Sorting algorithms]]