Bubble Sort Homework

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

Este es mi bash 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 decir) se clasifica 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 simplemente no lo he hecho todavía, ya que mi código aún no funciona.

Para explicar por qué su script no está funcionando en este momento, cambiaré el nombre de la variable unsorted a sorted .

Al principio, tu lista aún no está ordenada. Por supuesto, nos pusimos sorted en False .

Tan pronto como iniciamos el ciclo while, asumimos 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, volvemos a sorted en False . sorted permanecerá True solo si no hubiera 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 podrían ayudar a que el código sea más eficiente o legible.

  • En el bucle for , usas 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, simplemente use un nombre de variable temporal, como i para “índice”.

     for i in range(0, length): 
  • El comando de range también puede tomar un solo argumento (llamado stop ). En ese caso, obtendrás una lista de todos los enteros de 0 a ese argumento.

     for i in range(length): 
  • La Guía de estilo de Python recomienda que las variables se nombren en minúsculas con guiones bajos. Este es un problema muy menor para un pequeño script 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íbalos 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 del 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 

(Por cierto, también eliminé tu statement impresa).

El objective de la clasificación de burbujas es mover los elementos más pesados en la parte inferior de cada ronda, mientras se mueven los elementos más ligeros hacia arriba. En el bucle interno, donde se comparan los elementos, no tiene que iterar toda la lista en cada turno . El más pesado ya está colocado último. 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 

Esto es lo que sucede cuando usa el nombre de variable de significado negativo, necesita 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 apagada. Debe comprobar si dos elementos se intercambiaron durante el bucle 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 

Su uso de la variable sin clasificar es incorrecto; desea tener una variable que le indique si ha intercambiado dos elementos; si lo ha hecho, puede salir de su bucle; de ​​lo contrario, deberá hacerlo nuevamente. Para arreglar lo que tiene aquí, simplemente coloque el “unsorted = false” en el cuerpo de su caso, si es así; quite su otro caso; y ponga “unsorted = true antes de su bucle for .

 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 

#Una función muy simple, puede optimizarse (obviamente) reduciendo el espacio problemático de la segunda matriz. Pero igual 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 

Tienes un par de errores ahí. El primero es largo, y el segundo es su uso de sin clasificar (como lo indica McWafflestix). Probablemente también quieras devolver la lista si la vas a imprimir:

 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 anterior es un cochecito como el infierno. 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 

Soy un principiante fresco, comencé a leer sobre Python ayer. Inspirado por tu ejemplo, creé algo tal vez más en el estilo de los 80 empates, pero a pesar de todo 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) 

El problema con el algoritmo original es que si tuviera un número más bajo en la lista, no lo llevaría a la posición ordenada correcta. El progtwig debe volver al principio cada vez para asegurarse de que los números se ordenan completamente.

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

 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 

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 en esa ronda) y lo compara con su elemento adyacente, y hace un intercambio si es mayor que su elemento adyacente. Al final de la ronda, el último elemento se ordena y el proceso se ejecuta nuevamente sin él, hasta que todos los elementos se hayan ordenado.

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

Tenga en cuenta que este algoritmo toma en consideración la posición de los números solo cuando se intercambian, 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.

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

Las respuestas proporcionadas por the-fury y Martin Cote solucionaron 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 alguna sugerencia sobre cómo mejorar mi código en los comentarios, sería muy apreciado.

Prueba esto

 a = int(input("Enter Limit")) val = [] for z in range(0,a): b = int(input("Enter Number in List")) val.append(b) for y in range(0,len(val)): for x in range(0,len(val)-1): if val[x]>val[x+1]: t = val[x] val[x] = val[x+1] val[x+1] = t print(val) 

Me gustaría compartir mi solución:

 def bubble_sort(list_): for i in range(len(list_)): for j in range(i, len(list_)): if a[i] > a[j]: a[i], a[j] = a[j], a[i] return list_ 

Ejemplo de prueba:

 a = [8,1,2,4,1,3,5,1,5,6,1,8] bubble_sort(a) 

Resultado:

 [1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 8, 8] 

idk si esto podría ayudarte después de 9 años … es un progtwig simple de clasificación de burbujas

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