Tri À Bulles Devoirs

Pour expliquer pourquoi votre script ne fonctionne pas, je vais renommer la variable unsorted à sorted.

Au premier abord, votre liste n'est pas encore triées. Bien sûr, nous avons mis en sorted à False.

Dès que nous commençons à le while boucle, nous supposons que la liste est déjà triée. L'idée est la suivante: dès que nous trouvons deux éléments qui ne sont pas dans le bon ordre, nous avons mis en sorted retour à False. sorted restera True seulement si il n'y avait pas d'éléments dans le mauvais ordre.

sorted = False  # We haven't started sorting yet

while not sorted:
    sorted = True  # Assume the list is now sorted
    for element in range(0, length):
        if badList[element] > badList[element + 1]:
            sorted = False  # We found two elements in the wrong order
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
    # We went through the whole list. At this point, if there were no elements
    # in the wrong order, sorted is still True. Otherwise, it's false, and the
    # while loop executes again.

Il y a aussi des mineurs peu des questions susceptibles d'aider à ce que le code sera plus efficace ou plus lisible.

• Dans le for boucle, vous utilisez la variable element. Techniquement, element n'est pas un élément; c'est un nombre qui représente un indice de la liste. Aussi, c'est assez long. Dans ces cas, il suffit d'utiliser une variable temporaire nom, comme i pour "index".

  for i in range(0, length):

• La range commande peut aussi ne prendre qu'un seul argument (nommé stop). Dans ce cas, vous obtenez une liste de tous les entiers de 0 à cet argument.

  for i in range(length):

• La Python Guide De Style recommande de nommage des variables en minuscules avec des traits de soulignement. C'est un très mineur pinaille pour un petit script comme ça, c'est plus pour vous permettre de vous familiariser à ce que le code Python le plus souvent ressemble.

  def bubble(bad_list):

• Pour permuter les valeurs de deux variables, écrire comme un n-uplet d'affectation. La main droite est évaluée comme un n-uplet (dire, (badList[i+1], badList[i]) est (3, 5)) et obtient ensuite assignés à deux variables sur le côté gauche ((badList[i], badList[i+1])).

  bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

Mettre tout cela ensemble, et vous obtenez ceci:

my_list = [12, 5, 13, 8, 9, 65]

def bubble(bad_list):
    length = len(bad_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if bad_list[i] > bad_list[i+1]:
                sorted = False
                bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

bubble(my_list)
print my_list

(J'ai enlevé votre rapport d'impression trop, d'ailleurs.)

C'est ce qui arrive lorsque vous utilisez le nom de la variable de signification négative, vous devez inverser leurs valeurs. La suite serait plus facile à comprendre:

sorted = False
while not sorted:
    ...

D'autre part, la logique de l'algorithme est un peu à l'écart. Vous devez vérifier si deux éléments échangés au cours de la boucle for. Voici comment j'allais l'écrire:

def bubble(values):
    length = len(values) - 1
    sorted = False
    while not sorted:
        sorted = True
        for element in range(0,length):
            if values[element] > values[element + 1]:
                 hold = values[element + 1]
                 values[element + 1] = values[element]
                 values[element] = hold
                 sorted = False
    return values

def bubble_sort(l):
    for passes_left in range(len(l)-1, 0, -1):
        for index in range(passes_left):
            if l[index] < l[index + 1]:
               l[index], l[index + 1] = l[index + 1], l[index]
    return l

Vous avez un couple d'erreurs là-bas. Le premier est dans la longueur, et le second, dans votre utilisation de non triés (comme indiqué par McWafflestix). Vous avez sans doute aussi envie de retourner la liste si vous allez imprimer:

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 2
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False

            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
                unsorted = True

    return badList

print bubble(mylist)

eta: Vous avez raison, le ci-dessus est buggé comme l'enfer. Mon mauvais pour ne pas tester à travers quelques exemples.

def bubble2(badList):
    swapped = True
    length = len(badList) - 2

    while swapped:
        swapped = False
        for i in range(0, length):
            if badList[i] > badList[i + 1]:

                # swap
                hold = badList[i + 1]
                badList[i + 1] = badList[i]
                badList[i] = hold

                swapped = True

    return badList

Le problème avec l'algorithme original est que si vous avez un nombre inférieur de plus dans la liste, il ne serait pas l'amener à la bonne position assortie. Le programme doit retourner le début à chaque fois pour s'assurer que les numéros de trier tout le chemin à travers.

J'ai simplifié le code et il va maintenant travailler pour un numéro de la liste, indépendamment de la liste et même si il y a la répétition des nombres. Voici le code

mylist = [9, 8, 5, 4, 12, 1, 7, 5, 2]
print mylist

def bubble(badList):
    length = len(badList) - 1
    element = 0
    while element < length:
        if badList[element] > badList[element + 1]:
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
            element = 0
            print badList
        else:
            element = element + 1

print bubble(mylist)

def bubbleSort(alist):
if len(alist) <= 1:
    return alist
for i in range(0,len(alist)):
   print "i is :%d",i
   for j in range(0,i):
      print "j is:%d",j
      print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j])
      if alist[i] > alist[j]:
         alist[i],alist[j] = alist[j],alist[i]
