Skip to content

Instantly share code, notes, and snippets.

@IrSent
Created April 4, 2017 07:33
Show Gist options
  • Save IrSent/4077098f0265a76e2f9fb1888fb05e2e to your computer and use it in GitHub Desktop.
Save IrSent/4077098f0265a76e2f9fb1888fb05e2e to your computer and use it in GitHub Desktop.
Comb sort
# -​*- coding: utf-8 -*​-
from __future__ import unicode_literals, print_function
import random
def random_list(start=1, stop=1001, length=1000):
if stop <= length:
raise ValueError('stop value must be greater than length')
else:
return random.sample(xrange(start,stop), length)
def comb_sort(lst=random_list()):
# print(str(lst[:10]), '...')
shrink_factor, gap, passes, swaps, done = 1.247, len(lst), 0, 0, False
while not done:
passes += 1
gap = int(gap / shrink_factor)
done, gap = (False, gap) if gap > 1 else (True, 1)
i = 0
while i + gap < len(lst):
if lst[i] > lst[i + gap]:
lst[i], lst[i + gap] = lst[i + gap], lst[i]
swaps += 1
done = False
i += 1
# print('Passes:', passes, 'Swaps:', swaps)
# print(str(lst[:10]), '...')
# O(n log n)
# 1k elements:
# Passes: 28, Swaps: 4208
# 10k elements:
# Passes: 39, Swaps: 59558
# 100k elements:
# Passes: 49, Swaps: 789620
# 1kk elements:
# Passes: 61, Swaps: 9680764
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment