Ordenamiento impar-par
# Ordenamiento impar-par

En computación, una ordenación impar-par o ordenación por transposición impar-par (también conocido como ordenación por ladrillos) es un algoritmo de ordenación relativamente sencillo, desarrollado originalmente para uso en procesadores paralelos con interconexiones locales. Basa su funcionamiento en comparaciones; parecido al ordenamiento de burbuja, con el cual comparte muchas características. Funciona comparando todos los pares (elementos adyacentes) con índices impar/par que se encuentran en la lista y, si un par está en el orden incorrecto (el primero es más grande que el segundo) los elementos son reordenados. El próximo paso repite esto para pares adyacentes con índices par/impar que se encuentran en la lista. De esta forma alterna entre pares (de elementos adyacentes) impar/par y par/impar hasta que la lista se encuentre ordenada.

## Ordenando arreglos en procesadores

En procesadores paralelos, con un valor por procesador y solo conexiones locales de vecinos izquierda-derecha, los procesadores todos al mismo tiempo hacen operaciones de comparación e intercambio con sus vecinos, alternando entre pares con índices impar-par y par-impar. Este algoritmo era originalmente presentado, y mostrado para ser eficiente en tales procesadores, por Habermann en 1972.

El algoritmo se extiende perfectamente para el caso de elementos múltiples por procesador. En el algoritmo Baudet–Stevenson impar-par mezcla por divisiones, cada procesador ordena su propia sublista en cada paso, utilizando cualquier algoritmo de ordenación eficiente, y entonces se aplica un mezclador por divisiones o mezclador por transposición, operando con sus vecinos, aternando entre pares vecinos con índices impar-par y par-impar en cada paso.

## Ordenación por mezcla impar-par de Batcher

Un algoritmo parecido pero más eficiente es el de ordenación por mezcla impar-par de Batcher, utilizando operaciones de comparación e intercambio y operaciones de barajeo-perfecto. El método de Batcher es eficaz en procesadores paralelos con conexiones de largo rango.

## Algoritmo

El algoritmo de procesador único, como bubblesort, es sencillo pero no muy eficiente. En los siguientes ejemplos se asumen los índices en base cero:

Esto es un ejemplo del algoritmo en c++

Esto es un ejemplo del algoritmo en php

Esto es un ejemplo del algoritmo en python.

Esto es un ejemplo del algoritmo en MATLAB/OCTAVA.

## Demostración de la correctitud

Hipótesis: Sean $a_{1},...,a_{n}$ una secuencia de datos ordenados por $<$. El algoritmo de ordenación impar-par ordena correctamente esta secuencia de datos en $n$ pasos. (Un paso del algoritmo es definido como una secuencia completa de comparaciones impar-par, o par-impar. Los pasos ocurren en orden paso 1: impar-par, paso 2: par-impar, etc.)

Demostración:

Esta prueba está basada de forma aproximada en una realizada por Thomas Worsch.

Como el algoritmo de ordenación solo usa operaciones de comparaciones e intercambios de elementos y utiliza poca memoria (el orden de las operaciones de comparación e intercambio no depende de los datos), por el principio 0-1 de ordenación de Knuth, es suficiente comprobar la correctitud cuando cada $a_{i}$ es 0 o 1. Se asume que existen $e$ unos.

Observar que el 1 más a la derecha puede estar tanto en una posición par como en una impar, luego este no debe ser movido en la primera pasada impar-par del algoritmo. Pero después de la primera pasada impar-par dicho 1 se encontrará en una posición par. Este seguirá siendo movido a la derecha por las restantes pasadas del algoritmo. Por lo tanto el uno más a la derecha inicialmente se encuentra en una posición mayor o igual que e , tiene que ser movido a lo sumo $n-e$ pasos. Luego se puede concluir que toma a lo sumo $n-e+1$ pasos mover al 1 más a la derecha a su posición correcta

Ahora, consideremos el segundo 1 más a la derecha. Después de dos pasadas, el 1 a su derecha se habrá movido al menos un paso a la derecha. Luego para todas las pasadas restantes, podemos ver al segundo 1 como el 1 más a la derecha. El segundo 1 más a la derecha comienza al menos en la posición $e-1$ desde la cual tiene que ser movido a lo sumo a la posición $n-1$, entonces tiene que ser movido a lo sumo a la posición $(n-1)-(e-1)=n-e$ pasos. Después de como máximo 2 pasadas, el 1 más a la derecha ya ha sido movido, así que la entrada a la derecha del segundo 1 más a la derecha será 0. De ahí, para todas las pasadas después de las dos primeras, el segundo 1 más a la derecha se moverá a la derecha. Esto toma como máximo $n-e+2$ pasadas para lograr mover el segundo 1 más a la derecha a su posición correcta.

Continuando de esta manera, por inducción puede ser mostrado que el $i$-ésimo 1 más a la derecha está movido a su posición correcta en como máximo $n-e+i+1$ pasadas. Sigue que el $e$-ésimo 1 más a la derecha es movido a su posición correcta en como máximo $n-e+(e-1)+1=n$ pasadas (consideración: se comienza contando en el valor "0"). La lista es así ordenada correctamente en $n$ pasadas.

Remarcamos que cada paso toma $O(n)$ pasos, así que este algoritmo tiene complejidad $O(n^{2})$.

