Please enable JavaScript.
Coggle requires JavaScript to display documents.
MÉTODOS DE ORDENAMIENTO, Descripción, Pseudocódigo, BigO
Mejor Caso,…
MÉTODOS DE ORDENAMIENTO
Selection Sort
Encuentra el elemento más pequeño en la lista y lo coloca al principio. Luego repite el proceso para los elementos restantes.
para i desde 0 hasta longitud del arreglo - 1
min = i
para j desde i+1 hasta longitud del arreglo
si arreglo[j] < arreglo[min]
min = j
intercambiar(arreglo[min], arreglo[i])
Peor caso: O(n²)
Mejor caso: O(n²) (porque sigue buscando el mínimo en cada ciclo)
Mejor caso: No cambia su comportamiento, incluso si la lista ya está ordenada.
Bubble Sort
Recorre repetidamente la lista y compara elementos adyacentes, intercambiándolos si están en el orden incorrecto. Este proceso se repite hasta que la lista esté ordenada.
para i desde 0 hasta longitud del arreglo - 1
para j desde 0 hasta longitud del arreglo - i - 1
si arreglo[j] > arreglo[j+1]
intercambiar(arreglo[j], arreglo[j+1])
Peor caso: O(n²)
Mejor caso: O(n) (cuando la lista ya está ordenada)
Mejor caso: Cuando la lista ya está ordenada, solo se realiza un recorrido para verificar que no hay más intercambios.
Insertion Sort
Recorre la lista y, en cada iteración, toma un elemento y lo inserta en su posición correcta en la porción ordenada de la lista.
para i desde 1 hasta longitud del arreglo - 1
valor = arreglo[i]
j = i - 1
mientras j >= 0 y arreglo[j] > valor
arreglo[j+1] = arreglo[j]
j = j - 1
arreglo[j+1] = valor
Peor caso: O(n²)
Mejor caso: O(n) (cuando la lista ya está ordenada)
Mejor caso: Ocurre cuando la lista ya está ordenada, en cuyo caso solo se recorre una vez.
Shell Sort
Es una generalización del método de inserción que comienza comparando elementos que están alejados entre sí, utilizando un valor de salto que disminuye con el tiempo.
Peor caso: O(n²), aunque en muchos casos es más eficiente que O(n²).
Mejor caso: O(n log n)
Mejor caso: Depende de la secuencia de saltos utilizada, pero puede alcanzar un rendimiento cercano a O(n log n).
longitud = longitud del arreglo
salto = longitud / 2
mientras salto > 0
para i desde salto hasta longitud - 1
valor = arreglo[i]
j = i
mientras j >= salto y arreglo[j - salto] > valor
arreglo[j] = arreglo[j - salto]
j = j - salto
arreglo[j] = valor
salto = salto / 2
Peine Sort (Comb Sort)
Similar al método burbuja, pero en lugar de comparar elementos adyacentes, se compara con un espacio mayor que va reduciéndose en cada pasada. Reduce el efecto de los elementos pequeños atrapados en la parte final de la lista.
public class CombSort {
void sort(int arr[]) {
int n = arr.length;
int gap = n;
boolean swapped = true;
while (gap != 1 || swapped) {
gap = (int) (gap / 1.3);
if (gap < 1) {
gap = 1;
}
swapped = false;
for (int i = 0; i < n - gap; i++) {
if (arr[i] > arr[i + gap]) {
int temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
swapped = true;
}
}
}
}
}
longitud = longitud del arreglo
gap = longitud
intercambiado = verdadero
mientras gap > 1 o intercambiado es verdadero
gap = max(1, gap / 1.3)
intercambiado = falso
para i desde 0 hasta longitud - gap
si arreglo[i] > arreglo[i + gap]
intercambiar(arreglo[i], arreglo[i + gap])
intercambiado = verdadero
Peor caso: O(n²)
Mejor caso: O(n log n)
Mejor caso: Similar al shell sort, depende del espaciado usado.
Shaker Sort
Una variante del método de burbuja que ordena en ambas direcciones en cada pasada, moviendo elementos grandes al final y elementos pequeños al principio.
intercambiado = verdadero
inicio = 0
fin = longitud del arreglo - 1
mientras intercambiado es verdadero
intercambiado = falso
para i desde inicio hasta fin - 1
si arreglo[i] > arreglo[i + 1]
intercambiar(arreglo[i], arreglo[i + 1])
intercambiado = verdadero
fin = fin - 1
para i desde fin - 1 hasta inicio
si arreglo[i] > arreglo[i + 1]
intercambiar(arreglo[i], arreglo[i + 1])
intercambiado = verdadero
inicio = inicio + 1
Peor caso: O(n²)
Mejor caso: O(n)
Mejor caso: Igual que el burbuja, cuando la lista ya está ordenada.
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-