Strand sort: Difference between revisions

Revision as of 01:56, 5 December 2018

Revision as of 03:18, 13 December 2018

Line 10:

[[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.

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

It has [[Big O notation|O]](n²) worst time complexity which occurs when the input list is reverse 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> It has a best case [[time complexity]] of O(n) which occurs when the input is a list that is already sorted.<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> Strand sort is not [[In-place algorithm|in-place]] as it’s space complexity is O(n).<ref name=":0" />

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

StrandThe sortalgorithm isfirst amoves verythe simplefirst [[Recursion (computer science)|recursive]] [[sorting algorithm]] that sorts itemselement of a list into increasinga ordersub-list.<ref Itname=":0" works/> It bythen movingcompares the firstlast element ofin a list into athe sub-list. Then comparingto each subsequent element in the sub-original list.<ref toname=":0" the/> originalOnce listthere andis moving eachan element in the original list that is greater than the last element in the sub-list, tothe element is removed from the sub-original list. Thenand added to the sub-list.<ref isname=":0" merged/> intoThis aprocess newcontinues list.until Repeatthe thislast processelement andin merge allthe sub-listslist untilis allcompared to the remaining elements arein sortedthe original list.<ref name=":0">{{Cite book|url=https://www.worldcat.org/oclc/641462443|title=IT> enabledThe practicessub-list andis emergingthen managementmerged paradigms|date=2008|publisher=Prestigeinto Institutea ofnew Managementlist.<ref and Research|othersname=Gupta,":0" I./> C.Repeat (Ishwarthis Chandra),process 1946-,and Jaroliya,merge Deepak.,all Prestigesub-lists Instituteuntil ofall Managementelements andare Researchsorted.|isbn=9788174466761|edition=<ref 1st|___locationname=Indore|oclc=641462443}}<":0" /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=":10">{{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>

== Example ==

Based off of 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. 19 > 13 so 19 is added to the list.

* 4 < 5 so 4 is not added to the sub-list.

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

6* 2 < 195 so 62 is not added to the list. 25 > 19 so 25 is added to the sub-list.

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

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

29* 9 > 255 so 299 is added to the sub-list and removed from the original list.

'''Step 64:''' Now compare 299 towith the remaining elements in the original list until there is a number greater than 299.  

29* >6 1< 9 so 16 is not added to the sub-list. 29 > 4 so 4 is not added to the sub-list.

'''Step* 7:'''3 Merge< the9 sub-listso into3 ais newnot list,added calledto solutionthe sub-list.

* 8 < 9 so 8 is not added to the sub-list.

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

* 7 < 9 so 7 is not added to the sub-list.

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

'''Step 85:''' MoveNow thethere firstare elementno ofmore theelements originalto listcompare into9 to so merge the sub-list: sub-into a new list, containscalled solution-list. {7}

'''StepAfter 9:'''step Iterate through5, the original list andcontains compare{1, each4, number2, to0, 76, until3, there is a number greater than8, 7. }

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

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

'''Step 106:''' MergeMove sub-listthe first withelement of the original solution-list. Nowinto sub-list: is empty and solutionsub-list contains: {7, 13, 19, 25, 191}.

'''Step 57:''' NowIterate comparethrough 25the tooriginal thelist remainingand elementscompare ineach thenumber originalto list1 until there is a number greater than 251.

'''Step 11:'''  Move the first element of the original list into sub-list. Sub-list contains {6}

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

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

1'''Step <8:''' 6Now socompare 14 iswith notthe addedremaining toelements in the sub-original list. 4until < 6 so 4there is nota addednumber togreater thethan sub-list4.

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

'''Step 13:''' Since there are no more elements in the original list to compare {6} to, the sub-list is merged with the solution list.

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

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

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

'''Step 14:'''  Move the first element of the original list into sub-list. Sub-list contains {1}

'''Step 159:'''  IterateNow throughcompare the6 originalwith listthe andremaining compareelements eachin numberthe tooriginal 1list until there is a number greater than 16.  

4* >3 1< 6 so 43 is not added to the sub-list.

'''Step* 16:'''8  Since> there6 areso no8 moreis elements in the original list to compare {4}added to, the sub-list and is mergedremoved withfrom the solutionoriginal list.

The'''Step solution list now contains10:''' {1,4,Now 6,compare 7,8 13,with 19,the 25, 19}. There are now moreremaining elements in the original list, and all of the elements in the solution list haveuntil successfullythere beenis sorteda intonumber increasinggreater numericalthan order8.

* 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 sub-list is empty and solution-list contains: {1, 4, 5, 6, 8, 9}.

'''Step 1112:'''  Move the first element of the original list into sub-list. Sub-list contains {62}

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

* 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 414:''' Now compare 193 with the remaining elements in the original list until there is a number greater than 193.  

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

'''Step 1315:''' Since there are no more elements in the original list to compare {67} to, the sub-list is merged with the solution list.

The solution list now contains: {61, 72, 133, 194, 5, 6, 7, 258, 199}.

'''Step 1416:'''  Move the first element of the original list into sub-list. Sub-list contains {10}.

'''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 strandthe sortalgorithm.<ref name=":1" /> 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 of 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 84 ⟶ 109:

/**

* 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 108 ⟶ 133:

// 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 118 ⟶ 142:

}

}

// 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 131 ⟶ 154:

}

// 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);

}

Line 162 ⟶ 187:

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);