Python Forum
Question about Python Code
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Question about Python Code
#11
Okay,thanks I got it! Cheers!

As the hint suggests, let’s create a simple input list with values {4, 2, 3, 1} and see what happens on each step.
1: stop is set to the number of items in list - 2, which is 4 - 2 = 2
2: we start looping and set item to the first element of the list, which is 4
3: we have another loop with i set to 0
4: we see if list[0] > list[1], which sees if 4 > 2, which is true
6: the variable temp holds list[0], which is 4
7: list[0] is set to list[1], which is 2, which means our list now contains {2, 2, 3, 1}
8: list[1] is set to temp, which is 4, so our list is now {2, 4, 3, 1}
3: we continue with the inner loop, with i now set to 1
4: we see if list[1] > list[2], which sees if 4 > 3, which is true
6: the variable temp holds list[1], which is 4
7: list[1] is set to list[2], which is 3, so now the list is {2, 3, 3, 1}
8: list[2] is set to temp, which is 4, so the list becomes {2, 3, 4, 1}
3: we continue the inner loop, with i now set to 2; note that because stop is 2, this is the last time we will execute this inner loop
4: we see if list[2] > list[3], which sees if 4 > 1, which is true
6: temp holds list[2], which is 4
7: list[2] is set to list[3], so the list is now {2, 3, 1, 1}
8: list[3] is set to temp, which is 4, so the list becomes {2, 3, 1, 4}
At this point it may be possible to speculate what this algorithm does after just one pass through the outer loop, but let’s do the outer loop one more time just to check.
Let’s simplify things a bit, though, and note that lines 6-8 simply switch the values of list[i] and list[i+1]; we won’t walk through all three of those steps as we continue the example.
Now that we’ve completed the inner loop, we continue the outer loop, keeping in mind that list is now {2, 3, 1, 4}:
2: we continue looping and set item to the next element of the list, which is 3; note that item is not actually used anywhere other than line 2. All this does is ensure that the loop on lines 3-8 is executed the same number of times as there are items in the list.
3: we restart the inner loop with i set to 0
4: we see if list[0] > list[1], which sees if 2 > 3, which is false, so we do not execute lines 6-8
3: we continue with the inner loop, with i now set to 1
4: we see if list[1] > list[2], which sees if 3 > 1, which is true
6-8: we swap list[1] and list[2], so the list now becomes {2, 1, 3, 4}
3: we continue the inner loop, with i now set to 2
4: we see if list[2] > list[3], which sees if 3 > 4, which is false, so we do not execute lines 6-8, and because i reached the value of stop, we are done with the inner loop
Now the list is {2, 1, 3, 4}. Can you see what is happening? Let’s try one more:
2: we continue looping for the third time
3: we restart the inner loop with i set to 0
4: we see if list[0] > list[1], which sees if 2 > 1, which is true
6-8: we swap list[0] and list[1], so the list is now {1, 2, 3, 4}
3: we continue looping with i set to 1
4: we see if list[1] > list[2], which sees if 2 > 3, which is false
3: we continue looping with i set to 2
4: we see if list[2] > list[3], which sees if 3 > 4, which is false

Now we’re done with the inner loop and the list is {1, 2, 3, 4}. We do have one more iteration of the outer loop to perform, but we’ll stop here because perhaps you see what’s happening: as we go through the inner loop, bigger numbers are being swapped with neighboring smaller numbers so that the bigger numbers are moving to the right. Each time we do the outer loop, the biggest number moves all the way to the right, up until it hits the numbers that are bigger than it. The result is that the numbers end up in sorted order.
This algorithm is known as bubble sort and is one of the simplest algorithms for sorting elements in a list. It is called bubble sort because on each iteration of the outer loop, the largest value “bubbles” its way to the top (or to the right), until it reaches its place in the sorted list.

Although bubble sort is simple to implement, it is very inefficient and exhibits quadratic complexity, meaning that an input of N elements would require around N2^22 operations, and that doubling the input’s size would require four times as many operations. The most efficient sorting algorithms, such as merge sort and quick sort, require NlogN operations, which are much fewer than N2^22 for large values of N, but are more complicated to implement.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  How to Use Python for solving the following physics question. Python Code required ishahid 8 3,538 Dec-18-2019, 06:59 AM
Last Post: akashraj128

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020