Content deleted Content added
Added a section for the performance of the algorithm |
Added a step by step example on how the algorithm works |
||
Line 3:
== Performance ==
Strand sort has a worst case [[time complexity]] of O(n<sup>2</sup>) 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" />
== Example ==
Based off of the description of the algorithm provided in the book''IT enabled practices and emerging management paradigms''.
Step 1: Start with a list of numbers: {13, 7, 19, 6, 25, 29, 1, 4 }
Step 2: Next move the first element of the list into a new sub-list: sub-list contains {13}
Step 3: Then iterate through the original list and compare each number to 13 until there is a number greater than 13.
2 < 13 so 7 is not added to the sub-list. 19 > 13 so 19 is added to the list.
Step 4: Now compare 19 with the remaining elements in the original list until there is a number greater than 19.
6 < 19 so 6 is not added to the list. 25 > 19 so 25 is 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 > 25 so 29 is added to the sub-list.
Step 6: Now compare 29 to the remaining elements in the original list until there is a number greater than 29.
29 > 1 so 1 is not added to the sub-list. 29 > 4 so 4 is not added to the sub-list.
Step 7: Merge the sub-list into a new list, called solution-list.
After step 7, the original list contains {7, 6, 1, 4}
The sub-list is empty, and the solution list contains {13, 19, 25, 19}
Step 8: Move the first element of the original list into sub-list: sub-list contains {7}
Step 9: Iterate through the original list and compare each number to 7 until there is a number greater than 7.
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 10: Merge sub-list with solution-list. Now sub-list is empty and solution-list contains: {7, 13, 19, 25, 19}.
Step 11: Move the first element of the original list into sub-list. Sub-list contains {6}
Step 12: Iterate through the original list and compare each number to 6 until there is a number greater than 6.
1 < 6 so 1 is not added to the sub-list. 4 < 6 so 4 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. The solution list now contains: {6, 7, 13, 19, 25, 19}.
Step 14: Move the first element of the original list into sub-list. Sub-list contains {1}
Step 15: 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.
Step 15: Since there are no more elements in the original list to compare {4} to, the sub-list is merged with the solution list. The solution list now contains: {1,4, 6, 7, 13, 19, 25, 19}. There are now more elements in the original list, and all of the elements in the solution list have successfully been sorted into increasing numerical order.
{{AFC submission|t||ts=20181106150605|u=Heldw|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->
| |||