Content deleted Content added
m Vycl1994 moved page Strand Sort to Strand sort: WP:TITLECASE per WP:LEDE |
uncategorized |
||
Line 1:
[[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 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|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" />
Line 15:
'''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.
▲* 4 < 5 so 4 is not added to the sub-list.
* 2 < 5 so 2 is not added to the sub-list.
▲* 0 < 5 so 0 is not added to the sub-list.
* 9 > 5 so 9 is added to the sub-list and 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.
▲* 8 < 9 so 8 is not added to the sub-list.
▲* 7 < 9 so 7 is not added to the sub-list.
After step 5, the original list contains {1, 4, 2, 0, 6, 3, 8, 7}
Line 43 ⟶ 36:
'''Step 6:''' Move the first element of the original list into sub-list: sub-list contains {1}
'''Step 7:''' Iterate through the original list and compare each number to 1 until there is a number greater than 1.
* 4 > 1 so 4 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.
'''Step 10:''' Now compare 8 with the remaining elements in the original list until there is a number greater than 8.
* 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 the original list contains {2, 0, 3, 7}, the sub-list is empty and the solution-list contains: {1, 4, 5, 6, 8, 9}.
Line 69 ⟶ 59:
'''Step 12:''' Move the first element of the original list into sub-list. Sub-list contains {2}
'''Step 13:''' Iterate through the original list and compare each number to 2 until there is a number greater than 2.
▲* 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 ==
Line 203 ⟶ 192:
<!-- 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}}
{{uncategorized|date=May 2019}}
| |||