Ordenamiento Shell

1. Algoritmo de Ordenamiento Shell
2. Ejemplo de Ordenamiento Shell
3. Implementación del algoritmo Ordenamiento Shell
4. Complejidad del algoritmo Ordenamiento Shell

Ordenamiento Shell es un algoritmo de ordenación altamente eficiente basado en la comparación. Se considera la generalización del algoritmo de ordenación por burbujas o un algoritmo de ordenación por inserción optimizado. En el algoritmo de ordenación por inserción, movemos los elementos una posición hacia adelante. Pero en el caso de la ordenación de concha, movemos los elementos h posiciones por delante. Comienza ordenando elementos muy lejanos y reduce gradualmente la distancia basándose en una secuencia para ordenar todo el array. Algunas de las secuencias utilizadas son

Algoritmo de Ordenamiento Shell

Supongamos que tenemos un array sin ordenar A[] que contiene n elementos. Utilizaremos la secuencia original del shell para ordenar el array.

Ejemplo de Ordenamiento Shell

Supongamos que tenemos el array (9, 8, 3, 7, 5, 6, 4, 1). Vamos a ordenarlo utilizando el algoritmo de ordenación en cascarón y utilizando la secuencia original del cascarón para reducir los intervalos de separación.

• Primera iteración

n/2 = 4 , los elementos que se encuentran en el intervalo 4 se comparan y se intercambian.

A[0] > A[4] → intercambiados, (5,8,3,7,9,6,4,1).

A[1] > A[5] → intercambiado, (5,6,3,7,9,8,4,1).

A[2] < A[6]

A[3] > A[7] → intercambiado, (5,6,3,1,9,8,4,7).

El array se convierte en: (5,6,3,1,9,8,4,7).

• Segunda Iteración

n/4 = 2, los elementos que se encuentran en el intervalo 2 se comparan y se intercambian.

A[0] > A[2] → intercambiados, (3,6,5,1,9,8,4,7).

A[1] > A[3] → intercambiado, (3,1,5,6,9,8,4,7).

A[0] < A[2] < A[4]

A[1] < A[3] < A[5]

A[2] > A[4] y A[4] > A[6] → intercambiados, (3,1,4,6,5,8,9,7).

A[1] < A[3] < A[5] pero A[5] > A[7] → intercambiado, (3,1,4,6,5,7,9,8).

El array se convierte en: (3,1,4,6,5,7,9,8).

• Tercera Iteración

n/8 = 1, los elementos que se encuentran en el intervalo 1 se comparan y se intercambian.

A[0] > A[1] → intercambiado, (1,3,4,6,5,7,9,8).

A[0] .. A[2] → ordenado

A[0] .. A[3] → ordenado

A[0] .. A[3] → ordenado pero A[3] > A[4] → intercambiado, (1,3,4,5,6,7,9,8).

A[0] .. A[5] → ordenado

A[0] .. A[6] → ordenado

A[0] .. A[6] → ordenado pero A[6] > A[7] → intercambiado, (1, 3, 4, 5, 6, 7, 8, 9).

Implementación del algoritmo Ordenamiento Shell

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
int main() {
  int n = 8;
  int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  shellSort(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 Shell

Complejidad temporal

• Caso medio

La complejidad depende de la secuencia elegida para la ordenación. La complejidad temporal es del orden de [Big Theta]: O(nlog(n)²).

• El peor caso

La complejidad temporal en el peor de los casos para la ordenación en cascarón es siempre menor que igual a O(n²). Más concretamente, según el teorema de Poonen, viene dada por Θ(nlogn)²/(log n)²) o Θ(nlog n)²/log log n) o Θ(n(log n)^{) o algo intermedio. La complejidad temporal en el peor de los casos es [Big O]: menos que igual a O(n2).}

• El mejor caso

El mejor caso ocurre cuando el array ya está ordenado y las comparaciones necesarias para cada intervalo son iguales al tamaño del array. La complejidad temporal del mejor caso es [Big Omega]: O(nlogn).

Complejidad espacial

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