Ordenamiento Tim

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

Ordenamiento Tim es un algoritmo híbrido de ordenación estable. Es un algoritmo híbrido derivado de la ordenación por inserción y la ordenación por fusión. Primero realiza subarreglos utilizando la ordenación por inserción; estos pequeños subarreglos ordenados se denominan ejecuciones naturales. Estos recorridos se fusionan con subarrayas utilizando la ordenación por fusión para producir matrices ordenadas finales. Está diseñado teniendo en cuenta el rendimiento óptimo del algoritmo en datos del mundo real. Utiliza el hecho de que la ordenación por inserción funciona muy bien en submatrices de pequeño tamaño. Es el algoritmo de ordenación estándar utilizado por Array.sort() de Java y sorted() y sort() de Python.

Algoritmo de Ordenamiento Tim

Supongamos que tenemos un array A[] sin ordenar que contiene n elementos. Consideraremos que el tamaño de la array es 32. Puede ser cualquier potencia de 2 porque la fusión es más efectiva cuando los números son de potencias de 2.

TimSort()

Merge()

Ejemplo de Ordenamiento Tim

Supongamos que tenemos el array (3, 5, 2, 8, 1, 7, 6, 4). Vamos a ordenarlo utilizando el algoritmo de Ordenamiento Tim. Para simplificar la ilustración, consideremos que el tamaño de la array es 4.

Dividamos la array en dos submatrices: (3, 5, 2, 8) y (1, 7, 6, 4).

La primera subarray: (3, 5, 2, 8)

• Primera Iteración

Clave : A[1] = 5

• Segunda Iteración

Clave : A[2] = 4

• Tercera Iteración

Clave: A[3] = 2

El segundo subarray:(1,7,6,4)

• Primera iteración

Clave : A[1] = 7

• Segunda Iteración

Clave : A[2] = 6

• Tercera Iteración

Clave : A[3] = 4

Fusiona las dos submatrices ordenadas para obtener la subarray final como (1, 2, 3, 4, 5, 6, 7, 8)

Implementación del algoritmo Ordenamiento Tim

#include <bits/stdc++.h>
using namespace std;
const int RUN = 32;

void insertionSort(int arr[], int left, int right) {
  for (int i = left + 1; i <= right; i++) {
    int temp = arr[i];
    int j = i - 1;
    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

void merge(int arr[], int beg, int mid, int end) {
  int output[end - beg + 1];
  int i = beg, j = mid + 1, k = 0;
  // add smaller of both elements to the output
  while (i <= mid && j <= end) {
    if (arr[i] <= arr[j]) {
      output[k] = arr[i];
      k += 1;
      i += 1;
    } else {
      output[k] = arr[j];
      k += 1;
      j += 1;
    }
  }
  // remaining elements from first array
  while (i <= mid) {
    output[k] = arr[i];
    k += 1;
    i += 1;
  }
  // remaining elements from the second array
  while (j <= end) {
    output[k] = arr[j];
    k += 1;
    j += 1;
  }
  // copy output to the original array
  for (i = beg; i <= end; i += 1) {
    arr[i] = output[i - beg];
  }
}
void timSort(int arr[], int n) {
  for (int i = 0; i < n; i += RUN)
    insertionSort(arr, i, min((i + 31), (n - 1)));

  for (int size = RUN; size < n; size = 2 * size) {
    for (int left = 0; left < n; left += 2 * size) {
      int mid = left + size - 1;
      int right = min((left + 2 * size - 1), (n - 1));

      merge(arr, left, mid, right);
    }
  }
}

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

Complejidad del algoritmo Ordenamiento Tim

Complejidad temporal

• Caso medio

El algoritmo requiere O(nlogn) comparaciones para ordenar un array de n elementos. Por tanto, la complejidad temporal es del orden de [Big Theta]: O(nlogn).

• El peor caso

En el peor de los casos, se requieren nlogn comparaciones. La complejidad temporal en el peor de los casos es [Big O]: O(nlogn). Es lo mismo que la complejidad temporal del caso medio.

• El mejor caso

El mejor caso se produce cuando la array ya está ordenada y no se requieren intercambios. La complejidad temporal del mejor caso es [Big Omega]: O(n).

Complejidad espacial

La complejidad espacial de este algoritmo es O(n) porque el algoritmo de ordenación por fusión requiere un espacio auxiliar extra de O(n).