Nota importante: El pseudocódigo está destinado a ser una representación de alto nivel, no directamente ejecutable. Se centra en la * lógica * del algoritmo. La implementación del código real variará según el lenguaje de programación y los requisitos específicos.
1. Sorteo de burbujas
* Concepto: Pasa repetidamente a través de la lista, compara elementos adyacentes y los intercambia si están en el orden equivocado. Elementos más pesados "burbuja" hasta el final.
* pseudocódigo:
`` `` ``
Procedimiento Bubblesort (lista:matriz de elementos)
n =longitud (lista)
para i =0 a n-1 do
para j =0 a n-i-1 do
if list [j]> list [j+1] entonces
Lista de intercambio [j] y lista [j+1]
final si
finalizar
finalizar
procedimiento final
`` `` ``
* Eficiencia:
* Mejor caso: O (n) (cuando la lista ya está ordenada. Una versión optimizada puede detectar esto).
* Caso promedio: O (n
* peor de los casos: O (n
* Complejidad espacial: O (1) (ordenar en el lugar)
* Implementación: Muy simple de implementar.
* Casos de uso: Mayormente educativo. No es adecuado para grandes conjuntos de datos debido al bajo rendimiento. Puede ser útil para listas pequeñas y casi clasificadas si se optimizan.
2. Sorteo de selección
* Concepto: Encuentra el elemento mínimo en la porción no clasificada de la lista y lo cambia con el elemento al comienzo de la porción no organizada.
* pseudocódigo:
`` `` ``
Procedimiento Selectionsort (Lista:Mango de elementos)
n =longitud (lista)
para i =0 a n-1 do
// Encuentra el índice del elemento mínimo en la parte no organizada
min_index =i
para j =i+1 a n-1 do
if list [j]
final si
finalizar
// intercambia el elemento mínimo encontrado con el primer elemento
Lista de intercambio [i] y lista [min_index]
finalizar
procedimiento final
`` `` ``
* Eficiencia:
* Mejor caso: O (n
* Caso promedio: O (n
* peor de los casos: O (n
* Complejidad espacial: O (1) (ordenar en el lugar)
* Implementación: Relativamente simple.
* Casos de uso: Funciona un poco mejor que el tipo de burbujas en algunos casos, pero aún no es adecuado para conjuntos de datos grandes. El número de swaps se limita a O (N), lo que puede ser útil si las escrituras de memoria son caras.
3. Sorteo de inserción
* Concepto: Construye la lista ordenada de un elemento a la vez. Se itera a través de los datos de entrada, elimina un elemento a la vez, encuentra la posición correcta en la lista ordenada y la inserta allí.
* pseudocódigo:
`` `` ``
Procedimiento InservationsIrt (Lista:matriz de elementos)
n =longitud (lista)
para i =1 a n-1 do
clave =lista [i]
j =i - 1
// Mover elementos de la lista [0..i-1], que son mayores que la clave,
// a una posición antes de su posición actual
mientras que j> =0 y list [j]> clave hacer
Lista [J+1] =Lista [J]
J =J - 1
terminar mientras
Lista [j+1] =clave
finalizar
procedimiento final
`` `` ``
* Eficiencia:
* Mejor caso: O (n) (cuando la lista ya está ordenada)
* Caso promedio: O (n
* peor de los casos: O (n
* Complejidad espacial: O (1) (ordenar en el lugar)
* Implementación: Simple y eficiente para pequeños conjuntos de datos o datos casi clasificados.
* Casos de uso: Bueno para listas pequeñas o cuando espera que los datos de entrada se ordenen en su mayoría. Además, es un algoritmo * en línea * que significa que puede ordenar una lista tal como la recibe.
4. Fusionar Sort
* Concepto: Un algoritmo de división y conquista. Divide la lista en sublistas más pequeños, clasifica recursivamente a los sublistas y luego los combina nuevamente.
* pseudocódigo:
`` `` ``
Procedimiento MergeSort (Lista:Mango de elementos)
n =longitud (lista)
Si n <=1 entonces
Lista de devolución // ya ordenado
final si
// divide la lista en dos mitades
Mid =N / 2
LeftList =List [0 a Mid-1]
Lista derecha =Lista [Mid a N-1]
// Ordena recursivamente cada mitad
LeftList =Mergesort (LeftList)
Lista derecha =Mergesort (lista de rectas)
// fusionar las mitades ordenadas
Regresar fusion (lista izquierda, lista derecha)
procedimiento final
Procedimiento Fusionar (LeftList:Matriz de elementos, lista derecha:matriz de elementos)
ResultList =nueva matriz
Mientras que la lista izquierda no está vacía y la lista derecha no está vacía.
Si LeftList [0] <=Lista derecha [0] entonces
Agregar LeftList [0] a ResultList
Retire la lista izquierda [0] de la lista izquierda
demás
Agregar la lista correcta [0] a ResultList
Eliminar la lista derecha [0] de la lista derecha
final si
terminar mientras
// Agregar cualquier elemento restante de la lista izquierda o la lista derecha
Agregue todos los elementos restantes de LeftList a ResultList
Agregue todos los elementos restantes de la lista correcta a la lista de resultados
Return ResultList
procedimiento final
`` `` ``
* Eficiencia:
* Mejor caso: O (n log n)
* Caso promedio: O (n log n)
* peor de los casos: O (n log n)
* Complejidad espacial: O (n) (requiere espacio adicional para fusionar)
* Implementación: Más complejo que los algoritmos anteriores, pero proporciona un buen rendimiento para grandes conjuntos de datos.
* Casos de uso: Adecuado para clasificar grandes listas donde el rendimiento consistente es importante.
5. Clasificación rápida
* Concepto: También un algoritmo de división y conquista. Elige un elemento como un pivote y divide la matriz dada alrededor del pivote recogido.
* pseudocódigo:
`` `` ``
Procedimiento QuickSort (Lista:Mango de elementos, Bajo:Int, High:Int)
Si bajo
P =Partición (Lista, baja, alta)
// Ordenar los elementos por separado antes de la partición y después de la partición
Quicksort (lista, bajo, P-1)
Quicksort (lista, P+1, alto)
final si
procedimiento final
Partición del procedimiento (lista:matriz de elementos, bajo:int, alto:int)
pivot =list [high] // elige el último elemento como el pivote
i =bajo - 1 // índice de elementos más pequeños
para j =bajo a alto-1
// Si el elemento actual es más pequeño o igual a pivote
Si la lista [j] <=pivot entonces
i =i + 1 // índice de incremento de elementos más pequeños
Lista de intercambio [i] y lista [j]
final si
finalizar
Lista de intercambio [i + 1] y lista [alto]
Regreso i + 1
procedimiento final
`` `` ``
* Eficiencia:
* Mejor caso: O (n log n) (cuando el pivote es siempre la mediana)
* Caso promedio: O (n log n)
* peor de los casos: O (n
* Complejidad espacial: O (log n) (debido a llamadas recursivas, puede ser o (n) en el peor de los casos)
* Implementación: Generalmente rápido en la práctica, pero su peor rendimiento puede ser una preocupación. La elección del pivote afecta significativamente su rendimiento.
* Casos de uso: A menudo, el algoritmo de clasificación más rápido en la práctica para conjuntos de datos grandes. Sin embargo, se debe considerar su peor rendimiento. Muchas implementaciones utilizan aleatorización u otras técnicas para evitar el peor caso.
6. Sort de montón
* Concepto: Construye un montón máximo (o un montón min) a partir de los datos de entrada y luego extrae repetidamente el elemento raíz (el elemento más grande o más pequeño) y lo coloca al final de la matriz ordenada.
* pseudocódigo:
`` `` ``
PROCEDIMIENTO PEPSORT (LISTA:MAZO DE ARTÍCULOS)
n =longitud (lista)
// construir un montón máximo
para i =n/2 - 1 hasta 0 do
Heapify (List, N, I)
finalizar
// uno por uno extraer un elemento de la pata
para i =n-1 hasta 0 do
Lista de intercambio [0] y lista [i] // mover la raíz actual para finalizar
// Llamar a Max Heapify en el montón reducido
Heapify (Lista, I, 0)
finalizar
procedimiento final
Procedimiento Heapify (lista:matriz de elementos, n:int, i:int)
más grande =i // inicializar más grande como raíz
izquierda =2*i + 1
Derecha =2*i + 2
// Si el niño izquierdo es más grande que la raíz
Si se deja
más grande =izquierda
final si
// Si el niño correcto es más grande que el más grande hasta ahora
Si es correcto
más grande =correcto
final si
// Si el más grande no es raíz
si más grande! =yo entonces
Lista de intercambio [i] y lista [más grande]
// Aumento recursivamente el sub-árbol afectado
Heapify (lista, n, más grande)
final si
procedimiento final
`` `` ``
* Eficiencia:
* Mejor caso: O (n log n)
* Caso promedio: O (n log n)
* peor de los casos: O (n log n)
* Complejidad espacial: O (1) (ordenar en el lugar)
* Implementación: Más complejos que los algoritmos más simples, pero garantiza el rendimiento O (n log n).
* Casos de uso: Es deseable una buena opción cuando necesite el rendimiento de O (n log n) y la clasificación en el lugar. Utilizado en implementaciones de cola prioritaria.
Tabla resumida de eficiencias
| Algoritmo | Mejor caso | Caso promedio | Peor de los casos | Complejidad espacial |
| ------------------- | ----------- | -------------- | ------------ | ------------------- |
| Clasificación de burbujas | O (n) | O (n
| Clasificación de selección | O (n
| Sorteo de inserción | O (n) | O (n
| Clasificación de fusiones | O (n log n) | O (n log n) | O (n log n) | O (n) |
| Clasificación rápida | O (n log n) | O (n log n) | O (n
| Sort de montón | O (n log n) | O (n log n) | O (n log n) | O (1) |
Diferencias clave en eficiencia e implementación:
* cuadrática vs. logarítmica: Algoritmos con o (n
* Divide y conquista: Fusionar clasificación y clasificación rápida Use la estrategia de división y conquista, que permite una clasificación más eficiente de grandes conjuntos de datos.
* clasificación en el lugar: La clasificación de burbujas, el orden de selección, el orden de inserción y el tipo de almacenamiento de almacenamiento son algoritmos de clasificación en el lugar, lo que significa que no requieren memoria adicional significativa. La clasificación de fusión requiere o (n) espacio adicional para fusionar. El orden rápido requiere O (log n) en promedio, pero o (n) espacio en el peor de los casos debido a las llamadas recursivas.
* Estabilidad: Un algoritmo de clasificación es * estable * si los elementos con valores iguales mantienen su orden relativo después de la clasificación. La clasificación de fusión y el tipo de inserción son estables, mientras que el tipo de montón y la clasificación rápida (en su forma básica) no lo son. La estabilidad puede ser importante en ciertas aplicaciones.
* elección de pivote (clasificación rápida): El rendimiento de la clasificación rápida depende en gran medida de la elección del elemento pivote. Las opciones de pivote deficientes pueden conducir a la peor de los casos o (n
* Complejidad de implementación: El tipo de burbujas y el orden de inserción son los más simples de implementar. Fusion Sort, Rapid Sort y Heap Sort son más complejos.
* Adaptación: La clasificación de inserción es adaptativa, lo que significa que su rendimiento mejora si los datos de entrada ya están parcialmente ordenados.
Elegir el algoritmo correcto:
El mejor algoritmo de clasificación para usar depende de la aplicación específica y las características de los datos. Considere estos factores:
* Tamaño del conjunto de datos: Para conjuntos de datos muy pequeños, la simplicidad de la clasificación o el tipo de inserción de burbujas puede ser suficiente. Para conjuntos de datos más grandes, la clasificación de fusión, la clasificación rápida o el tipo de montón son generalmente mejores opciones.
* Nivel de clasificación: Si los datos ya se clasifican principalmente, la clasificación de inserción podría ser la opción más rápida.
* Restricciones de memoria: Si la memoria es limitada, se prefieren los algoritmos de clasificación en el lugar como la clasificación de burbujas, el tipo de selección, el orden de inserción y el tipo de montón.
* Requisitos de estabilidad: Si se requiere estabilidad, elija un algoritmo de clasificación estable como el tipo de fusión o el tipo de inserción.
* rendimiento en peor de los casos: Si necesita un rendimiento garantizado, evite el orden rápido (a menos que se implemente con la aleatorización de pivote u otras estrategias para mitigar el peor comportamiento de los casos).
* Facilidad de implementación y mantenimiento: Considere la compensación entre el rendimiento y la complejidad de la implementación.
¡Espero que esta explicación detallada ayude! Avísame si tienes más preguntas.
min_index =j