CODEWITHSUNDEEP
pythonalgorithmsortingdata-structuresbubble-sort
Colton Stoddard
Colton Stoddard

Reputation: 1

Bubble sort: understanding recursion

I'm new to programming and data structures and algorithms. I understand the program, what I don't understand is why does it recursively do what I want? I guess what I'm asking is why doesn't it stop after it goes through the list once? It keeps going until the whole list is sorted.

def bubblesort(numbers):
    for i in range(len(numbers)):
        for j in range(len(numbers) - 1):
            if(numbers[j] > numbers[j+1]):
                temp = numbers[j]
                numbers[j] = numbers[j+1]
                numbers[j+1] = temp

Upvotes: -1

Views: 76

Answers (2)

trincot
trincot

Reputation: 350760

There are two loops. The inner loop traverses the whole list for every iteration of the outer loop.

Now notice this:

The inner loop will guarantee that the greatest value "bubbles up" -- with every swap in which it participates -- to the far right. So after the first time that this inner loop completes, the greatest value will have arrived in its final spot.

The second time this inner loop restarts, we could imagine the list to be one element shorter: just imagine that the right most (i.e. greatest) value is not there. Then we have a similar situation: the now greatest value is guaranteed to be shifted to the far right. The inner loop will also compare this "greatest" value with the one we ignored (that really sits at the far right), but obviously they will not be swapped. So after the second time this inner loop does its traversal we have the two greatest values at the far right, in their final position.

So, there is a pattern here. If the inner loop is executed (in its totality) 10 times, then at the end we will have the greatest 10 values at the far right. That is why the outer loop makes as many iterations as there are values in the list. This way it is guaranteed that we will have sorted the whole list.

Upvotes: 1

Raphael Andres
Raphael Andres

Reputation: 127

Well, if I've got your question correctly, the point you're trying to understand is why your code run your list multiples time instead of only once right?

You've got a for inside another, in this way, in line 2 you started a loop that will walk trough the number array. For EVERY repetition of the first loop you are doing another loop in line 3, so, every time you run the array on line 2 you're running it again on line 3.

That's one of the main issues with bubble sorting, you'll keep running the array even after it was sorted.

Upvotes: 0

Related Questions