Algunas respuestas originalmente tenían este algoritmo de clasificación:
for i from 0 to n-1: for j from 0 to n-1: if A[j] > A[i]: swap A[i] and A[j]
Tenga en cuenta que tanto i
como j
van en el rango completo y, por lo tanto, j
puede ser tanto más grande como más pequeño que i
, por lo que puede hacer pares en el orden correcto e incorrecto (¡y en realidad hace ambos!). Pensé que era un error (y el autor más tarde lo llamó así) y que esto desordenaría la matriz, pero parece ordenarse correctamente. Sin embargo, no es obvio por qué. Pero la simplicidad del código (ir a rangos completos y sin +1
como en el tipo de burbuja) lo hace interesante.
¿Es correcto? Si es así, ¿por qué funciona? y tiene nombre?
Implementación de Python con pruebas:
from random import shuffle for _ in range(3): n = 20 A = list(range(n)) shuffle(A) print('before:', A) for i in range(n): for j in range(n): if A[j] > A[i]: A[i], A[j] = A[j], A[i] print('after: ', A, '\n')
Salida de muestra ( ¡Pruébelo en línea! ):
before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13] after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] before: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13] after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] before: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19] after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Editar: alguien señaló un artículo nuevo muy bueno sobre este algoritmo. Solo para aclarar: no estamos relacionados, es una coincidencia. Por lo que puedo decir, se envió a arXiv antes de la respuesta que provocó mi pregunta y arXiv la publicó después de mi pregunta.
Para probar que es correcto, tienes que encontrar algún tipo de invariante. Algo que es cierto durante cada paso del bucle.
Mirándolo, después del primer paso del ciclo interno, el elemento más grande de la lista estará en la primera posición.
Ahora, en el segundo paso del ciclo interno, i = 1
, y la primera comparación es entre i = 1
y j = 0
. Entonces, el elemento más grande estaba en la posición 0, y después de esta comparación, se cambiará a la posición 1.
En general, no es difícil ver que después de cada paso del bucle exterior, el elemento más grande se habrá movido uno a la derecha. Entonces, después de los pasos completos, sabemos que al menos el elemento más grande estará en la posición correcta.
¿Qué pasa con todo el resto? Digamos que el segundo elemento más grande se encuentra en la posición i
del ciclo actual. Sabemos que el elemento más grande se encuentra en la posición i-1
según la discusión anterior. El contador j
comienza en 0. Así que ahora estamos buscando el primer A[j]
tal que sea A[j] > A[i]
. Bueno, A[i]
es el segundo elemento más grande, por lo que la primera vez que sucede es cuando j = i-1
, en el primer elemento más grande. Por lo tanto, son adyacentes y se intercambian, y ahora están en el orden "correcto". Ahora A[i]
nuevamente apunta al elemento más grande y, por lo tanto, para el resto del ciclo interno no se realizan más intercambios.
Entonces podemos decir: una vez que el índice del bucle externo se ha movido más allá de la ubicación del segundo elemento más grande, el segundo y el primer elemento más grande estarán en el orden correcto. Ahora se deslizarán hacia arriba juntos, en cada iteración del ciclo externo, por lo que sabemos que al final del algoritmo, tanto el primer como el segundo elemento más grande estarán en la posición correcta.
¿Qué pasa con el tercer elemento más grande? Bueno, podemos usar la misma lógica nuevamente: una vez que el contador del bucle externo i
esté en la posición del tercer elemento más grande, se intercambiará de manera que estará justo debajo del segundo elemento más grande (si hemos encontrado que uno ya!) o justo debajo del primer elemento más grande.
ah Y aquí tenemos ahora nuestro invariante: después de k
iteraciones del ciclo externo, la secuencia de elementos de longitud k, que termina en la posición k-1
, estará ordenada:
Después de la primera iteración, la secuencia de longitud 1, en la posición 0, estará en el orden correcto. Eso es trivial.
Después de la segunda iteración, sabemos que el elemento más grande está en la posición 1, por lo que obviamente la secuencia A[0]
, A[1]
está en el orden correcto.
Ahora supongamos que estamos en el paso k
, por lo que todos los elementos hasta la posición k-1
estarán en orden. Ahora i = k
e iteramos sobre j
. Lo que esto hace es básicamente encontrar la posición en la que el nuevo elemento debe colocarse en la secuencia ordenada existente para que se ordene correctamente. Una vez que eso sucede, el resto de los elementos "burbujean" hasta que ahora el elemento más grande se encuentra en la posición i = k
y no ocurren más intercambios.
Así, finalmente, al final del paso N
, todos los elementos hasta la posición N-1
están en el orden correcto, QED.
No estoy muy seguro de si el algoritmo anterior tiene un nombre explícito, pero a partir de un análisis de salida rápido parece una implementación ineficiente de ordenación por inserción , donde la región ordenada es de los índices 0
a i
inclusive después de ejecutar la iteración i
.
Depuración de impresión
Esto se puede verificar mediante una inspección si colocamos una declaración de impresión justo después del ciclo interno:
for i from 0 to n-1: for j from 0 to n-1: if A[j] > A[i]: swap A[i] and A[j] print(A) <- add here
A = [5, 5, 0, 9, 2] 0. [9, 5, 0, 5, 2] 1. [5, 9, 0, 5, 2] 2. [0, 5, 9, 5, 2] 3. [0, 5, 5, 9, 2] 4. [0, 2, 5, 5, 9]
Prueba
Podemos probar esto por inducción en i
, el lazo exterior. Después de haber ejecutado la iteración i
, se ordenan los índices 0 to i
inclusive de A
, o A[0:i]
, con A[i] = max(A)
.
Caso base: i = 0
Para i = 0
, el máximo de A
se almacenará en el índice 0
. Esto más o menos se sigue de la inspección del algoritmo.
Paso inductivo: i > 0
Nuestra hipótesis inductiva es que A[0:i-1]
está ordenada y que A[i - 1] = max(A)
. ¿Qué sucede en la iteración i
? Básicamente, estamos determinando dónde debe colocarse A[i]
en la región ordenada (manejada por el bucle interno) y luego lo reajustamos.
Subcaso 1: A[i] < A[j]
para algún 0 <= j <= i - 1
Del algoritmo anterior, A[j]
se intercambiará con Ap = A[i]
. Observe que, a partir de nuestra hipótesis, se clasificó A[0:i-1]
. Entonces, se deduce que para el resto de los índices de j + 1 <= i
estaremos reordenando nuestra región ordenada después de insertar Ap
. De ello se deduce que A[0:i]
se ordenará cuando j = i
.
Subcaso 2: A[i] >= A[j]
para todo 0 <= j <= i - 1
No ocurren intercambios en este caso, y se deduce que A[0:i]
se ordena a partir de A[0:i-1]
que se ordena y el hecho de que A[i] >= A[i - 1]
.
Otro caso: j > i
Observe que, después de que j
alcance el índice i
, el máximo de A
volverá al índice i
. Por lo tanto, para el resto del ciclo interno, no se realizarán intercambios. Entonces, se deduce que se ordenará A[0:i]
.
Debido a que lo anterior es válido para todo i < n = len(A)
, podemos concluir que ejecutar la iteración n - 1
ordenará efectivamente A[0:n-1] = A
.
Verificación/Mejora
De la prueba anterior, vimos que la comprobación de j > i
era redundante. Para hacer que el algoritmo sea más eficiente y esté más en sintonía con la ordenación por inserción habitual, podemos ejecutar el siguiente código que también ordenará la matriz.
for i from 0 to n-1: for j from 0 to i: <- claim this line can be changed if A[j] > A[i]: swap A[i] and A[j]
Es un tipo bastante extraño, definitivamente no es un Bubble Sort. Al final de cada iteración for i in range(n)
, el i -ésimo elemento ahora contendrá el elemento más grande de la lista A
Es decir, intercambiamos el elemento i
con el elemento j
siempre que el elemento j sea mayor que el elemento i. Claramente, al final del algoritmo, el último elemento será el más grande.
El punto clave es este: al final de la iteración i
, cada elemento a la izquierda de la posición i
(valores más bajos de i
) debe tener valores menores o iguales, es decir, A[j] <= A[j+1] para j < i.
El siguiente programa intenta demostrar esto:
from random import shuffle def assert_partial_sort_order(A, i): """ Assert A[j] <= A[j+1] for j < i """ for j in range(i): assert A[j] <= A[j+1] def sort(A): n = len(A) print('sort before:', A) n_swaps = 0 for i in range(n): print('i =', i) for j in range(n): if A[j] > A[i]: A[i], A[j] = A[j], A[i] print(' swapping for j =', j) print(' A =', A) assert_partial_sort_order(A, i) print('sort after:', A, '\n') n = 10 A = list(range(n)) shuffle(A) sort(A)
Huellas dactilares:
sort before: [7, 0, 4, 2, 8, 9, 5, 1, 3, 6] i = 0 swapping for j = 4 A = [8, 0, 4, 2, 7, 9, 5, 1, 3, 6] swapping for j = 5 A = [9, 0, 4, 2, 7, 8, 5, 1, 3, 6] i = 1 swapping for j = 0 A = [0, 9, 4, 2, 7, 8, 5, 1, 3, 6] i = 2 swapping for j = 1 A = [0, 4, 9, 2, 7, 8, 5, 1, 3, 6] i = 3 swapping for j = 1 A = [0, 2, 9, 4, 7, 8, 5, 1, 3, 6] swapping for j = 2 A = [0, 2, 4, 9, 7, 8, 5, 1, 3, 6] i = 4 swapping for j = 3 A = [0, 2, 4, 7, 9, 8, 5, 1, 3, 6] i = 5 swapping for j = 4 A = [0, 2, 4, 7, 8, 9, 5, 1, 3, 6] i = 6 swapping for j = 3 A = [0, 2, 4, 5, 8, 9, 7, 1, 3, 6] swapping for j = 4 A = [0, 2, 4, 5, 7, 9, 8, 1, 3, 6] swapping for j = 5 A = [0, 2, 4, 5, 7, 8, 9, 1, 3, 6] i = 7 swapping for j = 1 A = [0, 1, 4, 5, 7, 8, 9, 2, 3, 6] swapping for j = 2 A = [0, 1, 2, 5, 7, 8, 9, 4, 3, 6] swapping for j = 3 A = [0, 1, 2, 4, 7, 8, 9, 5, 3, 6] swapping for j = 4 A = [0, 1, 2, 4, 5, 8, 9, 7, 3, 6] swapping for j = 5 A = [0, 1, 2, 4, 5, 7, 9, 8, 3, 6] swapping for j = 6 A = [0, 1, 2, 4, 5, 7, 8, 9, 3, 6] i = 8 swapping for j = 3 A = [0, 1, 2, 3, 5, 7, 8, 9, 4, 6] swapping for j = 4 A = [0, 1, 2, 3, 4, 7, 8, 9, 5, 6] swapping for j = 5 A = [0, 1, 2, 3, 4, 5, 8, 9, 7, 6] swapping for j = 6 A = [0, 1, 2, 3, 4, 5, 7, 9, 8, 6] swapping for j = 7 A = [0, 1, 2, 3, 4, 5, 7, 8, 9, 6] i = 9 swapping for j = 6 A = [0, 1, 2, 3, 4, 5, 6, 8, 9, 7] swapping for j = 7 A = [0, 1, 2, 3, 4, 5, 6, 7, 9, 8] swapping for j = 8 A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sort after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Es un tipo de inserción correcto pero extraño e ineficiente.
Primero visualicémoslo imprimiendo A
después de cada iteración completa del ciclo interno. Ejemplo:
before: [1, 12, 13, 8, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [19, 1, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 19, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 12, 19, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 8, 12, 19, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 8, 12, 13, 19, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 8, 12, 13, 15, 19, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 8, 12, 13, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 8, 12, 13, 15, 16, 18, 19, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 6, 7, 8, 11, 12, 13, 15, 16, 18, 19, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 3, 2, 9, 5, 4, 0, 10, 17] [1, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 2, 9, 5, 4, 0, 10, 17] [1, 2, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 9, 5, 4, 0, 10, 17] [1, 2, 3, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 5, 4, 0, 10, 17] [1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 4, 0, 10, 17] [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 0, 10, 17] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 10, 17] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 17] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Gráficamente, pero actualizándose después de cada intercambio, la barra roja muestra el índice i
( código aquí ):
Para i = 0
, en realidad mezcla más o menos la lista, pero trae el valor más grande a A[0]
(o un valor más grande, si hay varios). A partir de entonces, este valor actuará como centinela.
Debido a esta confusión inicial, sería difícil (y sin sentido) establecer un invariante basado en el estado inicial de la matriz. En su lugar, definamos A0
como el estado de la matriz después del ciclo externo para i = 0
:
Invariante: después del bucle externo para algunos i
:
A[i]
A[0 to i]
contiene A0[0 to i]
en orden ordenado.Prueba por inducción:
El caso base i = 0
es trivial.
Casos i > 0
: antes del ciclo externo con este i
, tenemos el centinela (valor general más grande) en A[i-1]
, y A[0 to i-1]
contiene A0[0 to i-1]
en orden pedido. Ahora el ciclo interno recorre todos los elementos e intercambiamos A[i]
y A[j]
siempre que A[j] > A[i]
. Veamos una fila de ejemplo desde arriba nuevamente:
[1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
El 19
es el centinela, se ordena la parte hasta él, e i
es el índice del 11. ¿Qué sucede cuando vamos con j
desde 0 hasta el final? Los valores 1, 7 y 8 no son mayores que el 11, por lo que no pasa nada. El 12 es más grande, por lo que se intercambiará con el 11:
[1, 7, 8, 11, 13, 15, 16, 18, 19, 12, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
Ahora es el 12 que está en el índice i
. Y luego se compara con 13. Como 13 es más grande, se intercambian:
[1, 7, 8, 11, 12, 15, 16, 18, 19, 13, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
Esto continúa, siempre intercambiando, hasta que intercambiamos con el centinela:
[1, 7, 8, 11, 12, 13, 16, 18, 19, 15, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 7, 8, 11, 12, 13, 15, 18, 19, 16, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 7, 8, 11, 12, 13, 15, 16, 19, 18, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17] [1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
En este punto, se completa la inserción del 11 en la parte clasificada. Y el centinela se movió al índice i
, donde luego evita más intercambios durante el ciclo interno (es decir, intercambios con elementos más a la derecha). En general, para un valor nuevo (como el 11), los números más pequeños permanecen donde están, y los números más grandes se intercambian y regresan a un lugar a la derecha.
Cuando hayamos terminado , tendremos el ciclo externo con i = n-1
. El invariante nos dice que A[0 to n-1]
contiene A0[0 to n-1]
en orden ordenado. Es decir, la matriz de hecho termina ordenada correctamente.
Por qué lo llamo una ordenación por inserción : después del desorden i = 0
, si observa la matriz después de cada ciclo interno completo, es indistinguible de la ordenación por inserción (vea mi gran bloque de visualización en la parte superior). Por ejemplo, el 11 simplemente se insertó en la parte ordenada a su izquierda. Simplemente difiere en cómo ocurre esa inserción. La clasificación por inserción normal "burbujea" el 11 hacia la izquierda hasta su lugar correcto, sin siquiera mirar los números aún más pequeños. En cambio, este algoritmo aquí busca el punto de inserción, comenzando desde el extremo izquierdo, y luego inserta el 11 allí y "burbujea" los números más grandes hasta el centinela hacia la derecha . Y luego continúa con más comparaciones infructuosas contra el centinela ahora sentado en A[i]
.
Actualización: smusamashah compartió su fantástica herramienta de visualización , que muy bien nos permite comparar este algoritmo con los otros algoritmos que se decía que era. Haga clic en las marcas de verificación a la derecha para Bubble Sort, Insertion Sort y Selection Sort, luego haga clic en Start. Verá nuevamente que nuestra ordenación es muy parecida a la ordenación por inserción y no se parece en nada a las otras. Y si, en cambio, hace Exchange Sort (lamentablemente no incluido), verá que se parece más a Selection Sort (pero más lento porque intercambia más y la herramienta muestra todos los intercambios).
Creo que es informativo reescribirlo eliminando las ineficiencias.
En pseudocódigo:
Find the largest element. Move it to the location A[0]. For i from 1 upto n: For j from 0 upto i: swap A[i] and A[j] if A[j] is greater than A[i] Invariant: A[0...j] is sorted Invariant: A[j+1...i-1] is sorted Invariant: A[i] is larger than anything in A[0...j] Invariant: A[0...i] contains the same elements sorted, but now sorted
Esto salta dos cosas. En primer lugar, omite el "revoltijo" inicial en su mayoría sin sentido de la matriz, y omite la comparación que nunca hace nada del elemento más grande y los elementos posteriores.
En el ciclo i=5, podríamos comenzar con:
i 10 20 30 40 99 25
j luego escanea:
[10] 20 30 40 99 25 10 [20] 30 40 99 25 10 20 [30] 40 99 25
en este punto, A[j] (también conocido como 30) es mayor que A[i] (también conocido como 25). Se intercambian y j avanza:
10 20 25 [40] 99 30 10 20 25 30 [99] 40 10 20 25 30 40 [99]
En el algoritmo original, la exploración de j hasta n continúa. Esto no hace nada, porque el elemento más grande ya está en A[i], por lo que A[j] nunca es mayor que A[i].
La única peculiaridad restante es el "revoltijo" que hace para mover el elemento más alto a A[0].
Mirando cómo funciona esto:
A[0] se compara sucesivamente con A[1..n-1]. Cualquier elemento más grande que A[0] se intercambia. Una vez que se encuentra el elemento más grande, las comparaciones restantes no hacen nada.
No es nada súper especial.
Lo último en lo que hay que pensar es en cómo se ve el circuito (la versión infinitamente paralela, en la que solo nos preocupamos por las dependencias de la información , la secuenciación esencial no es incidental) de este algoritmo. Sea X un circuito que lee desde arriba a la izquierda y desde arriba a la derecha, y envía el elemento superior hacia abajo a la derecha y hacia abajo a la izquierda. Deje que Y, en cambio, envíe el elemento superior a la parte inferior izquierda y el inferior a la parte inferior derecha.
1 2 3 4 5 6 7 Y | | | | | | Y | | | | | | Y | | | | | | Y | | | | | | Y | | | | | | Y | | | | | | *
luego giramos * de regreso a la primera columna.
Entonces, cada elemento que es más grande que cualquier cosa que quede se mueve hacia la derecha hasta que encuentra un elemento más grande. Finalmente, el elemento más grande se coloca en A[0] (ya que no tiene un elemento más grande en el que detenerse).
En iteraciones posteriores
1 2 3 * 5 6 7 8
5 se mueve "lógicamente" al extremo izquierdo de los valores:
5 1 2 3 * 6 7 8 X | | | X | | | X
y luego cambió de posición con un circuito como ese.
Si realiza un seguimiento del * (el elemento más grande), notará que ya conocemos todas sus comparaciones. Y mientras lo movemos a la ubicación 0 en el paso 1, procedemos a deslizarlo (sin necesidad de comparaciones) hasta el final.
Así que quitando el * de consideración
1 2 3 4 5 6 7 8
se conecta como:
5 1 2 3 4 6 7 8 X | | | | X | | | | X | | | | X
luego ponemos 6
6 5 1 2 3 4 6 7 8 X | | | | | X | | | | | X | | | | | X | | | | | X
En cada paso tomamos el nuevo elemento, lo rellenamos a la izquierda y luego hacemos una cadena de intercambios. Podemos tomar esa inversión como sin importancia y obtener este diagrama de cableado:
1 2 3 4 5 6 7 X | | | | | | X | | | | XX | | | | XX | | XXX | | XXX XXX | | XX | | XX | | | | X | | | | X | | | | |
que es básicamente lo que obtienes cuando haces esto con una especie de burbuja. En este algoritmo, los bucles internos existen en diagonal en el circuito anterior. Mientras tanto, es una especie de burbuja, los bucles internos existen horizontalmente en el circuito anterior.
En conclusión, creo que esta es una variante relativista del tipo burbuja; es una especie de burbuja, con un eje espacio-temporal inclinado. Pero el gráfico de dependencia para cada cálculo termina pareciendo casi idéntico, con algunas diferencias relativamente sin importancia (el elemento de búsqueda más grande y el orden de cambio de bits).