Clasificación bitónica

Fondo

Bitonic Sort es un algoritmo paralelo clásico para ordenar. 

• La cantidad de comparaciones realizadas por Bitonic sort es más que los algoritmos de clasificación populares como Merge Sort [hace comparaciones O (log N)], pero Bitonice sort es mejor para la implementación paralela porque siempre comparamos elementos en una secuencia predefinida y la secuencia de comparación no No depende de los datos. Por lo tanto, es adecuado para la implementación en hardware y array de procesadores en paralelo .
• La ordenación bitónica debe realizarse si el número de elementos a ordenar es 2^n. El procedimiento de secuencia bitónica falla si el número de elementos no es precisamente en la cantidad antes mencionada.

Para entender Bitonic Sort, primero debemos entender qué es Bitonic Sequence y cómo hacer una secuencia bitónica determinada. 

Secuencia Bitónica

Una sucesión se llama bitónica si primero es creciente y luego decreciente. En otras palabras, un arreglo arr[0..ni] es bitónico si existe un índice I, donde 0<=i<=n-1 tal que  

x0 <= x1 …..<= xi  
and  
xi >= xi+1….. >= xn-1 

1. Una secuencia ordenada en orden creciente se considera bitónica con la parte decreciente vacía. De manera similar, la secuencia de orden decreciente se considera bitónica con la parte creciente como vacía.
2. Una rotación de la Secuencia bitónica también es bitónica.

¿Cómo formar una secuencia bitónica a partir de una entrada aleatoria?  
Empezamos formando secuencias bitónicas de 4 elementos a partir de secuencias consecutivas de 2 elementos. Considere 4 elementos en secuencia x0, x1, x2, x3. Ordenamos x0 y x1 en orden ascendente y x2 y x3 en orden descendente. Luego concatenamos los dos pares para formar una secuencia bitónica de 4 elementos. 
A continuación, tomamos dos secuencias bitónicas de 4 elementos, clasificando una en orden ascendente, la otra en orden descendente (usando el Ordenamiento Bitónico que discutiremos más adelante), y así sucesivamente, hasta obtener la secuencia bitónica.

Ejemplo: 
convertir la siguiente secuencia en una secuencia bitónica: 3, 7, 4, 8, 6, 2, 1, 5 

Paso 1 : Considere cada elemento consecutivo de 2 como una secuencia bitónica y aplique la ordenación bitónica en cada elemento de 2 pares. En el siguiente paso, tome secuencias bitónicas de 4 elementos y así sucesivamente.

Nota: x0 y x1 se ordenan en orden ascendente y x2 y x3 en orden descendente y así sucesivamente

Paso 2: dos secuencias bitónicas de 4 elementos: A (3,7,8,4) y B (2,6,5,1) con una longitud de comparación de 2
 

Después de este paso, obtendremos una secuencia bitónica de longitud 8. 

 3, 4, 7, 8, 6, 5, 2, 1

Clasificación bitónica

Algoritmo de clasificación bitónica:

• Se crea una secuencia bitónica.
• Comparación entre el elemento correspondiente de la secuencia bitónica.
• Intercambiando el segundo elemento de la secuencia.
• Intercambio del elemento adyacente.

Se trata principalmente de dos pasos.  

1. Forme una secuencia bitónica (discutida anteriormente en detalle). Después de este paso llegamos a la cuarta etapa en el siguiente diagrama, es decir, la array se convierte en {3, 4, 7, 8, 6, 5, 2, 1}
2. Creación de una secuencia ordenada a partir de una secuencia bitónica: después del primer estado r ep, la primera mitad se ordena en orden creciente y la segunda mitad en orden decreciente. 
   Comparamos el primer elemento de la primera mitad con el primer elemento de la segunda mitad, luego el segundo elemento de la primera mitad con el segundo elemento de la segunda, y así sucesivamente. Intercambiamos elementos si un elemento de la primera mitad es más pequeño. 
   Después de los pasos anteriores de comparación e intercambio, obtenemos dos secuencias bitónicas en la array. Vea la quinta etapa debajo del diagrama. En la quinta etapa tenemos {3, 4, 2, 1, 6, 5, 7, 8}. Si observamos más de cerca los elementos, podemos notar que hay dos secuencias bitónicas de longitud n/2, de modo que todos los elementos de la primera secuencia bitónica {3, 4, 2, 1} son más pequeños que todos los elementos de la segunda secuencia bitónica {6, 5, 7, 8}. 
   Repetimos el mismo proceso dentro de dos secuencias bitónicas y obtenemos cuatro secuencias bitónicas de longitud n/4 tales que todos los elementos de la secuencia bitónica más a la izquierda son más pequeños y todos los elementos de la más a la derecha. Vea la sexta etapa en el siguiente diagrama, las arrays son {2, 1, 3, 4, 6, 5, 7, 8}. 
   Si repetimos este proceso una vez más, obtenemos 8 secuencias bitónicas de tamaño n/8, que es 1. Dado que todas estas secuencias bitónicas están ordenadas y cada secuencia bitónica tiene un elemento, obtenemos la array ordenada.

