Algoritmos de ordenamiento más eficientes

Vista previa del material en texto

Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
Algoritmos de ordenamiento más eficientes (ejemplo: 
quicksort, mergesort) 
 
Los algoritmos de ordenamiento burbuja, selección e 
inserción son eficientes para estructuras de datos 
pequeñas. Sin embargo, no son eficientes para 
estructuras de datos grandes. Para estructuras de datos 
grandes, existen algoritmos de ordenamiento más 
eficientes, como quicksort y mergesort. 
 
Quicksort 
 
Quicksort es un algoritmo de ordenamiento recursivo 
que funciona dividiendo la estructura de datos en dos 
mitades, ordenando cada mitad por separado y luego 
combinando las dos mitades ordenadas para formar 
una estructura de datos ordenada. 
 
Implementación en Python 
 
Python 
def quicksort(lista): 
 if len(lista) <= 1: 
 return lista 
 pivote = lista[len(lista) // 2] 
 menor = [x for x in lista if x < pivote] 
 mayor = [x for x in lista if x >= pivote] 
 return quicksort(menor) + [pivote] + quicksort(mayor) 
Usa el código con precaución. Más información 
Este algoritmo funciona seleccionando un elemento de 
la estructura de datos, llamado pivote. Luego, el 
algoritmo divide la estructura de datos en dos mitades, 
una que contiene todos los elementos menores que el 
pivote y otra que 
contiene todos los 
elementos mayores o 
iguales que el pivote. El 
algoritmo repite este 
proceso en cada mitad 
hasta que la estructura 
de datos esté ordenada. 
 
Complejidad 
 
La complejidad de 
quicksort es O(n log n), 
donde n es el tamaño 
de la estructura de 
datos. Esto significa que 
el tiempo de ejecución 
del algoritmo es 
proporcional al logaritmo 
del cuadrado del 
tamaño de la estructura 
de datos. 
 
Mergesort 
 
Mergesort es un 
algoritmo de 
ordenamiento recursivo 
que funciona dividiendo 
la estructura de datos 
en dos mitades, 
ordenando cada mitad 
por separado y luego 
combinando las dos 
mitades ordenadas para 
formar una estructura de 
datos ordenada. 
 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
Implementación en Python 
 
Python 
def mergesort(lista): 
 if len(lista) <= 1: 
 return lista 
 mitad = len(lista) // 2 
 izquierda = mergesort(lista[:mitad]) 
 derecha = mergesort(lista[mitad:]) 
 return merge(izquierda, derecha) 
 
def merge(lista_izquierda, lista_derecha): 
 lista_ordenada = [] 
 i = 0 
 j = 0 
 while i < len(lista_izquierda) and j < len(lista_derecha): 
 if lista_izquierda[i] < lista_derecha[j]: 
 lista_ordenada.append(lista_izquierda[i]) 
 i += 1 
 else: 
 lista_ordenada.append(lista_derecha[j]) 
 j += 1 
 lista_ordenada += lista_izquierda[i:] 
 lista_ordenada += lista_derecha[j:] 
 return lista_ordenada 
Usa el código con precaución. Más información 
Este algoritmo funciona dividiendo la estructura de 
datos en dos mitades iguales. Luego, el algoritmo 
ordena cada mitad por separado usando mergesort. 
Finalmente, el algoritmo 
combina las dos 
mitades ordenadas para 
formar una estructura de 
datos ordenada. 
 
Complejidad 
 
La complejidad de 
mergesort es O(n log n), 
donde n es el tamaño 
de la estructura de 
datos. Esto significa que 
el tiempo de ejecución 
del algoritmo es 
proporcional al logaritmo 
del cuadrado del 
tamaño de la estructura 
de datos. 
 
Ventajas y desventajas 
de quicksort y mergesort 
 
Quicksort 
 
Ventajas: 
 
Es un algoritmo eficiente 
para estructuras de 
datos grandes. 
Es un algoritmo 
recursivo, lo que puede 
ser más fácil de 
entender que los 
algoritmos iterativos. 
Desventajas: 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
 
Puede ser ineficiente para estructuras de datos con un 
pivote pobremente elegido. 
Mergesort 
 
Ventajas: 
 
Es un algoritmo eficiente para estructuras de datos 
grandes. 
Es un algoritmo estable, lo que significa que no 
intercambia elementos con el mismo valor. 
Desventajas: 
 
Puede ser más complejo de implementar que quicksort. 
Conclusión 
 
Quicksort y mergesort son dos algoritmos de 
ordenamiento eficientes para estructuras de datos 
grandes. Quicksort es un algoritmo más rápido que 
mergesort, pero puede ser ineficiente para estructuras 
de datos con un pivote pobremente elegido. Mergesort 
es un algoritmo más estable que quicksort, pero puede 
ser más complejo de implementar.