strand sort Algorithm
The Strand Sort Algorithm is an adaptive sorting algorithm that works efficiently on partially sorted input data. It was developed to optimize the sorting process by identifying and organizing the already sorted subsequences or "strands" within the original unsorted data. The algorithm operates by iterating through the input data and comparing each element with its adjacent element. If the current element is less than or equal to the adjacent element, both elements are considered part of the same strand. This process continues until all the elements of the input data have been traversed and sorted into their respective strands. The sorted strands are then merged together to produce the final sorted output.
The primary advantage of the Strand Sort Algorithm is its adaptability to the input data, which allows it to perform well on partially sorted datasets. The algorithm has a best-case time complexity of O(n) when the input data is already sorted or nearly sorted. However, in the worst-case scenario, when the input data is sorted in reverse order, the time complexity increases to O(n^2). This makes Strand Sort less suitable for large datasets or those with a high degree of disorder. Despite its limitations, the algorithm remains an interesting and useful approach for specific scenarios where the data is expected to have a significant amount of pre-sorted elements.
import operator
def strand_sort(arr: list, reverse: bool = False, solution: list = None) -> list:
"""
Strand sort implementation
source: https://en.wikipedia.org/wiki/Strand_sort
:param arr: Unordered input list
:param reverse: Descent ordering flag
:param solution: Ordered items container
Examples:
>>> strand_sort([4, 2, 5, 3, 0, 1])
[0, 1, 2, 3, 4, 5]
>>> strand_sort([4, 2, 5, 3, 0, 1], reverse=True)
[5, 4, 3, 2, 1, 0]
"""
_operator = operator.lt if reverse else operator.gt
solution = solution or []
if not arr:
return solution
sublist = [arr.pop(0)]
for i, item in enumerate(arr):
if _operator(item, sublist[-1]):
sublist.append(item)
arr.pop(i)
# merging sublist into solution list
if not solution:
solution.extend(sublist)
else:
while sublist:
item = sublist.pop(0)
for i, xx in enumerate(solution):
if not _operator(item, xx):
solution.insert(i, item)
break
else:
solution.append(item)
strand_sort(arr, reverse, solution)
return solution
if __name__ == "__main__":
assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]
