Combinar algoritmo de ordenación

En este tutorial, aprenderá sobre la ordenación combinada. Además, encontrará ejemplos prácticos de combinación de clases C, C ++, Java y Python.

Merge Sort es uno de los algoritmos de clasificación más populares que se basa en el principio de Divide and Conquer Algorithm.

Aquí, un problema se divide en múltiples subproblemas. Cada subproblema se resuelve individualmente. Finalmente, los subproblemas se combinan para formar la solución final.

Ejemplo de combinación de ordenación

Estrategia de divide y vencerás

Usando la técnica Divide and Conquer , dividimos un problema en subproblemas. Cuando la solución a cada subproblema está lista, 'combinamos' los resultados de los subproblemas para resolver el problema principal.

Supongamos que tuviéramos que ordenar una matriz A. Un subproblema sería ordenar una subsección de esta matriz comenzando en el índice py terminando en el índice r, denotado como A (p… r).

Dividir
Si q es el punto medio entre py r, entonces podemos dividir el subarreglo A (p… r) en dos arreglos A (p… q) y A (q + 1, r).

Conquista
En el paso de conquista, intentamos ordenar los subarreglos A (p… q) y A (q + 1, r). Si aún no hemos llegado al caso base, nuevamente dividimos estos dos subarreglos e intentamos ordenarlos.

Combinar
Cuando el paso de conquista alcanza el paso base y obtenemos dos subarreglos ordenados A (p… q) y A (q + 1, r) para el arreglo A (p… r), combinamos los resultados creando un arreglo ordenado A ( p… r) de dos subarreglos ordenados A (p… q) y A (q + 1, r).

El algoritmo MergeSort

La función MergeSort divide repetidamente la matriz en dos mitades hasta que llegamos a una etapa en la que intentamos realizar MergeSort en una submatriz de tamaño 1, es decir, p == r.

Después de eso, entra en juego la función de combinación y combina las matrices ordenadas en matrices más grandes hasta que se fusiona toda la matriz.

 MergeSort (A, p, r): si p> r devuelve q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r )

Para ordenar una matriz completa, necesitamos llamar MergeSort(A, 0, length(A)-1).

Como se muestra en la imagen a continuación, el algoritmo de clasificación por fusión divide recursivamente la matriz en mitades hasta que llegamos al caso base de la matriz con 1 elemento. Después de eso, la función de fusión recoge las submatrices ordenadas y las fusiona para ordenar gradualmente toda la matriz.

Fusionar ordenación en acción

La combinación de Paso de Merge Ordenar

Cada algoritmo recursivo depende de un caso base y de la capacidad de combinar los resultados de los casos base. Fusionar ordenación no es diferente. La parte más importante del algoritmo de ordenación por combinación es, lo adivinó, el paso de combinación.

El paso de fusión es la solución al simple problema de fusionar dos listas ordenadas (matrices) para construir una lista ordenada grande (matriz).

El algoritmo mantiene tres punteros, uno para cada una de las dos matrices y otro para mantener el índice actual de la matriz ordenada final.

¿Hemos llegado al final de alguna de las matrices? No: Comparar los elementos actuales de ambas matrices Copiar el elemento más pequeño en una matriz ordenada Mover el puntero del elemento que contiene el elemento más pequeño Sí: Copiar todos los elementos restantes de la matriz no vacía
Combinar paso

Escribir el código para el algoritmo de fusión

Una diferencia notable entre el paso de combinación que describimos anteriormente y el que usamos para la ordenación por combinación es que solo realizamos la función de combinación en submatrices consecutivas.

Es por eso que solo necesitamos el arreglo, la primera posición, el último índice del primer subarreglo (podemos calcular el primer índice del segundo subarreglo) y el último índice del segundo subarreglo.

Nuestra tarea es fusionar dos subarreglos A (p… q) y A (q + 1… r) para crear un arreglo ordenado A (p… r). Entonces las entradas a la función son A, p, qyr

La función de combinación funciona de la siguiente manera:

  1. Cree copias de los subarreglos L ← A(p… q)y M ← A (q + 1… r).
  2. Crea tres punteros i, j y k
    1. mantengo el índice actual de L, comenzando en 1
    2. j mantiene el índice actual de M, comenzando en 1
    3. k mantiene el índice actual de A (p… q), comenzando en p.
  3. Hasta que lleguemos al final de L o M, escoge el más grande entre los elementos de L y M y colócalos en la posición correcta en A (p… q)
  4. Cuando nos quedemos sin elementos en L o M, recoge los elementos restantes y coloca A (p… q)

En código, esto se vería así:

 // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )

Función Merge () explicada paso a paso

Están sucediendo muchas cosas en esta función, así que tomemos un ejemplo para ver cómo funcionaría.

Como de costumbre, una imagen vale más que mil palabras.

Fusionando dos subarreglos consecutivos de matriz

El arreglo A (0… 5) contiene dos subarreglos ordenados A (0… 3) y A (4… 5). Veamos cómo la función de combinación fusionará las dos matrices.

 void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)

Paso 1: cree copias duplicadas de submatrices para ordenar

  // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9)
Crear copias de subarreglos para fusionar

Paso 2: mantener el índice actual de submatrices y matriz principal

  int i, j, k; i = 0; j = 0; k = p;
Mantener índices de copias de submatriz y matriz principal

Paso 3: hasta que lleguemos al final de L o M, elija más grande entre los elementos L y M y colóquelos en la posición correcta en A (p… r)

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
Comparar elementos individuales de subarreglos ordenados hasta llegar al final de uno

Paso 4: Cuando nos quedemos sin elementos en L o M, recoge los elementos restantes y coloca A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Copie los elementos restantes de la primera matriz al subarreglo principal 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Copie los elementos restantes de la segunda matriz al subarreglo principal

Este paso habría sido necesario si el tamaño de M fuera mayor que L.

Al final de la función de combinación, se ordena el subarreglo A (p… r).

Ejemplos de Python, Java y C / C ++

Python Java C C ++ 
 # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array) 
 // Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
 // Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
 // Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )

Combinar complejidad de ordenación

Complejidad del tiempo

Mejor complejidad de caso: O (n * log n)

Peor complejidad del caso: O (n * log n)

Complejidad de casos promedio: O (n * log n)

Complejidad espacial

La complejidad espacial de la ordenación por fusión es O (n).

Combinar aplicaciones de clasificación

  • Problema de recuento de inversiones
  • Clasificación externa
  • Aplicaciones de comercio electrónico

Articulos interesantes...