Strand sort: Difference between revisions

Revision as of 23:43, 11 November 2018

Latest revision as of 06:34, 30 November 2024

(21 intermediate revisions by 16 users not shown)

Line 1:

{{Short description|Sorting algorithm}}

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

'''Strand sort''' is a very simple [[Recursion (computer science)|recursive]] [[sorting algorithm]] that sorts items of a list into increasing order. It workshas by{{math|1=[[Big movingO the first element of a list into anotation|''O'']](''n''²)}} subworst-list.case Then[[time comparingcomplexity]], eachwhich subsequentoccurs element inwhen the sub-list to the originalinput 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 arereverse 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|___location=Indore|oclc=641462443}}</ref> ThisIt algorithmhas isa calledbest-case strandtime sort because there are strandscomplexity of sorted elements within the unsorted elements that are removed one at a time.<ref name=":1">{{Cite webMath|url=https://xlinux.nist.gov/dads/HTML/strandSort.html|title=strand sort|website=xlinux.nist.gov|language=en-US|access-date=2018-11-06''O''(''n'')}}</ref>, Thiswhich algorithmoccurs is also comparison [[sorting algorithm]] because elements ofwhen the sub-list are compared to elements of the original list.  This algorithminput is alsoalready used in [[J Sort]] for fewer than 40 elementssorted.<ref>{{CiteCitation bookneeded|url=https://www.worldcat.org/oclc/311311576|titlereason=DataThe structurespreviously usinggiven Ccitation :does 1000not problemsmention and solutions|last=Sudipta.|first=Mukherjee,performance|date=2008|publisher=TataMay McGraw-Hill|isbn=9780070667655|___location=New Delhi|oclc=3113115762022}}</ref>

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 Enabled Practices and Emerging Management Paradigms''.<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.

4* >2 1< 5, so 42 is not added to the sub-list.

29* >0 25< 5, so 290  is not added to the sub-list.

1* <9 6> 5, so 19 is not added to the sub-list. 4and <removed 6from sothe 4original is not added to the sub-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 75, the original list contains {71, 4, 2, 0, 6, 13, 48, 7}.

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

The sub-list is empty, and the solution list contains {135, 19, 25, 199}.

'''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 68:''' Now compare 294 towith the remaining elements in the original list until there is a number greater than 294.

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 ==

Since Strand Sort requires many insertions and deletions, it is best to use a linked list when implementing strandthe sortalgorithm. <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. Linked lists can only access sequential elements, which is what strand sort does. 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 off ofon 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;

Line 74 ⟶ 85:

/**

* This is a recursive Strand Sort method. It takes in a linked list of

* integers as parametersits parameter. It first checkchecks the base case to see if the linked

* linked list is empty. Then proceeds to the Strand sort algorithm until the

* the linked list is empty.

*

* @param origList:

Line 98 ⟶ 109:

// 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++) {

Line 108 ⟶ 118:

}

}

// Merge sub-list into solution list.
// There are threetwo cases for this step/

// step

// Case 1: The first recursive call, add all of the elements to the

// solution list in sequential order

// list in sequential order

if (k == 0) {

for (int i = 0; i < subList.size(); i++) {

Line 121 ⟶ 130:

}

// Case 2: After the first recursive call if there subList contains

// more than one element,

// the elements need to be added to

// The front of the solution list, adding the largest element first.

else if (subList.size() > 1) {

for (int w = subList.size() - 1; w >= 0; w--) {

solList.addFirst(subList.get(w));

// Case 2: After the first recursive call, if there subList contains

// w = w+1;

// It just gets added tomerge the frontsub-list ofwith 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 {

else int ifsubEnd = (subList.size() >- 1) {;

int solStart = 0;

while (!subList.isEmpty()) {

if (subList.get(subEnd) > solList.get(solStart)) {

}

solStart++;

} else {

// If there is only one element in the subList, then

// It just gets added to the front of the solution list.

for (int w = 0; w < subList.size(); w++) {

} else {

solList.addFirst(subList.get(w));

solList.addFirstadd(solStart, subList.get(wsubEnd));

subList.remove(subEnd);

subEnd--;

// w solStart = w+10;

}

}

}

strandSortIterative(origList);

strandSortIterative(origList);

}

Line 152 ⟶ 163:

LinkedList<Integer> origList = new LinkedList<Integer>();

// Add the following integers to the linked list: {135, 71, 194, 2, 0, 9, 6, 253, 298, 7}

// 1, 4}

origList.add(135);

origList.add(7);

origList.add(19);

origList.add(6);

origList.add(25);

origList.add(29);

origList.add(1);

origList.add(4);

origList.add(192);

origList.add(250);

origList.add(299);

origList.add(6);

origList.add(3);

origList.add(8);

origList.add(7);

strandSortIterative(origList);

Line 175 ⟶ 187:

</syntaxhighlight>

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

== References ==

Line 187 ⟶ 192:

{{reflist}}

[[Category:Sorting algorithms]]

{{AFC submission|||ts=20181106172526|u=Heldw|ns=118}}