Как исправить мой алгоритм сортировки пузырьком на питоне?

Question

[SuperDuperPuper]

def buble():
    end = -len(array)

    
    while end!=-1: 
        for el in range(-1,end,-1):
            if array[el]<=array[-1+el]:
                mem = array[el]
                array[el] = array[-1+el]
                array[-1+el] = mem


        end=+1
    print("result is ")
    print(array)



array = [6,7,8,9,5,3,2,1,4,0]
buble()"

Answer 1

[Дмитрий Талько]

За ноут садиться никак(почти сплю), по этому писал с телефона. Я не мастер объяснять, но постарался описать каждый шаг

def buble(array):
    replaced = True

    for _ in array:
        #Если замен не было - выходим из цикла
        if not replaced: break
        replaced = False
    
        #Проходимся по списку и сравниваем 2 элемента
        for el in range(len(array)-1):

            #Если текущий элемент больше следующего
            if array[el] > array[el+1]:

                #Меняем местами
                array[el], array[el+1] = array[el+1], array[el]
          
                #ставим "флаг" что произошла замена
                replaced = True
    return array

array = [6,7,8,9,5,3,2,1,4,0]
print(buble(array))

Comments

[Hcuy]

Мне кажется что использование флага тут излишне...

[Дмитрий Талько]

Hcuy, это небольшая оптимизация, которая уменьшает суммарное количество операций сравнения путем досрочного выхода с цикла, когда все элементы уже отсортированы, но внешний цикл до конца списка еще не дошел) можете поставить счетчик и провести эксперимент :)

[SuperDuperPuper]

from random import randint    
def buble(array):
    global count
    count = 1
    end = -len(array)
    replaced = True
    while replaced == True:
        replaced = False
        
        for el in range(-1,end,-1):
            if array[el]<=array[-1+el]:
                array[el],array[-1+el] = array[-1+el],array[el]
                replaced = True

        print(count, ":" ,"\n",array,"\n")
        end+=1
        count+=1
    return array;

N = randint(10,50)
array = []

for i in range (N):
    array.append(randint(0,60))


print("now:",array,"\n")
print("result:",buble(array),"in ",count-1,"iterations",15*"\n")

[SuperDuperPuper]

Дмитрий, спасибо за идею с флагом.
Проблема моего алгоритма была в том,что я писал его,когда хотел спать и вместо " end+=1" писал "end=+1".
Это я заметил только утром.Такие вот пироги.