Skip to content

Instantly share code, notes, and snippets.

@robertDurst robertDurst/comparison.py
Last active Nov 3, 2019

Embed
What would you like to do?
Bubble Sort vs. Comb Sort
import random
import cProfile
def swap(arr, a, b):
arr[a], arr[b] = arr[b], arr[a]
def getNextGap(gap):
gap = (gap * 10) / 13
if gap < 1:
return 1
return int(gap)
def combsort(nums):
n, gap, swapped = len(nums), len(nums), True
while gap != 1 or swapped == True:
gap, swapped = getNextGap(gap), False
for i in range(0, n - gap):
if nums[i] > nums[i + gap]:
swap(nums, i, i + gap)
swapped = True
return nums
def bubblesort(nums):
n = len(nums)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if nums[j] > nums[j+1]:
swap(nums, j, j+1)
swapped = True
# short circuit here to be fair with the above
# implementation of comb sort
if not swapped:
return nums
return nums
unsorted = []
for i in range(0, 10000):
unsorted.append(i)
random.shuffle(unsorted)
# copy the arrays
a = unsorted[:]
b = unsorted[:]
# profile
cProfile.run("combsort(a)")
cProfile.run("bubblesort(b)")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.