A continuación se muestran las implementaciones de Bitonic Sort. 

/* C++ Program for Bitonic Sort. Note that this program
   works only when size of input is a power of 2. */
#include<bits/stdc++.h>
using namespace std;
 
/*The parameter dir indicates the sorting direction, ASCENDING
   or DESCENDING; if (a[i] > a[j]) agrees with the direction,
   then a[i] and a[j] are interchanged.*/
void compAndSwap(int a[], int i, int j, int dir)
{
    if (dir==(a[i]>a[j]))
        swap(a[i],a[j]);
}
 
/*It recursively sorts a bitonic sequence in ascending order,
  if dir = 1, and in descending order otherwise (means dir=0).
  The sequence to be sorted starts at index position low,
  the parameter cnt is the number of elements to be sorted.*/
void bitonicMerge(int a[], int low, int cnt, int dir)
{
    if (cnt>1)
    {
        int k = cnt/2;
        for (int i=low; i<low+k; i++)
            compAndSwap(a, i, i+k, dir);
        bitonicMerge(a, low, k, dir);
        bitonicMerge(a, low+k, k, dir);
    }
}
 
/* This function first produces a bitonic sequence by recursively
    sorting its two halves in opposite sorting orders, and then
    calls bitonicMerge to make them in the same order */
void bitonicSort(int a[],int low, int cnt, int dir)
{
    if (cnt>1)
    {
        int k = cnt/2;
 
        // sort in ascending order since dir here is 1
        bitonicSort(a, low, k, 1);
 
        // sort in descending order since dir here is 0
        bitonicSort(a, low+k, k, 0);
 
        // Will merge whole sequence in ascending order
        // since dir=1.
        bitonicMerge(a,low, cnt, dir);
    }
}
 
/* Caller of bitonicSort for sorting the entire array of
   length N in ASCENDING order */
void sort(int a[], int N, int up)
{
    bitonicSort(a,0, N, up);
}
 
// Driver code
int main()
{
    int a[]= {3, 7, 4, 8, 6, 2, 1, 5};
    int N = sizeof(a)/sizeof(a[0]);
 
    int up = 1;   // means sort in ascending order
    sort(a, N, up);
 
    printf("Sorted array: \n");
    for (int i=0; i<N; i++)
        printf("%d ", a[i]);
    return 0;
}

/* Java program for Bitonic Sort. Note that this program
   works only when size of input is a power of 2. */
