Ordenamiento par-impar

En informática, un ordenamiento impar-par u ordenamiento por transposición impar-par (también conocido como ordenamiento por ladrillo ^{[1] [ fuente autopublicada ]} u ordenamiento por paridad ) es un algoritmo de ordenamiento relativamente simple , desarrollado originalmente para su uso en procesadores paralelos con interconexiones locales. Es un ordenamiento por comparación relacionado con el ordenamiento por burbuja , con el que comparte muchas características. Funciona comparando todos los pares de elementos adyacentes indexados pares/impares en la lista y, si un par está en el orden incorrecto (el primero es más grande que el segundo), los elementos se intercambian. El siguiente paso repite esto para pares de elementos adyacentes indexados pares/impares. Luego alterna entre pasos impares/pares y pares/impares hasta que la lista esté ordenada.

Ordenación en matrices de procesadores

En procesadores paralelos, con un valor por procesador y solo conexiones locales de vecino izquierdo-derecho, todos los procesadores realizan simultáneamente una operación de comparación-intercambio con sus vecinos, alternando entre pares-impares y pares-impares. Este algoritmo fue presentado originalmente, y se demostró que era eficiente en tales procesadores, por Habermann en 1972. ^[2]

El algoritmo se extiende de manera eficiente al caso de múltiples elementos por procesador. En el algoritmo de fusión-división de pares e impares de Baudet-Stevenson, cada procesador ordena su propia sublista en cada paso, utilizando cualquier algoritmo de ordenación eficiente, y luego realiza una operación de fusión-división, o de transposición-fusión, con su vecino, alternando el emparejamiento de vecinos entre pares e impares y pares e impares en cada paso. ^[3]

Combinación de ordenamiento impar-par de Batcher

Un algoritmo de ordenamiento relacionado pero más eficiente es el método de combinación de pares e impares de Batcher , que utiliza operaciones de comparación-intercambio y operaciones de mezcla perfecta. ^[4] El método de Batcher es eficiente en procesadores paralelos con conexiones de largo alcance. ^[5]

Algoritmo

El algoritmo de un solo procesador, como bubblesort , es simple pero no muy eficiente. Aquí se supone un índice basado en cero :

función oddEvenSort ( lista ) { función swap ( lista , i , j ) { var temp = lista [ i ]; lista [ i ] = lista [ j ]; lista [ j ] = temp ; }                   var ordenado = falso ; mientras ( ! ordenado ) { ordenado = verdadero ; para ( var i = 1 ; i < lista . length - 1 ; i += 2 ) { si ( lista [ i ] > lista [ i + 1 ]) { intercambiar ( lista , i , i + 1 ); ordenado = falso ; } } para ( var i = 0 ; i < lista . length - 1 ; i += 2 ) { si ( lista [ i ] > lista [ i + 1 ]) { intercambiar ( lista , i , i + 1 ); ordenado = falso ; } } } }                                                                        

Prueba de corrección

Afirmación: Sea una secuencia de datos ordenados por <. El algoritmo de ordenamiento impar-par ordena correctamente estos datos en pasadas. (Una pasada se define aquí como una secuencia completa de comparaciones impar-par o par-impar. Las pasadas se producen en orden: pasada 1: impar-par, pasada 2: par-impar, etc.) ${\displaystyle a_{1},...,a_{n}}$ ${\displaystyle n}$

Prueba:

Esta prueba se basa vagamente en una de Thomas Worsch. ^[6]

Dado que el algoritmo de ordenamiento solo implica operaciones de comparación-intercambio y es inconsciente (el orden de las operaciones de comparación-intercambio no depende de los datos), por el principio de ordenamiento 0-1 de Knuth, ^{[7] [8]} es suficiente comprobar la corrección cuando cada uno es 0 o 1. Supongamos que hay 1. ${\displaystyle a_{i}}$ ${\displaystyle e}$

