0

I am new to Python and learning data structure in Python. I am trying to implement a bubble sort algorithm in python and I did well but I was not getting a correct result. Then I found some tutorial and there I saw that they are first setting a base range for checking.

So the syntax of range in python is:

range([start], stop[, step])

And the bubble sort algorithm is:

def bubbleSort(alist):

   for i in range(len(alist) - 1, 0, -1):
       for j in range(i):

           if alist[j] > alist[j+1]:
               temp = alist[j]
               alist[j] = alist[j+1]
               alist[j+1] = temp

   return alist

print(bubbleSort([5, 1, 2, 3, 9, 8, 0]))

I understood all the other logic of the algorithm but I am not able to get why the loop is starting from the end of the list and going till first element of the list:

for i in range(len(alist) - 1, 0, -1):

Why is this traversing the list in reverse? The main purpose of this loop is setting the range condition only so why can't we traverse from the first element to len(list) - 1 like this:

for i in range(0, len(alist) - 1, 1):
poke
  • 369,085
  • 72
  • 557
  • 602
  • 1
    This is python code that is clearly written by somebody who thinks they're still writing C code(the for loops are modeled after C for loops, even though python for loops are more flexible). Basically the `i` index is just keeping track of the number of unsorted items left in the list. I'd suggest looking at other bubble sort implementations to get a more 'pythonic' view of the algorithm. – Charles D Pantoga Sep 19 '17 at 06:41
  • @CharlesAddis Apart from the swapping part, what exactly would you change there? – poke Sep 19 '17 at 06:47
  • @poke the for loops... the outer loop can be a while loop with a sentinel value `sorted`... there are more than one way to implement bubble sort in python. See the first answer in this question: https://stackoverflow.com/questions/895371/bubble-sort-homework – Charles D Pantoga Sep 19 '17 at 06:54
  • @CharlesAddis There is *nothing* about a while loop and a boolean that makes any of that more pythonic. I would argue that while loops are the least pythonic construct in the language. – Using a boolean would be equally possible in literally *any* other language but the reason why you don’t want that is exactly what this question is about: To avoid iterating the already sorted list for approximately half of time. – poke Sep 19 '17 at 06:56
  • @poke that link wasn't meant to provide a "perfect" implementation of what I'm talking about. There are MULTIPLE ways to implement bubble sort in python. There is no need for the range at all if you use `enumerate`, and calling range on the length of an iterable (or variants of calling range on an iterable) are some of the most egregious sins against pythonic dogma... and "to avoid iterating the already sorted list for approximately half the time"... sheesh. A "fully optimized" sorting algorithm will account for cases where the list is already sorted `if sorted(alist): return alist` – Charles D Pantoga Sep 19 '17 at 07:01
  • Or `while not sorted(alist)` - there is your sentinel and you didn't need to store it in a boolean because it came from the builtins package. – Charles D Pantoga Sep 19 '17 at 07:05
  • @CharlesAddis I asked you for an explanation what exactly you would change to make it more pythonic, and you gave me an inferior and less pythonic example and again stated that it’s about those differences. What exactly am I supposed to believe you are talking about then? – I’d actually say there are only approximately a handful of acceptable ways to implement bubble sort; none of them will be very pythonic because sort algorithms are supposed to be very low-level, and outside of learning you wouldn’t want to implement sorting in Python anyway since we have a far superior algorithm built-in. – poke Sep 19 '17 at 07:07
  • @CharlesAddis `while not sorted(alist):` would be true for any empty list and vice versa, always. `sorted()` sorts. – Ilja Everilä Sep 19 '17 at 07:07
  • @CharlesAddis `not sorted(alist)` will **never** be true for non-empty lists, and `sorted` will actually *sort* the list so you’ve just added an incredibly high complexity there, apparently without understanding what it does. Even if `sorted()` would check whether a list is sorted, this would increase the complexity a lot since you would iterate the list once more for every iteration. – poke Sep 19 '17 at 07:10
  • Iterating a list more "increases the complexity"? It would not effect the worst case analysis at all since you drop the coefficients... – Charles D Pantoga Sep 19 '17 at 07:15
  • @CharlesAddis Nitpicking on word choice there… the code of this question is all about optimizing the iteration count, if you were to iterate the whole list once for every outer loop iteration to figure out whether it’s already sorted, you would be wasting everything you’ve tried to accomplish. – poke Sep 19 '17 at 07:31
  • And if sorted checked whether the list was sorted, it would not iterate the entire list during each iteration, it would only iterate until it found a value out of place, meaning it would would only iterate the entire list when the list is fully sorted, otherwise it will be only iterating part of the list. Doesn't change the worst case complexity at all, through asymptotic analysis. It's not the most optimized impl. but that wasn't the point of the question at all, nor was it the point of me saying there are more pythonic ways. Highly optimized Python code is not going to be very pythonic. – Charles D Pantoga Sep 19 '17 at 07:48

4 Answers4

2

In your code, the index i is the largest index that the inner loop will consider when swapping the elements. The way bubble sort works is by swapping sibling elements to move the largest element to the right.

This means that after the first outer iteration (or the first full cycle of the inner loop), the largest element of your list is positioned at the far end of the list. So it’s already in its correct place and does not need to be considered again. That’s why for the next iteration, i is one less to skip the last element and only look at the items 0..len(lst)-1.

