La ordenación por combinación es uno de los algoritmos de ordenación más eficientes. Funciona según el principio de dividir y vencer, basado en la idea de dividir una lista en varias sublistas hasta que cada una de ellas conste de un único elemento y combinar esas sublistas de manera que se obtenga una lista ordenada.
Regla de trabajo de ordenación por combinación
El concepto de Divide y vencerás implica tres pasos:
- Divida el problema en varios subproblemas.
- Resolver los subproblemas. La idea es descomponer el problema en subproblemas atómicos, donde realmente se resuelven.
- Combine las soluciones de los subproblemas para encontrar la solución del problema real.
Entonces, la regla de funcionamiento de la ordenación por combinación implica los siguientes pasos:
- Divida la matriz no ordenada en submatrices, cada una de las cuales contiene un único elemento.
- Tome pares adyacentes de dos matrices de un solo elemento y fusionelos para formar una matriz de 2 elementos.
- Repita el proceso hasta obtener una única matriz ordenada.
Una matriz de tamaño ‘N’ se divide en dos partes de tamaño ‘N/2’ cada una. Luego, esas matrices se dividen aún más hasta que llegamos a un solo elemento. El caso base aquí es llegar a un solo elemento. Cuando se llega al caso base, comenzamos a fusionar la parte izquierda y la parte derecha y obtenemos una matriz ordenada al final. La ordenación por fusión divide repetidamente una matriz en varias submatrices hasta que cada submatriz consta de un solo elemento y fusiona esas submatrices de una manera que da como resultado una matriz ordenada.
Flujo del algoritmo de ordenación por fusión
Matriz = {70,50,30,10,20,40,60}
Dividimos repetidamente la matriz en dos partes, la parte izquierda y la parte derecha. La división se realiza a partir del elemento central. Dividimos hasta que llegamos a un solo elemento y luego comenzamos a combinarlos para formar una matriz ordenada.
Implementaciones de ordenamiento por combinación
Implementaremos el algoritmo de ordenación por fusión en Java, C y Python.
1. Implementación de Java
package com.journaldev.ds;public class MergeSort {public static void main(String[] args) {int[] arr = { 70, 50, 30, 10, 20, 40, 60 };int[] merged = mergeSort(arr, 0, arr.length - 1);for (int val : merged) {System.out.print(val + " ");}}public static int[] mergeTwoSortedArrays(int[] one, int[] two) {int[] sorted = new int[one.length + two.length];int i = 0;int j = 0;int k = 0;while (i one.length j two.length) {if (one[i] two[j]) {sorted[k] = one[i];k++;i++;} else {sorted[k] = two[j];k++;j++;}}if (i == one.length) {while (j two.length) {sorted[k] = two[j];k++;j++;}}if (j == two.length) {while (i one.length) {sorted[k] = one[i];k++;i++;}}return sorted;}public static int[] mergeSort(int[] arr, int lo, int hi) {if (lo == hi) {int[] br = new int[1];br[0] = arr[lo];return br;}int mid = (lo + hi) / 2;int[] fh = mergeSort(arr, lo, mid);int[] sh = mergeSort(arr, mid + 1, hi);int[] merged = mergeTwoSortedArrays(fh, sh);return merged;}}PRODUCCIÓN
2. C Implementación
#include stdio.hvoid merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L[n1], R[n2]; /* Copy data to temp arrays L[] and R[] */ for (i = 0; i n1; i++) L[i] = arr[l + i]; for (j = 0; j n2; j++) R[j] = arr[m + 1+ j]; /* Merge the temp arrays back into arr[l..r]*/ i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray while (i n1 j n2) { if (L[i] = R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* Copy the remaining elements of L[], if there are any */ while (i n1) { arr[k] = L[i]; i++; k++; } /* Copy the remaining elements of R[], if there are any */ while (j n2) { arr[k] = R[j]; j++; k++; } } /* l is for left index and r is the right index of the sub-array of arr to be sorted */void mergeSort(int arr[], int l, int r) { if (l r) { // Same as (l+r)/2, but avoids overflow for // large l and h int m = l+(r-l)/2; // Sort first and second halves mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge(arr, l, m, r); } } void printArray(int A[], int size) { int i; for (i=0; i size; i++) printf("%d ", A[i]); printf("n"); } /* Driver program to test above functions */int main() { int arr[] = {70, 50, 30, 10, 20, 40,60}; int arr_size = sizeof(arr)/sizeof(arr[0]); printf("Given array is n"); printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); printf("nSorted array is n"); printArray(arr, arr_size); return 0; } PRODUCCIÓN
3. Implementación de Python
def merge_sort(unsorted_array): if len(unsorted_array) 1: mid = len(unsorted_array) // 2 # Finding the mid of the array left = unsorted_array[:mid] # Dividing the array elements right = unsorted_array[mid:] # into 2 halves merge_sort(left) merge_sort(right) i = j = k = 0 # data to temp arrays L[] and R[] while i len(left) and j len(right): if left[i] right[j]: unsorted_array[k] = left[i] i += 1 else: unsorted_array[k] = right[j] j += 1 k += 1 # Checking if any element was left while i len(left): unsorted_array[k] = left[i] i += 1 k += 1 while j len(right): unsorted_array[k] = right[j] j += 1 k += 1# Code to print the listdef print_list(array1): for i in range(len(array1)): print(array1[i], end=" ") print()# driver code to test the above codeif __name__ == '__main__': array = [12, 11, 13, 5, 6, 7] print("Given array is", end="n") print_list(array) merge_sort(array) print("Sorted array is: ", end="n") print_list(array)PRODUCCIÓN
Complejidad temporal y espacial de la ordenación por fusión
1. Complejidad espacial
Espacio auxiliar: O(n) Ordenación en el lugar: No Algoritmo: Divide y vencerás
2. Complejidad temporal
Merge Sort es un algoritmo recursivo y la complejidad temporal se puede expresar como la siguiente relación de recurrencia. T(n) = 2T(n/2) + O(n) La solución de la recurrencia anterior es O(nLogn) . La lista de tamaño N se divide en un máximo de partes Logn, y la fusión de todas las sublistas en una sola lista lleva O(N) tiempo, el tiempo de ejecución en el peor de los casos de este algoritmo es O(nLogn). Complejidad temporal en el mejor caso: O(n*log n) Complejidad temporal en el peor caso: O(n*log n) Complejidad temporal promedio: O(n*log n) La complejidad temporal de MergeSort es O(n*Log n) en los 3 casos (peor, promedio y mejor) ya que el mergesort siempre divide la matriz en dos mitades y lleva un tiempo lineal fusionar dos mitades. Lecturas adicionales:
- Página de Wikipedia sobre ordenación por fusión
- Ordenamiento de burbuja en Java
- Ordenación por inserción en Java