Observe que el 1 más a la derecha puede estar en una posición par o impar, por lo que podría no moverse con el primer pase par-impar. Pero después del primer pase par-impar, el 1 más a la derecha estará en una posición par. De ello se deduce que se moverá hacia la derecha con todos los pases restantes. Dado que el 1 más a la derecha comienza en una posición mayor o igual a , debe moverse como máximo pasos. De ello se deduce que se necesitan como máximo pases para mover el 1 más a la derecha a su posición correcta. ${\displaystyle e}$ ${\displaystyle n-e}$ ${\displaystyle n-e+1}$

Ahora, consideremos el segundo 1 más a la derecha. Después de dos pasadas, el 1 a su derecha se habrá movido a la derecha al menos un paso. De ello se deduce que, para todas las pasadas restantes, podemos ver al segundo 1 más a la derecha como el 1 más a la derecha. El segundo 1 más a la derecha comienza en la posición al menos y debe moverse a la posición como máximo , por lo que debe moverse como máximo pasos. Después de como máximo 2 pasadas, el 1 más a la derecha ya se habrá movido, por lo que la entrada a la derecha del segundo 1 más a la derecha será 0. Por lo tanto, para todas las pasadas después de las dos primeras, el segundo 1 más a la derecha se moverá a la derecha. Por lo tanto, se necesitan como máximo pasadas para mover el segundo 1 más a la derecha a su posición correcta. ${\displaystyle e-1}$ ${\displaystyle n-1}$ ${\displaystyle (n-1)-(e-1)=n-e}$ ${\displaystyle n-e+2}$

Continuando de esta manera, por inducción se puede demostrar que el -ésimo 1 más a la derecha se mueve a su posición correcta en como máximo pases. Como , se deduce que el -ésimo 1 más a la derecha se mueve a su posición correcta en como máximo pases. La lista está, por tanto, correctamente ordenada en pases. QED. ${\displaystyle i}$ ${\displaystyle n-e+i}$ ${\displaystyle i\leq e}$ ${\displaystyle i}$ ${\displaystyle n-e+e=n}$ ${\displaystyle n}$

Observamos que cada pasada implica pasos, por lo que este algoritmo tiene complejidad. ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$

Referencias

1. Phillips, Malcolm. "Ordenación de matrices". Homepages.ihug.co.nz . Archivado desde el original el 28 de octubre de 2011. Consultado el 3 de agosto de 2011 .
2. N. Habermann (1972) "Ordenamiento de vecinos paralelos (o la gloria del principio de inducción)", Informe de Ciencias de la Computación de la CMU (disponible como informe técnico AD-759 248, Servicio Nacional de Información Técnica, Departamento de Comercio de los EE. UU., 5285 Port Royal Rd Springfield VA 22151).
3. Lakshmivarahan, S.; Dhall, SK y Miller, LL (1984), Alt, Franz L. y Yovits, Marshall C. (eds.), "Algoritmos de ordenamiento paralelo", Advances in Computers , 23 , Academic Press: 295–351, doi :10.1016/S0065-2458(08)60467-2, ISBN 978-0-12-012123-6
4. Sedgewick, Robert (2003). Algoritmos en Java, partes 1-4 (3.ª ed.). Addison-Wesley Professional. págs. 454-464. ISBN 978-0-201-36120-9.
5. Kent, Allen ; Williams, James G. (1993). Enciclopedia de informática y tecnología: suplemento 14. CRC Press. págs. 33–38. ISBN 978-0-8247-2282-1.
6. "Cinco conferencias sobre CA" (PDF) . Liinwww.ira.uka.de . Consultado el 30 de julio de 2017 .
7. Lang, Hans Werner. "El principio 0-1". inf.hs-flensburg.de . Consultado el 30 de julio de 2017 .
8. "Ordenamiento distribuido" (PDF) . Net.t-labs.tu-berlin.de . Consultado el 30 de julio de 2017 .