Ordenamiento por casilleros

1. Algoritmo de ordenamiento por casilleros
2. Ejemplo de ordenamiento por casilleros
3. Implementación del algoritmo ordenamiento por casilleros
4. Complejidad del algoritmo Ordenamiento por casilleros

Ordenamiento por casilleros es un algoritmo de ordenación de tipo comparación. Ordena los elementos distribuyéndolos en cubos o contenedores y utilizando un algoritmo diferente (normalmente la ordenación por inserción) para ordenar el contenido de los cubos individuales. Los cubos individuales ordenados se añaden juntos para obtener la array final ordenada. Este enfoque de algoritmo de ordenación también se conoce como enfoque de dispersión. Se utiliza principalmente cuando la entrada se distribuye uniformemente en un rango como los flotadores que van de 0.00 a 1.00.

Algoritmo de ordenamiento por casilleros

Supongamos que tenemos un array sin ordenar A[] que contiene n elementos.

Ejemplo de ordenamiento por casilleros

Supongamos que tenemos el array (0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). Vamos a ordenarlo utilizando el algoritmo de ordenación por cubos.

• Haz 10 cubos cada uno de rango 0.1.

• Después de insertar los elementos en los cubos obtenemos

• Ordenar los cubos individuales para obtener:

Sumando todos los resultados, obtenemos la array final ordenada como (0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55).

Implementación del algoritmo ordenamiento por casilleros

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

void bucketSort(float *array, int size) {
  vector<float> bucket[size];
  // insert elements into different buckets.
  for (int i = 0; i < size; i++) {
    bucket[int(size * array[i])].push_back(array[i]);
  }
  // sort individual buckets.
  for (int i = 0; i < size; i++) {
    sort(bucket[i].begin(), bucket[i].end());
  }

  int index = 0;
  for (int i = 0; i < size; i++) {
    while (!bucket[i].empty()) {
      array[index++] = *(bucket[i].begin());
      bucket[i].erase(bucket[i].begin());
    }
  }
}

int main() {
  int n = 8;
  float arr[8] = {0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bucketSort(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 Ordenamiento por casilleros

Complejidad temporal

• Caso medio

El caso medio se da si los elementos están distribuidos aleatoriamente, y el algoritmo da resultados muy eficientes. La complejidad temporal es del orden de [Big Theta]: O(n+k). Es uno de los pocos algoritmos con complejidad temporal media lineal, y esta complejidad se mantiene si la suma de los cuadrados de los tamaños de los cubos es lineal en n.

• El peor caso

El peor caso se produce cuando muchos elementos están muy cerca en la array y se agrupan en el mismo cubo. Esto elimina todas las ventajas de dividir las entradas en cubos, y la complejidad total pasa a depender del algoritmo de ordenación utilizado. La ordenación por inserción tiene una complejidad temporal en el peor de los casos de O(n²) cuando los elementos están en orden inverso. Por lo tanto, la complejidad temporal en el peor de los casos es [Big O]: O(n²).

• El mejor caso

El mejor caso se produce cuando los elementos se distribuyen uniformemente en todos los cubos, o se obtiene un array ya ordenado. La complejidad temporal total comprende el tiempo necesario para crear los cubos O(n) y el tiempo necesario para ordenar O(k). La complejidad temporal en el mejor de los casos es [Big Omega]: O(n+k).

Complejidad espacial

La complejidad espacial en el peor de los casos para el algoritmo de ordenamiento por casilleros es O(n*k), donde n es el número de elementos y k es el número de cubos. La complejidad espacial puede reducirse a O(n+k) reduciendo el espacio para mantener todos los elementos y almacenando punteros al inicio del cubo.