Programa Python para ordenar por combinación
Combinar orden es una Divide y conquistaras algoritmo. Divide la matriz de entrada en dos mitades, se llama a sí mismo para las dos mitades y luego fusiona las dos mitades ordenadas. La función fusionar() se utiliza para fusionar dos mitades. La combinación (arr, l, m, r) es un proceso clave que supone que arr[l..m] y arr[m+1..r] están ordenados y fusiona los dos subarreglos ordenados en uno.
Programa Python para ordenar por combinación
El proporcionado Pitón El código implementa el algoritmo Merge Sort, una técnica de clasificación de divide y vencerás. Divide una matriz en submatrices más pequeñas, las clasifica individualmente y luego las vuelve a fusionar para crear una matriz ordenada. El código incluye dos funciones principales: merge, responsable de fusionar dos subarreglos, y mergeSort, que divide y ordena el arreglo de forma recursiva. La función de combinación combina dos subarreglos ordenados en un solo arreglo ordenado. La función mergeSort divide recursivamente la matriz por la mitad hasta que cada submatriz tiene un solo elemento, luego los fusiona para lograr el resultado final ordenado. El ejemplo ordena una matriz usando Merge Sort e imprime tanto la matriz inicial como la ordenada.
Python3
# Python program for implementation of MergeSort> # Merges two subarrays of arr[].> # First subarray is arr[l..m]> # Second subarray is arr[m+1..r]> def> merge(arr, l, m, r):> > n1> => m> -> l> +> 1> > n2> => r> -> m> > # create temp arrays> > L> => [> 0> ]> *> (n1)> > R> => [> 0> ]> *> (n2)> > # Copy data to temp arrays L[] and R[]> > for> i> in> range> (> 0> , n1):> > L[i]> => arr[l> +> i]> > for> j> in> range> (> 0> , n2):> > 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 and j if L[i] <= R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # Copy the remaining elements of L[], if there # are any while i arr[k] = L[i] i += 1 k += 1 # Copy the remaining elements of R[], if there # are any while j arr[k] = R[j] j += 1 k += 1 # l is for left index and r is right index of the # sub-array of arr to be sorted def mergeSort(arr, l, r): if l # Same as (l+r)//2, but avoids overflow for # large l and h m = l+(r-l)//2 # Sort first and second halves mergeSort(arr, l, m) mergeSort(arr, m+1, r) merge(arr, l, m, r) # Driver code to test above arr = [12, 11, 13, 5, 6, 7] n = len(arr) print('Given array is') for i in range(n): print('%d' % arr[i],end=' ') mergeSort(arr, 0, n-1) print('
Sorted array is') for i in range(n): print('%d' % arr[i],end=' ') # This code is contributed by Mohit Kumra> |
Producción
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13
Complejidad del tiempo: O(n*log(n))
Espacio Auxiliar: En)
Consulte el artículo completo sobre Combinar ordenar ¡para más detalles!
