CODEWITHSUNDEEP
pythonpython-3.xbubble-sort
Aulmeies
Aulmeies

Reputation: 5

Sorting algorithm in Python

Currently I found this code while learning from a video. However, the code has a flaw which was pointed out but I am unable to understand part of the algorithm and why that flaw is a 'flaw'.

i = len(numList) - 1

while i > 1:
    j = 0

    while j < i:

        # If the value on the left is bigger switch values
        if numList[j] > numList[j+1]:
            temp = numList[j]
            numList[j] = numList[j + 1]
            numList[j + 1] = temp
        else:
            print()

        j += 1

    i -= 1

for k in numList:
    print(k, end=", ")
print()

The code is supposed to order numbers from a list of numbers, however I am unable to understand two things out of it:

One is "Why is 1 subtracted from "i"?" 

i = len(numList) - 1

And two, when the last number of the algorithm is "1" the algorithm won't order the numbers properly. For example, a list of "4, 2, 6, 3, 1" will be ordered as "2, 1, 3, 4, 6" instead of the correct "1, 2, 3, 4, 6,". People from the comments pointed out the reason for this is that it should be "while i > 0" or "while i >= 1" instead of "while i > 1". 

while i > 1:

However I am unable to understand why it is like that.

Upvotes: 0

Views: 234

Answers (2)

kuco 23
kuco 23

Reputation: 830

The algorithm carries the maximum of the first i+1 numbers to the front (so i+1-th position), by switching the neighbours until the maximum 'bubbles up'. In the first iteration, i = len(numList) - 1, so the maximum of the whole numList (index starts at 0 and ends at len(numList) - 1) is carried to the front. This is the maximum value, which should be last. Now you only have to worry about the first i - 1 values, therefore i is reduced by one. Because i > 1 forgets about carrying the first element to the front (being the second position), 2 and 1 in your example are not ordered correctly, as they would need to switch. Therefore you need the i = 1 iteration step.

There is a great site, which helps with visualisation of the sorting algorithms. https://visualgo.net/en/sorting?slide=1. Your algorithm is called bubble-sort.

Upvotes: 1

OneCricketeer
OneCricketeer

Reputation: 192043

"Why is 1 substracted from "i"?"

Because collections are zero-indexed. You have N elements, but the last indexable value is always N-1

When j < i and you access numList[j+1], then for when j is at its max value, j == i-1, and i is at its max value of len(numList) - 1, then you access numList[(i-1)+1] == numList[i] == numList[len(numList) - 1], which is the last available element.

two and the one that makes my head hurt the most

while i > 0 is correct because in the first iteration, i == 1 and j == 0, and you swap j+1 == 1 and j == 0 index when numList[j] > numList[j+1], so therefore 2 (index 1) and 1 (index 0) would be flipped, and you get 1,2,3,4,6 from 2,1,3,4,6

Upvotes: 1

Related Questions