Ordenamiento binaria

1. Algoritmo de ordenamiento binaria
2. Ejemplo de ordenación binaria
3. Implementación del algoritmo de ordenación binaria
4. Complejidad del algoritmo de ordenamiento binaria

La ordenamiento binaria es un algoritmo de ordenación de tipo comparación. Es una modificación del algoritmo de ordenamiento por inserción. En este algoritmo, también mantenemos una submatriz ordenada y otra sin ordenar. La única diferencia es que encontramos la posición correcta de un elemento utilizando la búsqueda binaria en lugar de la búsqueda lineal. Esto ayuda a acelerar el algoritmo de ordenación reduciendo el número de comparaciones necesarias.

Algoritmo de ordenamiento binaria

Supongamos que tenemos un array sin ordenar A[] que contiene n elementos. El primer elemento, A[0], ya está ordenado y en la submatriz ordenada.

Ejemplo de ordenación binaria

Supongamos que tenemos el array (5,3,4,2,1,6). Lo ordenaremos utilizando el algoritmo de ordenación por inserción.

• Primera Iteración

Clave : A[1] = 3

Búsqueda binaria: devuelve la posición de 3 como índice 0. Desplazamiento a la derecha del resto de elementos del array ordenada.

• Segunda Iteración

Clave : A[2] = 4

Búsqueda binaria: devuelve la posición de 4 como índice 1. Desplazamiento a la derecha del resto de elementos del array ordenada.

• Tercera Iteración

Clave : A[3] = 2

Búsqueda binaria: devuelve la posición de 2 como índice 0. Desplazamiento a la derecha del resto de elementos del array ordenada.

• Cuarta Iteración

Clave : A[4] = 1

Búsqueda binaria: devuelve la posición de 1 como índice 0. Desplazamiento a la derecha del resto de elementos del array ordenada.

• Quinta Iteración

Clave : A[5] = 6

Búsqueda binaria: devuelve la posición de 6 como índice 5. No hay elementos en el lado derecho.

Obtenemos el array ordenado después de la cuarta iteración - (1 2 3 4 5 6)

Implementación del algoritmo de ordenación binaria

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int a[], int x, int low, int high) {
  if (high <= low) return (x > a[low]) ? (low + 1) : low;

  int mid = (low + high) / 2;

  if (x == a[mid]) return mid + 1;

  if (x > a[mid]) return binarySearch(a, x, mid + 1, high);
  return binarySearch(a, x, low, mid - 1);
}

void binarySort(int a[], int n) {
  for (int i = 1; i < n; ++i) {
    int j = i - 1;
    int key = a[i];
    int pos = binarySearch(a, key, 0, j);
    while (j >= pos) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  binarySort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo de ordenamiento binaria

Complejidad temporal

• Caso medio

La búsqueda binaria tiene una complejidad logarítmica logn comparada con la complejidad lineal n de la búsqueda lineal utilizada en la ordenación por inserción. Utilizamos la ordenación binaria para n elementos lo que nos da la complejidad temporal nlogn. Por tanto, la complejidad temporal es del orden de [Big Theta]: O(nlogn).

• El peor caso

El peor caso se produce cuando el array está ordenada de forma inversa y se requiere el máximo número de desplazamientos. La complejidad temporal en el peor caso es del orden de [Big O]: O(nlogn).

• El mejor caso

El mejor caso se produce cuando el array ya está ordenada y no es necesario desplazar elementos. La complejidad temporal en el mejor caso es [Big Omega]: O(n).

Complejidad espacial

La complejidad espacial del algoritmo de ordenación binaria es O(n) porque no se necesita más memoria que una variable temporal.