Orden impar-par

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

Clasificación por matrices de procesadores

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

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

Clasificación de fusión par-impar de Batcher

Un algoritmo de clasificación relacionado pero más eficiente es el mergesort par-impar 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 de base cero :

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

Prueba de corrección

Reclamación: Sea una secuencia de datos ordenados por <. El algoritmo de clasificación par-impar clasifica correctamente estos datos en pasadas. (Aquí un pase se define como una secuencia completa de comparaciones pares-impar o par-impar. Los pases ocurren en el orden paso 1: par-impar, paso 2: par-impar, etc.) ${\displaystyle a_{1},...,a_{n}}$ ${\displaystyle n}$

Prueba:

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

Dado que el algoritmo de clasificación solo implica operaciones de intercambio de comparación y no tiene en cuenta (el orden de las operaciones de intercambio de comparación no depende de los datos), según el principio de clasificación 0-1 de Knuth, ^{[7] [8]} es suficiente verificar la exactitud cuando cada es 0 o 1. Supongamos que hay unos. ${\displaystyle a_{i}}$ ${\displaystyle e}$

Observe que el 1 situado más a la derecha puede estar en una posición par o impar, por lo que es posible que no se mueva en el primer paso 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 todos los pases restantes lo moverán hacia la derecha. Dado que el más a la derecha comienza en una posición mayor o igual a , se debe mover en la mayoría de los 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, considere el segundo 1 más a la derecha. Después de dos pases, el 1 a su derecha se habrá movido a la derecha al menos un paso. De ello se deduce que, para todos los pases restantes, podemos ver el 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 los pasos. Después de como máximo 2 pases, 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 todos los pases después de los dos primeros, el segundo 1 más a la derecha se moverá hacia la derecha. Por lo tanto, se necesitan como máximo pasos 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}$

Siguiendo de esta manera, por inducción se puede demostrar que el -ésimo 1 situado más a la derecha se mueve a su posición correcta como máximo en pasadas. Desde , se deduce que el -ésimo 1 más a la derecha se mueve a su posición correcta en la mayoría de los pases. De este modo la lista queda correctamente ordenada en pasadas. QED. ${\displaystyle i}$ ${\displaystyle n-e+i}$ ${\displaystyle i\leq e}$ ${\displaystyle i}$ ${\displaystyle n-e+e=n}$ ${\displaystyle n}$

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

Referencias

1. Phillips, Malcolm. "Clasificación de matrices". Páginas de inicio.ihug.co.nz . Archivado desde el original el 28 de octubre de 2011 . Consultado el 3 de agosto de 2011 .
2. N. Habermann (1972) "Parallel Neighbor Sort (o la gloria del principio de inducción)", CMU Computer Science Report (disponible como informe técnico AD-759 248, Servicio Nacional de Información Técnica, Departamento de Comercio de 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 clasificación paralela", Avances en computadoras , 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.). Profesional de Addison-Wesley. 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. "Clasificación distribuida" (PDF) . Net.t-labs.tu-berlin.de . Consultado el 30 de julio de 2017 .