Content deleted Content added
Friedlemon (talk | contribs) Reverting edit(s) by 2001:16B8:67C7:7E00:8845:CC15:5447:12B3 (talk) to rev. 954892336 by Citation bot: Unexplained content removal (RW 15) |
m Replaced incorrect citation with citation needed. Tag: references removed |
||
Line 1:
[[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 [[Big O notation|O]](n<sup>2</sup>) worst 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 O(n) which occurs when the input is a list that is already sorted.
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>
| |||