Ordenamiento por mezcla

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

La Ordenamiento por mezcla es uno de los algoritmos de ordenación más populares y eficientes. Se basa en el principio del algoritmo divide y vencerás. Funciona dividiendo el array en dos mitades repetidamente hasta que obtenemos el array dividido en elementos individuales. Un elemento individual es un array ordenado en sí mismo. La ordenamiento por mezcla combina repetidamente estas pequeñas matrices ordenadas para producir submatrices ordenadas más grandes hasta que obtenemos una array final ordenada. Se utiliza mucho en aplicaciones de comercio electrónico.

Algoritmo de ordenamiento por mezcla

El método de ordenamiento por mezcla descendente comienza desde la parte superior con el array completo y procede hacia abajo a los elementos individuales con recursión.

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

MergeSort()

Merge()

Ejemplo de ordenamiento por mezcla

Supongamos que tenemos el array (5,3,4,2,1,6). Vamos a ordenarlo utilizando el algoritmo de ordenamiento por mezcla.

Obtenemos el array ordenado - (1 2 3 4 5 6)

Implementación del algoritmo Ordenamiento por mezcla

#include <iostream>
using namespace std;

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 mergeSort(int arr[], int beg, int end) {
  if (beg < end) {
    int mid = (beg + end) / 2;
    // divide and conquer
    mergeSort(arr, beg, mid);      // divide : first half
    mergeSort(arr, mid + 1, end);  // divide: second half
    merge(arr, beg, mid, end);     // conquer
  }
}
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";
  mergeSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo Ordenamiento por mezcla

Complejidad temporal

• Caso medio

Merge Sort es un algoritmo recursivo. La siguiente relación de recurrencia da la expresión de la complejidad temporal de Merge sort.

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

El resultado de esta relación de recurrencia da T(n) = nLogn.También podemos verlo como un array de tamaño n que se divide en un máximo de Logn partes, y la fusión de cada parte toma O(n) tiempo.

Por tanto, la complejidad temporal es del orden de [Big Theta]: O(nLogn).

• El peor caso

La complejidad temporal en el peor de los casos es del orden de [Big O]: O(nLogn).

• El mejor caso

La complejidad temporal en el mejor de los casos es [Big Omega]: O(nLogn). Es la misma que la complejidad temporal del peor caso.

Complejidad espacial

La complejidad espacial del algoritmo Ordenamiento por mezcla es O(n) porque se necesita n espacio auxiliar para almacenar la subarray ordenada en la array auxiliar.