python - pyplot - Tarea de clasificación de burbujas

subplot python title

Question

En clase estamos haciendo algoritmos de clasificación y, aunque los entiendo bien cuando hablo de ellos y escribo pseudocódigo, tengo problemas para escribir el código real para ellos.

Este es mi intento en Python:

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

def bubble(badList):
    length = len(badList) - 1
    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
            else:
                unsorted = True

print bubble(mylist)

Ahora, esto (por lo que puedo ver) se ordena correctamente, pero una vez que termina, simplemente se repite indefinidamente.

¿Cómo se puede arreglar este código para que la función finalice correctamente y ordene correctamente una lista de cualquier tamaño (razonable)?

PD. Sé que realmente no debería tener impresiones en una función y debería tener una devolución, pero aún no lo he hecho ya que mi código realmente no funciona todavía.

Answer 1

# Una función muy simple, se puede optimizar (obviamente) disminuyendo el espacio problema de la 2 ª matriz. Pero la misma complejidad O (n ^ 2).

def bubble(arr):
    l = len(arr)        
    for a in range(l):
        for b in range(l-1):
            if (arr[a] < arr[b]):
            arr[a], arr[b] = arr[b], arr[a]
    return arr 

Answer 2

El objetivo de la clasificación de burbujas es mover los elementos más pesados en la parte inferior de cada ronda, mientras mueve los elementos más ligeros hacia arriba. En el ciclo interno, donde se comparan los elementos, no es necesario iterar toda la lista en cada turno . El más pesado ya está colocado en último lugar. La variable intercambiada es una verificación adicional, por lo que podemos marcar que la lista ahora está ordenada y evitar continuar con cálculos innecesarios.

def bubble(badList):
    length = len(badList)
    for i in range(0,length):
        swapped = False
        for element in range(0, length-i-1):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                swapped = True
        if not swapped: break

    return badList

Su versión 1, corregida:

def bubble(badList):
    length = len(badList) - 1
    unsorted = True
    while unsorted:
        unsorted = False
        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
                 unsorted = True
                 #print badList
             #else:
                 #unsorted = True

     return badList

Answer 3

El problema con el algoritmo original es que si tuviera un número más bajo en la lista, no lo colocaría en la posición ordenada correcta. El programa debe retroceder al principio cada vez para garantizar que los números se clasifiquen todo el tiempo.

Simplifiqué el código y ahora funcionará para cualquier lista de números independientemente de la lista e incluso si hay números que se repiten. Aquí está el código

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)

Answer 4

Esto es lo que sucede cuando usas el nombre de variable de significado negativo, necesitas invertir sus valores. Lo siguiente sería más fácil de entender:

sorted = False
while not sorted:
    ...

Por otro lado, la lógica del algoritmo está un poco desajustada. Debe verificar si se intercambiaron dos elementos durante el ciclo for. Así es como lo escribiría:

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

Answer 5

Las respuestas proporcionadas por the-furry y Martin Cote arreglaron el problema del bucle infinito, pero mi código aún no funcionaría correctamente (para una lista más grande, no se ordenaría correctamente). Terminé abandonando la variable unsorted y usé un contador en su lugar.

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 alguien pudiera proporcionar sugerencias sobre cómo mejorar mi código en los comentarios, sería muy apreciado.

Answer 6

Para explicar por qué su script no funciona ahora, cambiaré el nombre de la variable unsorted sorted para sorted .

Al principio, tu lista aún no está ordenada. Por supuesto, configuramos sorted to False .

Tan pronto como comenzamos el ciclo while, suponemos que la lista ya está ordenada. La idea es la siguiente: tan pronto como encontramos dos elementos que no están en el orden correcto, establecemos sorted nuevamente en False . sorted se mantendrá True solo si no hay elementos en el orden incorrecto .

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.

También hay pequeños problemas menores que ayudarían a que el código sea más eficiente o legible.

• En el ciclo for , usa el element variable. Técnicamente, el element no es un elemento; es un número que representa un índice de lista. Además, es bastante largo. En estos casos, solo use un nombre de variable temporal, como i para "índice".

  for i in range(0, length):

• El comando de range también puede tomar solo un argumento (llamado stop ). En ese caso, obtienes una lista de todos los enteros desde 0 hasta ese argumento.

  for i in range(length):

• La Guía de estilo de Python recomienda que las variables se denominen en minúsculas con guiones bajos. Este es un pequeño detalle para un pequeño guión como este; es más para acostumbrarte a lo que el código de Python se parece más a menudo.

  def bubble(bad_list):

