Según yo, depende del tipo de datos, es decir, supongamos que si desea ordenar el tipo de datos de cadena, usó la clasificación lexicográfica y la selección del algoritmo de clasificación también depende del tamaño de los datos, es decir, si desea ordenar un tipo de datos grande, entonces uno vaya a la combinación de clasificación porque el tiempo de ejecución para el peor de los casos es o (n log n) y si su tipo de datos es entero y el tamaño es pequeño, entonces vaya para la clasificación, el peor tiempo de ejecución es o (n), así que este es el la forma en que elige su algoritmo de clasificación para que el tiempo de ejecución de su programa sea mínimo y todo el algoritmo clasifique los datos en orden ascendente si desea ordenar los datos que dependen de la raíz, entonces elija la clasificación de la raíz y la selección del algoritmo también depende de la disposición de los datos supone que sus datos ya están ordenados, entonces uno quiere ir a una clasificación rápida, pero este es el peor caso de clasificación rápida.
Entonces el algoritmo de clasificación depende de
- Tipo de datos
- Tamaño de datos
- disposición de los datos en la dirección de memoria
pero para lo básico, va a ordenar buble, ordenar por inserción, ordenar por selección, ordenar por fusión
- ¿Qué es el algoritmo de transformación de Burrows-Wheeler y cómo se usa en aplicaciones del mundo real?
- Cómo desarrollar un algoritmo para detectar rangos de negociación horizontales / patrones de consolidación
- ¿Un montón necesita usar una cola prioritaria?
- ¿Cuál es la diferencia entre estos dos métodos de inicialización de matrices Java?
- Estoy tratando de incrementar un elemento de matriz de caracteres inicializado a cero pero no puedo, ¿por qué?
código para ordenar por fusión
/* C program for Merge Sort */
#include
#include
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
merge(int
void
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 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+(rl)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* UTILITY FUNCTIONS */
/* Function to print an array */
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[] = {12, 11, 13, 5, 6, 7};
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;
}
Complejidad del tiempo: clasificación de matrices en diferentes máquinas. Merge Sort es un algoritmo recursivo y la complejidad del tiempo se puede expresar como la siguiente relación de recurrencia.
T (n) = 2T (n / 2) +
La recurrencia anterior se puede resolver utilizando el método del árbol de recurrencia o el método maestro. Cae en el caso II del Método Maestro y la solución de la recurrencia es
.
La complejidad de tiempo de Merge Sort es
En los 3 casos (peor, promedio y mejor), la ordenación por fusión siempre divide la matriz en dos mitades y toma tiempo lineal para fusionar las dos mitades.
Espacio auxiliar: O (n)
Paradigma algorítmico: divide y vencerás
Clasificación en el lugar: no en una implementación típica
Estable: sí