FilesExpand file tree

Write-for-current-Python

/

cycle_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (39 loc) · 1.22 KB

Write-for-current-Python

/

cycle_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (39 loc) · 1.22 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

"""

Code contributed by Honey Sharma

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

"""

def cycle_sort(array: list) -> list:

"""

>>> cycle_sort([4, 3, 2, 1])

[1, 2, 3, 4]

>>> cycle_sort([-4, 20, 0, -50, 100, -1])

[-50, -4, -1, 0, 20, 100]

>>> cycle_sort([-.1, -.2, 1.3, -.8])

[-0.8, -0.2, -0.1, 1.3]

>>> cycle_sort([])

[]

"""

array_len = len(array)

for cycle_start in range(0, array_len - 1):

item = array[cycle_start]

pos = cycle_start

for i in range(cycle_start + 1, array_len):

if array[i] < item:

pos += 1

if pos == cycle_start:

continue

while item == array[pos]:

pos += 1

array[pos], item = item, array[pos]

while pos != cycle_start:

pos = cycle_start

for i in range(cycle_start + 1, array_len):

if array[i] < item:

pos += 1

while item == array[pos]:

pos += 1

array[pos], item = item, array[pos]

return array

if __name__ == "__main__":

assert cycle_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]

assert cycle_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]