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.

 

Kenneth E. Batcher

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.

 

Bitonicsort. Ejemplo en Java (Monoprocesador)
Bitonicsort. Ejemplo en Java (Monoprocesador)
Bitonicsort. Ejemplo en Java (2 Hilos)
Bitonicsort. Ejemplo en Java (2 Hilos)

 

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.

 

 

Rendimiento algoritmo sort bitonic de 10 a 100 mil elementos

Rendimiento algoritmo sort bitonic de 100 mil a 1Millon de elementos