Writing a Bubble Sort algorithm

Python Help
1

I am learning algorithmic design and currently working on the most basic sorting algorithm - - Bubble Sort.

Here are two code snippets. My Python interpreter didn’t like either of them.

arr = [5,3,4,1,2]

print(f"Original list: {arr}")

def bubble(arr): 
    for idx1,idx2 in arr:
        if idx1 > idx2:
            temp = arr[idx1]
            arr[idx1] == arr[idx2]
            arr[idx2] = temp
        else:
            continue
    return arr

sorted_list = bubble(arr)

print(f"Final sorted list: {sorted_list}")

Traceback:

$ python script1.py 
Original list: [5, 3, 4, 1, 2]
Traceback (most recent call last):
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Bubble-Sort/script1.py", line 15, in <module>
    sorted_list = bubble(arr)
                  ^^^^^^^^^^^
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Bubble-Sort/script1.py", line 6, in bubble
    for idx1,idx2 in arr:
        ^^^^^^^^^
TypeError: cannot unpack non-iterable int object

Here is a second attempt with the corresponding traceback:

arr = [5,3,4,1,2]

print(f"Original list: {arr}")

def bubble(arr): 
    for iteration in range(0,len(arr)):
        for idx1,idx2 in arr[iteration]::
            if idx1 > idx2:
                temp = arr[idx1]
                arr[idx1] == arr[idx2]
                arr[idx2] = temp
            else:
                continue
    return arr

sorted_list = bubble(arr)

print(f"Final sorted list: {sorted_list}")

$ python script2.py
Original list: [5, 3, 4, 1, 2]
Traceback (most recent call last):
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Bubble-Sort/script2.py", line 16, in <module>
    sorted_list = bubble(arr)
                  ^^^^^^^^^^^
  File "/home/gnull/dev/projects/python/2018-and-2020/algos/Bubble-Sort/script2.py", line 7, in bubble
    for idx1,idx2 in arr:
        ^^^^^^^^^
TypeError: cannot unpack non-iterable int object

I realize I need two for loops. In my first code snippet above there is just one. So that will not do. In my second code snippet I have two for loops, but I am not referring to the two index variable (pointers) properly.

Hints and tips welcome but please avoid solving the entire algorithm for me because that would ruin my educational experience. While I am not taking for-credit courseware at a college or univeristy, I am pretending that I am. So please don’t provide a full solution.

With AI tools at my disposal, I feel like I have a strong grasp over the concept of how a Bubble Sort works in general. I asked both ChatGPT and meta.ai: “Explain a Bubble Sort algorithm using English and no computer code” which turned up some very helpful instructions to work with. My problem is modeling the English functionality in Python syntax.

What comments and suggestions might you people recommend to overcome my tracebacks above and improve my code?

2

You appear to be using equality test (==) in place of assignment (=). Haven’t checked if that’s the cause of your tracebacks.

Also, did you know that in Python you can do

x, y = y, x

eliminating the need for an intermediate variable?

3

The equality test was deliberate because I thought that was required. I changed the quality test instance with assignment operator. The traceback remains.

I have seen Python syntax like you describe in other contexts. I didn’t think to use it. While that suggestion is more elegant and seasoned developers might say such an approach aligns with more Pythonic form, I prefer to keep the intermediate value structure for now because it is just more compatible with my ‘warped’ cerebral thinking patterns. Either technique should work. Perhaps once I overcome the tracebacks and have a working Bubble Sort algorithm, afterwards I can experiment with x, y = y, x for the sake of comparison.

4

There are still problems with it, but this should get you closer to a running code so you can sort it out.

Also, try to execute your code line by line without making it into a function straight away. This will help you see which line fails

3 Likes
5

Thank you @dg-pb .

I have taken your suggested code snippet, made some small changes, and have played around with it in VSC’s Python debugger. The largest number in the list is 5 and as-is, the function successfully ‘bubbles it up’ (moves it) to the end. But the other elements remain in their otherwise original order.

With the equality operator, the function outputs a list where all elements are 5. When I change that line and use the assignment operator, I get better but not the complete desired end result. I also removed the else condition and continue .

When I run the code with my debugger and step through, line by line, I can observe the iteration and i double loop variables start out at 0 and increase, one at time, as each loop progresses. So as far as I can tell, that mechanism is executing as expected.

I am not sure what else to look out for. I mean, I gather that the issue is probably with the way the two el variables and list pointers are positioned and toss around the different list items, but I am not sure what to try next.

Here is the script I am working with now and its corresponding output:

arr = [5,3,4,1,2]

print(f"Original list: {arr}")

def bubble(arr): 
    for iteration in range(0,len(arr)):
        for i in range(iteration):
            el1 = arr[i]
            el2 = arr[i+1]
            if el1 > el2:
                arr[i] = el2
                arr[i+1] = el1
            # else:
            #    continue
    return arr

sorted_list = bubble(arr)

print(f"Final sorted list: {sorted_list}")

$ python Bubble-Sort/script3.py
Original list: [5, 3, 4, 1, 2]
Final sorted list: [3, 1, 4, 2, 5]

Executing the code, line by line makes sense. I have explored the code using my debugger rather than flattening the code outside the function. I am not even sure how that would work. I prefer to stick with the Python debugger.

6

Yeah, equality was a typo. I was hoping you will figure it out yourself. :slight_smile:

There are many tutorials online where you can just copy+paste the code and it will work if you just need a working algorithm. In this case, there is no need to ask for help here.

Otherwise, if you want to become better at algorithms yourself, then someone telling you your mistakes is not beneficial to you. What would be is you actually understanding the algorithm and why it works.

So in both cases, someone helping you with the algorithm here, especially if the problem is not with the python language itself, is not a very productive use of everyone’s time.

A quick fix for your code is… Just replace with this:

for iteration in reversed(range(len(arr))):
7

In my OP I said this:

I specifically asked forum members not to provide the solution. In your first comment, you wrote a solution which was 80%-90% of the full answer. When I first saw your comment, I looked away. My first reaction was to ask you to either delete or hide or modify. But instead I just took it and ran with it. In retrospect, I shouldn’t have.

That’s a good suggestion because with such easy access to solutions on Google but also considering this new world of generative AI where working algorithms are so accessible, focusing on “understanding the why” makes sense. But then I am not writing my own code, I am just reading code.

Even with perfect solutions that I don’t write myself that I find elsewhere online, I suppose I can use my Python debugger to explore them further. But even then I don’t always understand every line or why the algorithm is behaving the way it is, in which case I can continue learning by using the “rubber ducky technique” and then continuing to ask follow up questions in online forums.

This comment strikes me as slightly unusual because while algorithmic design in general and my question specifically here is platform / language agnostic, I would think that most online forums for any language would still welcome novice users like myself to ask questions even if the questions are about programming in general or programming-adjacent topics. I think most mods on this message board would agree that my questions here about algorithms implemented in Python are valid, relevant, and on topic. By telling me to ask elsewhere seems misplaced.

Other forum members in many other threads I’ve created in the past have replied to my questions about incomplete or non-working algorithms I’ve written by providing feedback in many ways including pointing out problem areas and sharing hints and tips instead of the full solution. This is pretty standard. I think that is a fair expectation.

8

I missed your request to “not give full solution”.

I was just suggesting that it might not be a very good learning strategy, but if it works for you and others, then I don’t see any problem.