+ 9

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

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

28th Nov 2018, 2:19 AM
LONGTIE👔
LONGTIE👔 - avatar
9 Antworten
+ 12
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?
28th Nov 2018, 5:05 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 7
Kishalaya Saha thank you so much for helping me 😃😄. you are a super hero ✌👍🤗.
2nd Dec 2018, 4:35 AM
LONGTIE👔
LONGTIE👔 - avatar
2nd Dec 2018, 3:35 AM
LONGTIE👔
LONGTIE👔 - avatar
+ 4
Kishalaya Saha Mayur Garg Question is updated
28th Nov 2018, 11:06 PM
LONGTIE👔
LONGTIE👔 - avatar
+ 3
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 😊
29th Nov 2018, 2:20 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 2
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.
28th Nov 2018, 8:17 AM
Mayur Garg
Mayur Garg - avatar
+ 2
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 :)
2nd Dec 2018, 4:05 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 2
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.
2nd Dec 2018, 4:13 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 2
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.
2nd Dec 2018, 4:39 AM
Kishalaya Saha
Kishalaya Saha - avatar