return alist

accédez à la liste = [54,26,93,17,77,31,44,55,20,-23,-34,16,11,11,11]

impression bubbleSort(accédez à la liste)

Un exemple plus simple:

a = len(alist)-1
while a > 0:
    for b in range(0,a):
        #compare with the adjacent element
        if alist[b]>=alist[b+1]:
            #swap both elements
            alist[b], alist[b+1] = alist[b+1], alist[b]
    a-=1

Cela prend simplement les éléments de 0 à un(en fait, tous les éléments non triés lors de la ronde) et la compare avec son élément adjacent, et de faire un swap si elle est supérieure à celle de son élément adjacent. À la fin de la ronde, le dernier élément est trié, et le processus s'exécute à nouveau sans elle, jusqu'à ce que tous les éléments ont été triés.

Il n'est pas nécessaire pour une condition si sort est vrai ou pas.

Noter que cet algorithme prend en considération la position des numéros seulement lors de l'échange, de sorte chiffres répétés ne l'affectera pas.

PS. Je sais qu'il a été très longtemps puisque cette question a été posté, mais je voulais juste partager cette idée.

def bubble_sort(li):
    l = len(li)
    tmp = None
    sorted_l = sorted(li)
    while (li != sorted_l):
        for ele in range(0,l-1):
            if li[ele] > li[ele+1]:
                tmp = li[ele+1]
                li[ele+1] = li [ele]
                li[ele] = tmp
    return li

def bubblesort(array):
    for i in range(len(array)-1):
        for j in range(len(array)-1-i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return(array)

print(bubblesort([3,1,6,2,5,4]))

Les réponses fournies par la fureur et Martin Cote fixe le problème de la boucle infinie, mais mon code ne serait pas travailler correctement (pour une liste plus exhaustive, il ne serait pas trier correctement.). J'ai fini par abandonner unsorted variable et utilisé un compteur à la place.

def bubble(badList):
    length = len(badList) - 1
    n = 0
    while n < len(badList):
        for element in range(0,length):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                n = 0
            else:
                n += 1
    return badList

if __name__ == '__main__':
    mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99]
    print bubble(mylist)

Si quelqu'un pouvait fournir tous les pointeurs sur la façon d'améliorer mon code dans les commentaires, il serait très apprécié.

idk si cela peut vous aider, après 9 ans...
ses un simple tri à bulles programme

    l=[1,6,3,7,5,9,8,2,4,10]

    for i in range(1,len(l)):
        for j in range (i+1,len(l)):
            if l[i]>l[j]:
                l[i],l[j]=l[j],l[i]

def bubble_sort(l):
    for i in range(len(l) -1):
        for j in range(len(l)-i-1):
            if l[j] > l[j+1]:
                l[j],l[j+1] = l[j+1], l[j]
    return l