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