Strand sort: Difference between revisions

Revision as of 23:43, 11 November 2018

Revision as of 01:52, 5 December 2018

Line 1:

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

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

== Performance ==

Line 63 ⟶ 71:

== Implementation ==

Since Strand Sort requires many insertions and deletions, it is best to use a linked list when implementing strand sort. <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 175 ⟶ 183:

</syntaxhighlight>

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

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

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