strand_sort.py

importoperator


defstrand_sort(arr: list, reverse: bool=False, solution: list|None=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.ltifreverseelseoperator.gt
solution=solutionor []

ifnotarr:
returnsolution

sublist= [arr.pop(0)]
fori, iteminenumerate(arr):
if_operator(item, sublist[-1]):
sublist.append(item)
arr.pop(i)

# merging sublist into solution list
ifnotsolution:
solution.extend(sublist)
else:
whilesublist:
item=sublist.pop(0)
fori, xxinenumerate(solution):
ifnot_operator(item, xx):
solution.insert(i, item)
break
else:
solution.append(item)

strand_sort(arr, reverse, solution)
returnsolution


if__name__=="__main__":
assertstrand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
assertstrand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]