Then in the next iteration, the last two elements will be sorted correctly, so it only needs to look at the item 0..len(lst)-2, and so on.

So you want to decrement i since more and more elements at the end of the list will be already in its correct position and don’t need to be looked at any longer. You don’t have to do that; you could also just always have the inner loop go up to the very end but you don’t need to, so you can skip a few iterations by not doing it.

I asked why we are going reverse in the list like len(list)-1,0. Why are we not going forward way like 0,len(list)-1?

I was hoping that the above explanation would already cover that but let’s go into detail. Try adding a print(i, alist) at the end of the outer loop. So you get the result for every iteration of i:

>>> bubbleSort([5, 1, 3, 9, 2, 8, 0])
6 [1, 3, 5, 2, 8, 0, 9]
5 [1, 3, 2, 5, 0, 8, 9]
4 [1, 2, 3, 0, 5, 8, 9]
3 [1, 2, 0, 3, 5, 8, 9]
2 [1, 0, 2, 3, 5, 8, 9]
1 [0, 1, 2, 3, 5, 8, 9]

As you can see, the list will be sorted from the right to the left. This works well for our index i which will limit how far the inner loop will go: For i = 4 for example, we already have 3 sorted elements at the end, so the inner loop will only have to look at the first 4 elements.

Now, let’s try changing the range to go in the other direction. The loop will be for i in range(0, len(alist)). Then we get this result:

>>> bubbleSort([5, 1, 3, 9, 2, 8, 0])
0 [5, 1, 3, 9, 2, 8, 0]
1 [1, 5, 3, 9, 2, 8, 0]
2 [1, 3, 5, 9, 2, 8, 0]
3 [1, 3, 5, 9, 2, 8, 0]
4 [1, 3, 5, 2, 9, 8, 0]
5 [1, 3, 2, 5, 8, 9, 0]
6 [1, 2, 3, 5, 8, 0, 9]

As you can see, this is not sorted at all. But why? i still limits how far the inner loop will go, so at i = 1, the loop will only look at the first pair and sort that; the rest will stay the same. At i = 2, the loop will look at the first two pairs and swap those (once!); the rest will stay the same. And so on. By the time the inner loop can reach the last element (which is only on the final iteration), there aren’t enough iterations left to swap the zero (which also happens to be the smallest element) to the very left.

This is again because bubble sort works by sorting the largest elements to the rightmost side first. So we have to start the algorithm by making the inner loop be able to reach that right side completely. Only when we are certain that those elements are in the right position, we can stop going that far.

There is one way to use a incrementing outer loop: By sorting the smallest elements first. But this also means that we have to start the inner loop on the far right side to make sure that we check all elements as we look for the smallest element. So we really have to make those loops go in the opposite directions.

poke
  • 369,085
  • 72
  • 557
  • 602
  • awesome , its more clear now , But i have still some doubt, not cleared full , why we need inner loop actually, that 's last question. –  Sep 19 '17 at 07:37
  • The inner loop is responsible for finding *one* large element and sorting it to the end of the list (by swapping two adjacent elements). The outer loop is responsible to repeat that process enough times to make sure that all elements will be sorted eventually. If you are having difficulties understanding it, try it by hand on paper, you will surely see how exactly it’s working now. The step-by-step example and the animation [on Wikipedia](https://en.wikipedia.org/wiki/Bubble_sort) do really help explaining the process as well. – poke Sep 19 '17 at 07:41
0

It's because when you bubble from the start of the list to the end, the final result is that the last item in the list will be sorted (you've bubbled the largest item to the end). As a result, you don't want to include the last item in the list when you do the next bubble (you know it's already in the right place). This means the list you need to sort gets shorter, starting at the end and going down towards the start. In this code, i is always the length of the remaining unsorted list.

Jeremy McGibbon
  • 3,527
  • 14
  • 22
  • you meant "the final result is that the last item in the list will be "un"sorted ? you wrote "sorted" ? –  Sep 19 '17 at 07:01
  • I meant "sorted". If you have [5, 4, 6, 2, 0], then after one bubble you'll have [5, 4, 2, 0, 6] and the last item "6" is sorted. After another bubble you have [4, 2, 0, 5, 6] and the last two are sorted, and so on. – Jeremy McGibbon Sep 19 '17 at 07:04
0

You can use this for:

for i in range(0,len(alist)-1,1):

but consequently you should change your second iteration:

for j in range(0,len(alist)-i,1):

I think the purpose of using reverse iteration in the first line is to simplify the second iteration. This is the advantage of using python

as @Jeremy McGibbon's answer, the logic behind bubble sort is to avoid j reach the "sorted part" in the behind of list. When using the example code, j range will be decreased as the value of i decrease. When you change i to increasing, you should handle j iteration differently

malioboro
  • 3,097
  • 4
  • 35
  • 55
0

You can write the code as follow

lst = [9,6,5,7,8,3,2,1,0,4]
lengthOfArray = len(lst) - 1

for i in range(lengthOfArray):
    for j in range(lengthOfArray - i):
        if lst[j] > lst[j + 1]:
            lst[j], lst[j + 1] = lst[j + 1], lst[j]

print(lst)
Gehan Fernando
  • 1,221
  • 13
  • 24