FilesExpand file tree

Write-for-current-Python

/

slowsort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (50 loc) · 1.77 KB

Write-for-current-Python

/

slowsort.py

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (50 loc) · 1.77 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

"""

Slowsort is a sorting algorithm. It is of humorous nature and not useful.

It's based on the principle of multiply and surrender,

a tongue-in-cheek joke of divide and conquer.

It was published in 1986 by Andrei Broder and Jorge Stolfi

in their paper Pessimal Algorithms and Simplexity Analysis

(a parody of optimal algorithms and complexity analysis).

Source: https://en.wikipedia.org/wiki/Slowsort

"""

from typing import Optional

def slowsort(

sequence: list, start: Optional[int] = None, end: Optional[int] = None

) -> None:

"""

Sorts sequence[start..end] (both inclusive) in-place.

start defaults to 0 if not given.

end defaults to len(sequence) - 1 if not given.

It returns None.

>>> seq = [1, 6, 2, 5, 3, 4, 4, 5]; slowsort(seq); seq

[1, 2, 3, 4, 4, 5, 5, 6]

>>> seq = []; slowsort(seq); seq

[]

>>> seq = [2]; slowsort(seq); seq

[2]

>>> seq = [1, 2, 3, 4]; slowsort(seq); seq

[1, 2, 3, 4]

>>> seq = [4, 3, 2, 1]; slowsort(seq); seq

[1, 2, 3, 4]

>>> seq = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]; slowsort(seq, 2, 7); seq

[9, 8, 2, 3, 4, 5, 6, 7, 1, 0]

>>> seq = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]; slowsort(seq, end = 4); seq

[5, 6, 7, 8, 9, 4, 3, 2, 1, 0]

>>> seq = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]; slowsort(seq, start = 5); seq

[9, 8, 7, 6, 5, 0, 1, 2, 3, 4]

"""

if start is None:

start = 0

if end is None:

end = len(sequence) - 1

if start >= end:

return

mid = (start + end) // 2

slowsort(sequence, start, mid)

slowsort(sequence, mid + 1, end)

if sequence[end] < sequence[mid]:

sequence[end], sequence[mid] = sequence[mid], sequence[end]

slowsort(sequence, start, end - 1)

if __name__ == "__main__":

from doctest import testmod

testmod()