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