Search code examples
pythonarrayssortingbubble-sort

How do I make my bubble sort algorithm go through all entries in my array?


I have an array which stores highscores to a quiz. I have a for loop that should get the bubble sort to go through all entries, however it doesn't function as intended and seems to

All the scores before the sort appear like this:

[(3, ), (0, ), (1, ), (0, ), (3, ), (0, ), (0, ), (3, ), (69, )]

And after the sort is 'completed', they appear as:

[(3, ), (1, ), (0, ), (3, ), (0, ), (0, ), (3, ), (0, ), (69, )]

As you can see, they appear to have sorted to an extent but it doesn't fully loop back to the start and resort until they are fully in ascending to descending order.

The code for this is:

        swapScores = True
        while swapScores == True and lengthHighscore >= 0:
            swapScores = False
            for counter in range(i, lengthHighscore - 2):
                if leaderboardScores[i] < leaderboardScores[i + 1]:
                    tempScore = leaderboardScores[i]
                    leaderboardScores[i] = leaderboardScores[i + 1]
                    leaderboardScores[i + 1] = tempScore
                lengthHighscore = lengthHighscore - 1
                i = i + 1
                swapScores = True

Any help at all would be great, thank you!! My code probably isn't as efficient as I would like but I'm really going for functionality over efficiency at this point haha :)


Solution

  • There are a few issues in your implementation of bubble sort:

    • i is not reset to 0 in the iteration of the outer loop, which means that the second time the range of the inner loop is evaluated, it is an empty range. In fact, that range should always start with 0.

    • That range should go up to, and including lengthHighscore - 2, so the range should be range(lengthHighscore - 1) instead of lengthHighscore - 2.

    • lengthHighscore should not be reduced in the inner loop, as that will make the outer loop exit after the inner loop finishes. It should be reduced in the outer loop.

    The following are not breaking the algorithm, but still deserve to be corrected:

    • swapScores = True should happen in the if block, otherwise it does not really help to short cut the algorithm.

    • counter and i will be equal if you fix the above errors, so then you could just use i and drop counter

    • Python has a nice syntax to swap values without using an explicit temporary variable

    • The outer loop can also be implemented with a range so that you don't have to explicitly decrease lengthHighscore. An if not swapScores can then be used to break out of that loop as a short cut.

    Corrected code:

    for last in range(len(leaderboardScores) - 1, 0, -1):
        swapScores = False
        for i in range(last):
            if leaderboardScores[i] < leaderboardScores[i + 1]:
                leaderboardScores[i], leaderboardScores[i + 1] = leaderboardScores[i + 1], leaderboardScores[i]
                swapScores = True
        if not swapScores:
            break
    

    This will sort the scores in descending order. If you need the order to be ascending, then change the if condition to use > instead of <.

    Obviously, there is no need to implement your own sorting algorithm, as Python has a sort method and a sorted function. These will do the job faster than any custom implementation using Python code.