Comb sort

comb_sort.py

# -​*- 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