Do you know why my bubblesort isn't working? [Python]

Question

I am trying to make a bubblesort in python from scratch, do you know why it is not working? I am getting the error list index out of range.

data = [1, 32, 50, 12, 14, 7, 45, 27, 18, 9, 19, 22, 51, 42, 4, 25, 13, 6, 21, 49, 41, 37]

def bubbleSort(alist):
    length = len(alist)
    for i in range(length):
        first = alist[i]
        second = alist[i + 1]
        if first > second:
            a, b = alist.index(first), alist.index(second)
            alist[b], alist[a] = alist[a], alist[b]


    return data

print(bubbleSort(data))

Thanks, Scott

There's no need to call `alist.index(...` in that line. The indexes are `i` and `i+1`, since you used them earlier. `index` can also fail with duplicates — TerryA, Jan 19 '18 at 08:53
Correcting the `index out of range` error won't make this a working bubblesort program. You might want to change your headline. — Mr. T, Jan 19 '18 at 09:05

score 1 · Answer 1 · answered Jan 19 '18 at 08:52

1

change your loop to:

for i in range(length-1):

since you grab alist[i + 1] max i should be 2 less than length of list

answered Jan 19 '18 at 08:52

Karan Shishoo

2,402
2
17
32

score 1 · Answer 2 · answered Jan 19 '18 at 08:52

1

Check if you've handled the case for last element.

    first = alist[i]
    second = alist[i + 1]

The second line uses i+1. So, when i points to the last index of the list, the second element alist[i+1] seems to be out of list index.

answered Jan 19 '18 at 08:52

Anuj Gautam

1,235
1
7
14

score 0 · Answer 3 · answered Jan 19 '18 at 08:56

0

Found the fix:

data = [1, 32, 50, 12, 14, 7, 45, 27, 18, 9, 19, 22, 51, 42, 4, 25, 13, 6, 21, 49, 41, 37]

def bubbleSort(alist):
    length = len(alist) - 1
    while sorted(alist) != alist:
        for i in range(length):
            first = alist[i]
            second = alist[i + 1]
            if first > second:
                a, b = alist.index(first), alist.index(second)
                alist[b], alist[a] = alist[a], alist[b]


    return data

print(bubbleSort(data))

answered Jan 19 '18 at 08:56

Scott Watson

1

1) You put the desired output into the condition of the `while` loop? 2) You sort each time the `alist`, when executing this loop? – Mr. T Jan 19 '18 at 09:01
This makes no sense at all. You're calling an external sort function to determine when to terminate your loop. Why?? Wouldn't you consider that "cheating"? And the use of `index` is changing an O(n\*\*2) algorithm into an O(n\*\*3) algorithm. You haven't implemented bubble sort. Not even close. – Tom Karzes Jan 19 '18 at 09:04
Actually, given that the call to `sorted` is itself O(n*log(n)), I'd say you've implemented an O(n\*\*2*log(n)) sort which uses the builtin sort function as an integral part of the algorithm. Why not just return the result of `sorted` directly? – Tom Karzes Jan 19 '18 at 09:09

Do you know why my bubblesort isn't working? [Python]

3 Answers3