• Para intercambiar los valores de dos variables, escríbalas como una asignación de tupla. El lado derecho se evalúa como una tupla (por ejemplo, (badList[i+1], badList[i]) es (3, 5) ) y luego se asigna a las dos variables en el lado izquierdo ( (badList[i], badList[i+1]) ).

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

Ponlo todo junto, y obtienes esto:

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

(A propósito, eliminé tu extracto impreso).

Answer 7

Soy un nuevo principiante, comencé a leer sobre Python ayer. Inspirado por su ejemplo, creo algo más en el estilo de los 80, pero de todos modos funciona

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

i=0
while i < len(lista1)-1:
    if lista1[i] > lista1[i+1]:
        x = lista1[i]
        lista1[i] = lista1[i+1]
        lista1[i+1] = x
        i=0
        continue
    else:
        i+=1

print(lista1)

Answer 8

Su uso de la variable Unsorted es incorrecto; desea tener una variable que le indique si ha intercambiado dos elementos; si lo ha hecho, puede salir de su ciclo, de lo contrario, debe repetir el ciclo. Para arreglar lo que tienes aquí, simplemente coloca el "no clasificado = falso" en el cuerpo de tu caso; elimina tu caso más; y pon "unsorted = true" antes de tu ciclo for .

Answer 9

Tienes un par de errores allí. El primero es en longitud, y el segundo es en su uso de no ordenado (según lo establecido por McWafflestix). Probablemente también quiera devolver la lista si va a imprimirla:

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: tienes razón, lo de arriba está lleno de errores. Mi mal por no probar a través de algunos ejemplos más.

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

Answer 10

Un ejemplo más 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

Esto simplemente toma los elementos de 0 a a (básicamente, todos los elementos sin clasificar de esa ronda) y los compara con su elemento adyacente, y realiza un intercambio si es mayor que su elemento adyacente. Al final de la ronda, se ordena el último elemento, y el proceso se ejecuta nuevamente sin él, hasta que se hayan ordenado todos los elementos.

No hay necesidad de una condición si la sort es verdadera o no.

Tenga en cuenta que este algoritmo tiene en cuenta la posición de los números solo al intercambiar, por lo que los números repetidos no lo afectarán.

PD. Sé que ha pasado mucho tiempo desde que se publicó esta pregunta, pero solo quería compartir esta idea.

Answer 11

def bubbleSort(a): def swap(x, y): temp = a[x] a[x] = a[y] a[y] = temp #outer loop for j in range(len(a)): #slicing to the center, inner loop, python style for i in range(j, len(a) - j):  #find the min index and swap if a[i] < a[j]: swap(j, i) #find the max index and swap if a[i] > a[len(a) - j - 1]: swap(len(a) - j - 1, i) return a

Answer 12

def bubbleSort ( arr ):
    swapped = True 
    length = len ( arr )
    j = 0

    while swapped:
        swapped = False
        j += 1 
        for i in range ( length  - j ):
            if arr [ i ] > arr [ i + 1 ]:
                # swap
                tmp = arr [ i ]
                arr [ i ] = arr [ i + 1]
                arr [ i + 1 ] = tmp 

                swapped = True

if __name__ == ''__main__'':
    # test list
    a = [ 67, 45, 39, -1, -5, -44 ];

    print ( a )
    bubbleSort ( a )
    print ( a )

Answer 13

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

alist = [54,26,93,17,77,31,44,55,20, -23, -34,16,11,11,11]

imprimir bubbleSort (alist)

Answer 14

def bubble_sort(a):
    t = 0
    sorted = False # sorted = False because we have not began to sort
    while not sorted:
    sorted = True # Assume sorted = True first, it will switch only there is any change
        for key in range(1,len(a)):
            if a[key-1] > a[key]:
                sorted = False
                t = a[key-1]; a[key-1] = a[key]; a[key] = t;
    print a

Answer 15

def bubble_sort(l):
    exchanged = True
    iteration = 0
    n = len(l)

    while(exchanged):
        iteration += 1
        exchanged = False

        # Move the largest element to the end of the list
        for i in range(n-1):
            if l[i] > l[i+1]:
                exchanged = True
                l[i], l[i+1] = l[i+1], l[i]
        n -= 1   # Largest element already towards the end

    print ''Iterations: %s'' %(iteration)
    return l

Answer 16

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

Answer 17

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

Answer 18

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]))