public class BitonicSort
{
    /* The parameter dir indicates the sorting direction,
       ASCENDING or DESCENDING; if (a[i] > a[j]) agrees
       with the direction, then a[i] and a[j] are
       interchanged. */
    void compAndSwap(int a[], int i, int j, int dir)
    {
        if ( (a[i] > a[j] && dir == 1) ||
             (a[i] < a[j] && dir == 0))
        {
            // Swapping elements
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
 
    /* It recursively sorts a bitonic sequence in ascending
       order, if dir = 1, and in descending order otherwise
       (means dir=0). The sequence to be sorted starts at
       index position low, the parameter cnt is the number
       of elements to be sorted.*/
    void bitonicMerge(int a[], int low, int cnt, int dir)
    {
        if (cnt>1)
        {
            int k = cnt/2;
            for (int i=low; i<low+k; i++)
                compAndSwap(a,i, i+k, dir);
            bitonicMerge(a,low, k, dir);
            bitonicMerge(a,low+k, k, dir);
        }
    }
 
    /* This function first produces a bitonic sequence by
       recursively sorting its two halves in opposite sorting
       orders, and then  calls bitonicMerge to make them in
       the same order */
    void bitonicSort(int a[], int low, int cnt, int dir)
    {
        if (cnt>1)
        {
            int k = cnt/2;
 
            // sort in ascending order since dir here is 1
            bitonicSort(a, low, k, 1);
 
            // sort in descending order since dir here is 0
            bitonicSort(a,low+k, k, 0);
 
            // Will merge whole sequence in ascending order
            // since dir=1.
            bitonicMerge(a, low, cnt, dir);
        }
    }
 
    /*Caller of bitonicSort for sorting the entire array
      of length N in ASCENDING order */
    void sort(int a[], int N, int up)
    {
        bitonicSort(a, 0, N, up);
    }
 
    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    // Driver method
    public static void main(String args[])
    {
        int a[] = {3, 7, 4, 8, 6, 2, 1, 5};
        int up = 1;
        BitonicSort ob = new BitonicSort();
        ob.sort(a, a.length,up);
        System.out.println("\nSorted array");
        printArray(a);
    }
}

# Python program for Bitonic Sort. Note that this program
# works only when size of input is a power of 2.
 
# The parameter dir indicates the sorting direction, ASCENDING
# or DESCENDING; if (a[i] > a[j]) agrees with the direction,
# then a[i] and a[j] are interchanged.*/
def compAndSwap(a, i, j, dire):
    if (dire==1 and a[i] > a[j]) or (dire==0 and a[i] < a[j]):
        a[i],a[j] = a[j],a[i]
 
# It recursively sorts a bitonic sequence in ascending order,
# if dir = 1, and in descending order otherwise (means dir=0).
# The sequence to be sorted starts at index position low,
# the parameter cnt is the number of elements to be sorted.
def bitonicMerge(a, low, cnt, dire):
    if cnt > 1:
        k = cnt//2
        for i in range(low , low+k):
            compAndSwap(a, i, i+k, dire)
        bitonicMerge(a, low, k, dire)
        bitonicMerge(a, low+k, k, dire)
 
# This function first produces a bitonic sequence by recursively
# sorting its two halves in opposite sorting orders, and then
# calls bitonicMerge to make them in the same order
def bitonicSort(a, low, cnt,dire):
    if cnt > 1:
          k = cnt//2
          bitonicSort(a, low, k, 1)
          bitonicSort(a, low+k, k, 0)
          bitonicMerge(a, low, cnt, dire)
 
# Caller of bitonicSort for sorting the entire array of length N
# in ASCENDING order
def sort(a,N, up):
    bitonicSort(a,0, N, up)
 
# Driver code to test above
a = [3, 7, 4, 8, 6, 2, 1, 5]
n = len(a)
up = 1
 
sort(a, n, up)
print ("\n\nSorted array is")
for i in range(n):
    print("%d" %a[i],end=" ")

/* C# Program for Bitonic Sort. Note that this program
   works only when size of input is a power of 2. */
using System;
   
/*The parameter dir indicates the sorting direction, ASCENDING
   or DESCENDING; if (a[i] > a[j]) agrees with the direction,
   then a[i] and a[j] are interchanged.*/
class GFG
{
    /* To swap values */
    static void Swap<T>(ref T lhs, ref T rhs)
    {
        T temp;
        temp = lhs;
        lhs = rhs;
        rhs = temp;
    }
    public static void compAndSwap(int[] a, int i, int j, int dir)
    {
        int k;
        if((a[i]>a[j]))
            k=1;
        else
            k=0;
        if (dir==k)
            Swap(ref a[i],ref a[j]);
    }
       
    /*It recursively sorts a bitonic sequence in ascending order,
      if dir = 1, and in descending order otherwise (means dir=0).
      The sequence to be sorted starts at index position low,
      the parameter cnt is the number of elements to be sorted.*/
    public static void bitonicMerge(int[] a, int low, int cnt, int dir)
    {
        if (cnt>1)
        {
            int k = cnt/2;
            for (int i=low; i<low+k; i++)
                compAndSwap(a, i, i+k, dir);
            bitonicMerge(a, low, k, dir);
            bitonicMerge(a, low+k, k, dir);
        }
    }
       
    /* This function first produces a bitonic sequence by recursively
        sorting its two halves in opposite sorting orders, and then
        calls bitonicMerge to make them in the same order */
    public static void bitonicSort(int[] a,int low, int cnt, int dir)
    {
        if (cnt>1)
        {
            int k = cnt/2;
       
            // sort in ascending order since dir here is 1
            bitonicSort(a, low, k, 1);
       
            // sort in descending order since dir here is 0
            bitonicSort(a, low+k, k, 0);
       
            // Will merge whole sequence in ascending order
            // since dir=1.
            bitonicMerge(a,low, cnt, dir);
        }
    }
       
    /* Caller of bitonicSort for sorting the entire array of
       length N in ASCENDING order */
    public static void sort(int[] a, int N, int up)
    {
        bitonicSort(a,0, N, up);
    }
       
    // Driver code
    static void Main()
    {
        int[] a= {3, 7, 4, 8, 6, 2, 1, 5};
        int N = a.Length;
       
        int up = 1;   // means sort in ascending order
        sort(a, N, up);
       
        Console.Write("Sorted array: \n");
        for (int i=0; i<N; i++)
            Console.Write(a[i] + " ");
        }
        //This code is contributed by DrRoot_
}

<script>
 
      /* JavaScript program for Bitonic Sort.
      Note that this program
      works only when size of input is a power of 2. */
      /* The parameter dir indicates the sorting direction,
    ASCENDING or DESCENDING; if (a[i] > a[j]) agrees
    with the direction, then a[i] and a[j] are
    interchanged. */
      function compAndSwap(a, i, j, dir) {
        if ((a[i] > a[j] && dir === 1) ||
        (a[i] < a[j] && dir === 0))
        {
          // Swapping elements
          var temp = a[i];
          a[i] = a[j];
          a[j] = temp;
        }
      }
 
      /* It recursively sorts a bitonic sequence in ascending
    order, if dir = 1, and in descending order otherwise
    (means dir=0). The sequence to be sorted starts at
    index position low, the parameter cnt is the number
    of elements to be sorted.*/
      function bitonicMerge(a, low, cnt, dir) {
        if (cnt > 1) {
          var k = parseInt(cnt / 2);
          for (var i = low; i < low + k; i++)
          compAndSwap(a, i, i + k, dir);
          bitonicMerge(a, low, k, dir);
          bitonicMerge(a, low + k, k, dir);
        }
      }
 
      /* This function first produces a bitonic sequence by
    recursively sorting its two halves in opposite sorting
    orders, and then calls bitonicMerge to make them in
    the same order */
      function bitonicSort(a, low, cnt, dir) {
        if (cnt > 1) {
          var k = parseInt(cnt / 2);
 
          // sort in ascending order since dir here is 1
          bitonicSort(a, low, k, 1);
 
          // sort in descending order since dir here is 0
          bitonicSort(a, low + k, k, 0);
 
          // Will merge whole sequence in ascending order
          // since dir=1.
          bitonicMerge(a, low, cnt, dir);
        }
      }
 
      /*Caller of bitonicSort for sorting the entire array
    of length N in ASCENDING order */
      function sort(a, N, up) {
        bitonicSort(a, 0, N, up);
      }
 
      /* A utility function to print array of size n */
      function printArray(arr) {
        var n = arr.length;
        for (var i = 0; i < n; ++i)
        document.write(arr[i] + " ");
        document.write("<br>");
      }
 
      // Driver method
      var a = [3, 7, 4, 8, 6, 2, 1, 5];
      var up = 1;
      sort(a, a.length, up);
      document.write("Sorted array: <br>");
      printArray(a);
       
</script>

Producción:  

Sorted array: 
1 2 3 4 5 6 7 8

Análisis de ordenación bitónica

Para formar una secuencia ordenada de longitud n a partir de dos secuencias ordenadas de longitud n/2, se requieren comparaciones log(n).

Por ejemplo: log(8) = 3 cuando el tamaño de la secuencia. Por lo tanto, el número de comparaciones T(n) de toda la clasificación viene dado por:

T(n) = log(n) + T(n/2)

La solución de esta ecuación de recurrencia es

T(n) = log(n) + log(n)-1 + log(n)-2 + ... + 1 = log(n) · (log(n)+1) / 2

Como cada etapa de la red de clasificación consta de n/2 comparadores. Por lo tanto total O (n log ² n) comparadores.

Complejidad del tiempo :

• Mejor caso: O (log ² n)
• Caso Promedio: O(log ² n)
• Peor caso: O(log ² n)

Complejidad espacial : O(n.log ² n)

Estable : Si

Puntos importantes :

• Es una técnica de clasificación basada en la comparación.
• Los elementos se ordenan según la secuencia bitónica.
• Implementado fácilmente en computación paralela
• Más eficiente que Quicksort
• El número de comparaciones es mayor que otros algoritmos.
• Una secuencia con elementos en orden creciente y decreciente es una secuencia bitónica.
• La memoria es bien manejada por el proceso.
• Ideal para arreglos de procesadores paralelos.

Este artículo es una contribución de Rahul Agarwal. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.