Bitonic Sort

Bitonic Sort es un algoritmo de ordenación por comparación de los más eficientes para trabajar en computación paralela, su característica principal es el equilibrio de carga. Fue desarrollado por Ken E. Batcher en 1.964-8. Inicialmente estaba diseñada para que la longitud del vector n fuese ​​una potencia de 2. En el ejemplo se propone para una entrada n arbitraria.

 

Rendimiento – Complejidad
Mejor caso Ω	Peor caso O	Media Θ	Espacio
(log²n)	(log²n)	(log²n)	O(n log²n)

 

Bitonic compara los elementos en una secuencia predefinida, secuencia bitónica, que no debe depender de los datos que se ordenan. En la secuencia bitónica los elementos aparecen, primero en orden creciente (Monolítica creciente) y luego comienzan a disminuir (Monolítica decreciente) a partir de algún punto (índice) en concreto. Ese punto no existe si el vector solo está aumentando o disminuyendo (está ordenado).

 

El algoritmo realiza los siguientes pasos :

 

1. Divide el vector en 2 subvectores y estos sucesivamente entre 2 para obtener otros subvectores.
2. Compara los elementos entre pares (subvectores), primer elemento de la primera mitad con el primer elemento de la segunda mitad y así sucesivamente. En el supuesto de encontrar algún elemento de la segunda mitad más pequeño que de la primera, estos se intercambian (si el criterio que hemos elegido es orden creciente). Como resultado obtenemos que: En la primera mitad todos los elementos son menores que todos los elementos de la segunda mitad.
3. Repetimos el proceso realizado en el paso 2 por cada uno de los 2 subvectores principales y de forma indpendiente, así obtenemos el vector ordenado.

 

	Vector desordenado	41	66		21	85		9	60		30	15		28	74		99	49		1	47		72	33
1	Dividimos el vector en 2 subvectores y estos sucesivamente entre 2.
2	Intercambio entre pares	41	66	↔ ↓	85	21		9	60	↔ ↓	30	15		74	28	↔ ↓	49	16		47	1	↔ ↓	33	72
		41	21	↔ ↓	85	66		30	60	↔ ↓	9	15		74	99	↔ ↓	49	28		33	1	↔ ↓	47	72
	Intercambio entre subvectores	21	41		66	85	↙↘	60	30		15	9		99	74		49	28	↙↘	1	33		47	72
	Intercambio entre pares	21	30	↔ ↓	15	9		60	41	↔ ↓	66	85		99	74	↔ ↓	49	72		1	33	↔ ↓	47	28
	Intercambio entre subvectores	15	9		21	30	↙↘	60	41		66	85		99	74		49	72	↙↘	47	33		1	28
	Intercambio entre subvectores principales	9	15		21	30		41	60		66	85	↙↘	99	74		72	49		47	33		28	1
3
	Intercambio entre subvectores	9	15		21	30	↙↘	41	33		28	1		99	74		72	49	↙↘	47	60		66	85
	Intercambio entre pares	9	15	↔ ↓	21	1		41	33	↔ ↓	28	30		47	60	↔ ↓	66	49		99	74	↔ ↓	72	85
	Intercambio entre pares	9	1	↔ ↓	21	15		28	30	↔ ↓	41	33		47	49	↔ ↓	66	60		72	74	↔ ↓	99	85
													↓
	Vector ordenado	1	9		15	21		28	30		33	41		47	49		60	66		72	74		85	99

 

 

Ejemplo.

Están dos versiones en Java, una con monoprocesador y otra con 2 hilos (Thread) en paralelo. La diferencia en tiempo es importante, no tanto para pequeñas ordenaciones (puede invertirse la relación) que es algo en común con el resto de algoritmos. El equipo utilizado es el mismo del resumen de estadísticas de ordenación.

 

 

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación. El gráfico corresponde a la ejecución en monoprocesador.