Ошибка сортировки пузыря - PullRequest
Новая
       15

Ошибка сортировки пузыря

0 голосов
/ 04 ноября 2011

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

#!/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()

1 Ответ

0 голосов
/ 04 ноября 2011

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

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
...