[SOLVED] is this the proper way to do a bubble sort algorithm?

Question

https://code.sololearn.com/cKeJ6iaoFErV/?ref=app
now ive a new code and is this one right?

https://code.sololearn.com/ctqtv9X8StMq/?ref=app

Answer 1

It certainly sorts the list, but it's not exactly bubble sort. It has some redundant comparisons. Please allow me to illustrate with a reverse-sorted initial list: [5, 4, 3, 2, 1]

Compare 5 and 4. Swap.
[4, 5, 3, 2, 1]
Compare 4 and 5 (again). Don't Swap.
Compare 5 and 3. Swap.
[4, 3, 5, 2, 1]
Compare 4 and 3. Swap.
[3, 4, 5, 2, 1]
Compare 4 and 5 (again). Don't Swap.
Compare 5 and 2. Swap.
[3, 4, 2, 5, 1]
Compare 3 and 4 (again). Don't Swap.
Compare 4 and 2. Swap.
[3, 2, 4, 5, 1]
Compare 3 and 2. Swap.
[2, 3, 4, 5, 1]
Compare 3 and 4 (again). Don't Swap.
Compare 4 and 5 (again). Don't Swap.
...
...
...

Have you started to see the issue? Just to get the first four elements in the original list in the right order, you compare 4 and 5 four times. It's possible to make your code more efficient by avoiding all these redundant comparisons. Then it would not exactly be bubble sort, but something close. You, my friend, have rediscovered insertion sort:
https://en.wikipedia.org/wiki/Insertion_sort

Bubble sort is slightly different. It goes like this:
Initial list: [4, 3, 2, 1]
[3, 4, 2, 1]
[3, 2, 4, 1]
[3, 2, 1, 4]
(First sweep through the list is complete. The last element is in the right position. We won't look at it any more.)
[2, 3, 1, 4]
[2, 1, 3, 4]
(Second sweep complete. Last two elements in right position.)
[1, 2, 3, 4]
(Third sweep complete. DONE!)

Reference: https://en.wikipedia.org/wiki/Bubble_sort

Check out the .gif in both wiki links. Can you code it now?

Answer 2

Kishalaya Saha thank you so much for helping me 😃😄.

you are a super hero ✌👍🤗.

Answer 3

Kishalaya Saha take 3 😁

https://code.sololearn.com/c2kd1qKt5nlv/?ref=app

Answer 4

Kishalaya Saha
Mayur Garg
Question is updated

Answer 5

In bubble sort,
1. We're always supposed to compare consecutive elements. Your x and y don't necessarily differ by one.
2. After the first sweep through the list, the last element is in the correct position, so we ignore it for the next sweep. After the second sweep, the second-to-last element is in the correct position, and we ignore it for the third sweep, and so on. So the index of the outer loop also determines how far we'll scan in each sweep.

Try again 😊

Answer 6

Along with what Kishalaya Saha mentioned, you can also set up a flag variable which is activated if there is a swap in the loop and else not. If after a loop, the flag isn't activated, you can safely assume that the list is now sorted and break out of the loop. This will highly optimise you code for almost sorted lists.

Answer 7

Excellent! Now that's a bubble sort! 😊

Just some finishing touches to save lines. Instead of y, we can directly use x-1. But as you noticed, that creates an issue when x==0. But not to worry, we'd just start with x==1 by changing line 15 to
for x in range(1, decr):

Hope that makes sense :)

Answer 8

Another variable you might consider getting rid of is decr. In line 15, you can directly write
for x in range(1, len(list1)-i):

Because that's how decr and i are related: for the i-th outer loop (i starting with 0), we ignore the last i elements.

Answer 9

Haha, thanks! It's my pleasure really!

Now it may be a good idea to compare your code with the "official" Sololearn Python algorithm:
https://www.sololearn.com/learn/701/?ref=app

Try to understand the differences, and let me know if anything confuses you.