I wrote bubble sort, based on my knowledge

[admuh]

Evening everyone. I would like to share my bubble sort program that I wrote based on what I understand about the bubble sort. What do you think? I think it is a bit not good because I need to pass as much as length of the array when the array is already sorted.

def sort(arr):
    i = 0
    passes = 0

    while True:
        if i >= len(arr) - 1:
            i = 0
            passes += 1
            if passes == (len(arr)):
                return arr

        print(arr, passes)
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
        
        i += 1

[sanity]

Have you found which part of code needs to be changed to not pass through whole array in every time?

while loop might add some complexity, as i and passes need to be manually changed. Have you tried using for loops?

[pkdvalis]

I see what you mean, it continues to sort for a few more passes after it’s sorted. I think it’s just the case that bubble sort isn’t that efficient.

Maybe you could add an extra check that loops through each digit and checks for (arr[i-1] < arr[i] < arr[+1]) once per pass and returns arr if it’s true. It’s not really more efficient than just letting the algorithm complete though I think

[admuh]

At this point, no. But that is the main reason why I developed the sort; I want to code to learn and understand about the sorting and I feel like by looking at examples won’t make me understand it.

Have not tried for loop yet, but I will try to code with it.

[admuh]

The more I think about it, it makes sense; Python supports mathematics interval statement. I will consider that

[sanity]

Which part is responsible for starting new pass?

[admuh]

@admuh

if i >= len(arr) - 1:
    i = 0
    passes += 1
        if passes == (len(arr)):
            return arr

To “starting new pass,” I made the i set to 0 and add passes and repeat it until the value of passes reaches the size of list.

[sanity]

Okay, consider then what happens across few passes:

1. During pass 0, no sorted numbers when starting it:
   • Is i equal to last index of array? (in other words pass is complete and one number is sorted.)
   • Set i to 0, increment passes.
2. During pass 1 - one number is sorted (at the end of array) when starting it:
   • Is i equal to last index of array?
   • Set i to 0, increment passes.
3. During pass 2 - two numbers are sorted (at the end of array) when starting it:
   • Is i equal to last index of array?
   • Set i to 0, increment passes.
4. etc.

Does this give you any ideas?

[admuh]

You mean some new ideas? I’m not sure though

[admuh]

Ah now I got another idea. Instead of giving passes, how about wrap it in a for?

def newsort(arr):
    n = len(arr)

    # This is the "passes"
    for j in range(n):

        # This is the swap between current and next index.
        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
    
    return arr

The “passes” will pass about size of the array minus one and the swap need to be size of the array minus two in order to avoid next index out of range.

[pkdvalis]

You got rid of the extra pass at the end, nice!