Блог

Я пытаюсь написать и оптимизировать пузырьковую сортировку, но мой код фактически не сортируется по списку. Любые предложения относительно того, почему он останавливается раньше?

 #!/usr/bin/env python

from random import *
import time

def bubble(lst):
    counter = 0
    n = len(lst)
    while n > 0:
        temp = 0
        for i in range(1, n - 1):
            if lst[i] > lst[i   1]:
                lst[i], lst[i   1] = lst[i   1], lst[i] # swap
                temp = i
                counter  = 1 # to compare the speed to the
                             # unoptimized bubble sort
            n = temp
    return counter

def main():
    lst = range(10)
    shuffle(lst)
    print lst
    start = time.time()
    counter = bubble(lst)
    print lst
    end = time.time()
    print counter
    print "time", end - start

main()
  

Это должно исправить это:

 def bubble(lst):
    counter = 0
    n = len(lst)
    while n > 0:
            temp = 0
            for i in range(0,n-1): # <- first element is at position 0
                    if lst[i] > lst[i 1]:
                            lst[i],lst[i 1] = lst[i 1],lst[i]  #swap
                            temp = i 1 # <- the last swapped position
                            counter  = 1
            n = temp
    return counter