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[1]​) 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.[2]​

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.[3]​

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.[4]​

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:

function oddEvenSort(list) {
  function swap( list, i, j ){
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
  }

  var sorted = false;
  while(!sorted)
  {
    sorted = true;
    for(var i = 1; i < list.length-1; i += 2)
    {
      if(list[i] > list[i+1])
      {
        swap(list, i, i+1);
        sorted = false;
      }
    }

    for(var i = 0; i < list.length-1; i += 2)
    {
      if(list[i] > list[i+1])
      {
        swap(list, i, i+1);
        sorted = false;
      }
    }
  }
}

Esto es un ejemplo del algoritmo en c++

 template <class T>
void OddEvenSort (T a[], int n)
{
    for (int i = 0 ; i < n ; i++)
    {
         if (i & 1) // 'i' is odd
         {
             for (int j = 2 ; j < n ; j += 2)
             {     
                  if (a[j] < a[j-1])
                      swap (a[j-1], a[j]) ;
             }
          }
          else
          {  
              for (int j = 1 ; j < n ; j += 2)
              {
                   if (a[j] < a[j-1])
                       swap (a[j-1], a[j]) ;
              } 
          }
    }
}

Esto es un ejemplo del algoritmo en php

function oddEvenSorting(&$a) {
	$n = count($a);
	$sorted = false;
	while (!$sorted) {
		$sorted = true;
		for ($i = 1; $i < ($n - 1); $i += 2) {
			if ($a[$i] > $a[$i + 1]) {
				list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
				if ($sorted) $sorted = false;
			}
		}
		
		for ($i = 0; $i < ($n - 1); $i += 2) {
			if ($a[$i] > $a[$i + 1]) {
				list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
				if ($sorted) $sorted = false;
			}
		}
	}
}

Esto es un ejemplo del algoritmo en python.

def oddevenSort(x):
	sorted = False
	while sorted == False:
		sorted = True

		for i in range(0, len(x)-1, 2):
			if x[i] > x[i+1]:
				x[i], x[i+1] = x[i+1], x[i]
				sorted = False
		for i in range(1, len(x)-1, 2):
			if x[i] > x[i+1]:
				x[i], x[i+1] = x[i+1], x[i]
				sorted = False
	return x

Esto es un ejemplo del algoritmo en MATLAB/OCTAVA.

function x = oddevenSort(x)
sorted = false;
n = length(x);
while ~sorted
    sorted = true;
    for ii=1:2:n-1
        if x(ii) > x(ii+1)
            
            [x(ii), x(ii+1)] = deal(x(ii+1), x(ii));
            sorted = false;
        end
    end
    for ii=2:2:n-1
        if x(ii) > x(ii+1)
            [x(ii), x(ii+1)] = deal(x(ii+1), x(ii));
            sorted = false;
        end
    end
end

Demostración de la correctitud

Hipótesis: Sean ${\displaystyle a_{1},...,a_{n}}$ una secuencia de datos ordenados por ${\displaystyle <}$. El algoritmo de ordenación impar-par ordena correctamente esta secuencia de datos en ${\displaystyle 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.[5]​

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,[6]​[7]​ es suficiente comprobar la correctitud cuando cada ${\displaystyle a_{i}}$ es 0 o 1. Se asume que existen ${\displaystyle 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 ${\displaystyle n-e}$ pasos. Luego se puede concluir que toma a lo sumo ${\displaystyle 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 ${\displaystyle e-1}$ desde la cual tiene que ser movido a lo sumo a la posición ${\displaystyle n-1}$, entonces tiene que ser movido a lo sumo a la posición ${\displaystyle (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 ${\displaystyle 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 ${\displaystyle i}$-ésimo 1 más a la derecha está movido a su posición correcta en como máximo ${\displaystyle n-e+i+1}$ pasadas. Sigue que el ${\displaystyle e}$-ésimo 1 más a la derecha es movido a su posición correcta en como máximo ${\displaystyle n-e+(e-1)+1=n}$ pasadas (consideración: se comienza contando en el valor "0"). La lista es así ordenada correctamente en ${\displaystyle n}$ pasadas.

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

Referencias

1. Phillips, Malcolm. «Array Sorting». Archivado desde el original el 28 de octubre de 2011. Consultado el 3 de agosto de 2011. 
2. N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151).
3. S. Lakshmivarahan, S. K. Dhall, and L. L. Miller (1984), «Parallel Sorting Algorithms», en Franz L. Alt and Marshall C. Yovits, ed., Advances in computers (Academic Press) 23: 295-351, ISBN 978-0-12-012123-6 .
4. Allen Kent and James G. Williams (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. pp. 33-38. ISBN 978-0-8247-2282-1. 
5. http://liinwww.ira.uka.de/~thw/vl-hiroshima/slides-4.pdf
6. «Copia archivada». Archivado desde el original el 3 de noviembre de 2015. Consultado el 23 de octubre de 2015. 
7. «Copia archivada». Archivado desde el original el 4 de marzo de 2016. Consultado el 23 de octubre de 2015. 

• Datos: Q578580