[Need Opinion]Comb Sort Visualization 👀

Processing.py
1 
width = 1000
height = width / 2

l = 10
num = width / l
h = []
gap = int(num * 0.7)
count = 0

def setup():
    size(width,height)
    for i in range(num):
        h.append(map(i,0,num,0,height))
    shuffl()
    
def draw():
    global count,gap
    background(0)
    for i in range(num):
        if count < num - gap:
            if h[count] > h[count + gap]:
                print("swap")
                h[count],h[count + gap] = h[count + gap],h[count]
        else:
            count = 0
            gap = gapper(gap)
        if i == count or i == count + gap:
            fill(255,0,0)
        else:
            fill(255)
        rect(i*10,height - h[i],l,h[i])
    count += 1
    
def gapper(gap):
    gap = int(gap*0.7)
    if gap > 0:
        return gap
    return 1
    
def shuffl():
    for i in range(num):
        for j in range(num):
            a = int(random(num))
            h[j],h[a] = h[a],h[j]

I simplified my code a lot, everything works, I believe, but I feel like something is wrong, my final part is worse than bubblesort, is this how the algorithm works or I lost something during the ‘coversion’ of the sort for Processing?

2

What do you mean by this? Are you timing it or counting steps? By “final part” do you mean the last pass? Worse how?

If implemented correctly, the last pass of comb sort should be at gap 1, so it should be identical to a bubblesort pass – not better or worse, just the same. Comb sort implements a pre-sort at different gaps (the comb) to eliminate turtles (low values at the end of the list), so that the final bubble sort is more efficient. So, if you have turtles (e.g. a worst-case list for bubble-sort: 9, 8, 7, 6, 5, 4, 3, 2, 1), then comb sort will speed up the process substantially. If it doesn’t, you haven’t implemented the algorithm correctly.

However, in the very best case for bubble sort (1, 2, 3, 4, 5, 6, 7, 8, 9) then comb sort will be slower, because it will check those different gapped value comparisons before doing the final pass – where bubble sort would just do it in one pass and be done.

1 Like