Strand sort: Difference between revisions

Revision as of 21:48, 20 February 2019

Latest revision as of 06:34, 30 November 2024

(16 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Sorting algorithm}}

{{AFC submission|d|essay|u=Heldw|ns=118|decliner=K.e.coffman|declinets=20181205015623|ts=20181106172526}} <!-- Do not remove this line! -->

{{AFC comment|1=Please also see [[WP:HOWTO]]. [[User:K.e.coffman|K.e.coffman]] ([[User talk:K.e.coffman|talk]]) 01:56, 5 December 2018 (UTC)}}

{{AFC comment|1=This was deleted from mainspace several years ago. See [[Wikipedia:Articles for deletion/Strand sort]]. For what it's worth, this draft looks like it was written entirely from scratch, at least we're not talking [[WP:G4]]. I don't see it mentioned in [[Introduction to Algorithms|CLR]], which is pretty much the authoritative text for these sorts of things. That's not a good sign.

The previous AfD was not very well attended, and this draft looks reasonable sourced, so my inclination is that it should be accepted into mainspace, as one could make a reasonable argument that this passes [[WP:AFCR#Reviewing workflow]]. If there's still a question of notability, it can be brought back to AfD for another look. I'll leave it to another reviewer to make a final decision on that. -- [[User:RoySmith|RoySmith]] [[User Talk:RoySmith|(talk)]] 01:52, 5 December 2018 (UTC)}}

----

[[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|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 {{Math|''O''(''n'')}}, which occurs when the input is a list that is already sorted.<ref name=":1">{{CiteCitation webneeded|urlreason=https://xlinux.nist.gov/dads/HTML/strandSort.html|title=strandThe sort|website=xlinux.nist.gov|language=en-US|access-date=2018-11-06}}</ref>previously Strandgiven sortcitation isdoes not [[In-placemention algorithmperformance|in-place]] as it’s space complexity is O(n).<ref namedate=":0"May />2022}}

'''Strand sort''' is a very simple [[Recursion (computer science)|recursive]] [[sorting algorithm]] that sorts items of a list into increasing order.

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

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

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: {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.

'''Step 1:''' Start with a list of numbers: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7 }.

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

*'''Step 2:''' <Next, 5move sothe 2first iselement notof addedthe tolist theinto 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.

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

* 91 >< 5, so 91 is not added to the sub-list and removed from the original list.

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

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

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

* 69 > 45, so 69 is added to the sub-list and is 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.

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

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

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

*'''Step 35:''' <Now 9there soare 3no ismore notelements addedto 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}.

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

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

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

'''Step 56:''' NowMove therethe arefirst noelement moreof elementsthe tooriginal comparelist 9 to so merge theinto sub-list: into a new sub-list, calledcontains solution-list{1}.

After'''Step step7:''' Iterate 5,through the original list containsand compare each number to {1, 4,until 2,there 0,is 6,a 3,number 8,greater 7}than 1.

The* 4 > 1, so 4 is added to the sub-list and 4 is empty,removed andfrom the solutionoriginal list contains {5, 9}.

'''Step 68:''' MoveNow compare 4 with the firstremaining elementelements ofin the original list intountil sub-list:there sub-listis a number greater containsthan {1}4.

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

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

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

* 46 > 14, so 46 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.

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

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

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

* 07 < 28, so 07 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 1211:'''  MoveSince thethere firstare elementno ofmore elements in the original list intoto compare {8} to, the sub-list is merged with the solution list. Sub-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 1312:''' Iterate through Move the originalfirst listelement andof comparethe eachoriginal numberlist tointo 2sub-list. untilSub-list there is a number greater thancontains {2}.

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

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

* 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.<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 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 214 ⟶ 192:

{{reflist}}

[[Category:Sorting algorithms]]

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