FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

algorithms-python/algorithms/sort/comb_sort.py at master · Mu-L/algorithms-python · GitHub

32 lines (25 loc) · 572 Bytes

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

"""

https://en.wikipedia.org/wiki/Comb_sort

Worst-case performance: O(N^2)

"""

def comb_sort(arr):

def swap(i, j):

arr[i], arr[j] = arr[j], arr[i]

n = len(arr)

gap = n

shrink = 1.3

sorted = False

while not sorted:

gap = int(gap / shrink)

if gap > 1:

sorted = False

else:

gap = 1

sorted = True

i = 0

while i + gap < n:

if arr[i] > arr[i + gap]:

swap(i, i + gap)

sorted = False

i = i + 1

return arr

Back | FazBrowse Home | New Git URL