Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python Bubble Sort list with swap count

Tags:

python

sorting

I'm trying to make a function that sorts a list using bubble sorting and returns a tuple with the number of swaps and comparisons. Such that:

print(perform_bubble_sort([3, 5, 7]))    
>>> (3, 0)

.
I tried using the following code but it doesn't return the right number of comparisons for some reason.

def perform_bubble_sort(blist):
    cmpcount, swapcount = 0, 0
    while True:
        swapped = False
        for i in range(1, len(blist)):
            cmpcount += 1
            if blist[i-1] > blist[i]:
                swapcount += 1
                blist[i-1], blist[i] = blist[i], blist[i-1]
                swapped = True
        if not swapped:
            break
    return cmpcount, swapcount
like image 235
Newbie Avatar asked Mar 18 '23 04:03

Newbie


1 Answers

def perform_bubble_sort(blist):
    cmpcount, swapcount = 0, 0
    for j in range(len(blist)):
        for i in range(1, len(blist)-j):
            cmpcount += 1
            if blist[i-1] > blist[i]:
                swapcount += 1
                blist[i-1], blist[i] = blist[i], blist[i-1]
    return cmpcount, swapcount

You don't need to iterate over blist every time

like image 61
laike9m Avatar answered Mar 26 '23 01:03

laike9m