iframe-proxy | Sunbelt Computer Software

History

51 lines (40 loc) · 1.34 KB

Raw

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]

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

strand_sort.py

Latest commit

History

strand_sort.py

File metadata and controls