El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Algoritmos de Ordenamiento

Siguiente ►
►

Introducción

El ordenamiento es una operación fundamental en la programación y en la manipulación de datos. Consiste en reorganizar los elementos de una lista o arreglo en un orden específico, ya sea ascendente o descendente. Existen múltiples algoritmos de ordenamiento, cada uno con sus propias ventajas y desventajas en términos de eficiencia y complejidad.

En esta sección, exploraremos algunos de los algoritmos de ordenamiento más comunes:

  1. Ordenamiento por Burbuja (Bubble Sort)
  2. Ordenamiento por Selección (Selection Sort)
  3. Ordenamiento por Inserción (Insertion Sort)
  4. Ordenamiento Rápido (Quick Sort)
  5. Ordenamiento por Mezcla (Merge Sort)

  1. Ordenamiento por Burbuja (Bubble Sort)

Descripción

El ordenamiento por burbuja es uno de los algoritmos más simples. Funciona comparando pares de elementos adyacentes y los intercambia si están en el orden incorrecto. Este proceso se repite hasta que la lista está ordenada.

Ejemplo de Código

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# Ejemplo de uso
lista = [64, 34, 25, 12, 22, 11, 90]
print("Lista original:", lista)
print("Lista ordenada:", bubble_sort(lista))

Explicación del Código

  1. Inicialización: n es la longitud de la lista.
  2. Primer bucle: Itera desde 0 hasta n-1.
  3. Segundo bucle: Compara elementos adyacentes y los intercambia si están en el orden incorrecto.
  4. Intercambio: Si arr[j] es mayor que arr[j+1], se intercambian los elementos.

Complejidad

  • Peor caso: O(n²)
  • Mejor caso: O(n) (cuando la lista ya está ordenada)
  • Promedio: O(n²)

  1. Ordenamiento por Selección (Selection Sort)

Descripción

El ordenamiento por selección encuentra el elemento más pequeño (o más grande) de la lista y lo coloca en la primera posición. Luego, encuentra el siguiente más pequeño y lo coloca en la segunda posición, y así sucesivamente.

Ejemplo de Código

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Ejemplo de uso
lista = [64, 25, 12, 22, 11]
print("Lista original:", lista)
print("Lista ordenada:", selection_sort(lista))

Explicación del Código

  1. Inicialización: n es la longitud de la lista.
  2. Primer bucle: Itera desde 0 hasta n-1.
  3. Segundo bucle: Encuentra el índice del elemento más pequeño en la sublista no ordenada.
  4. Intercambio: Coloca el elemento más pequeño en su posición correcta.

Complejidad

  • Peor caso: O(n²)
  • Mejor caso: O(n²)
  • Promedio: O(n²)

  1. Ordenamiento por Inserción (Insertion Sort)

Descripción

El ordenamiento por inserción construye la lista ordenada de uno en uno, tomando cada elemento y colocándolo en su posición correcta dentro de la lista ordenada.

Ejemplo de Código

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Ejemplo de uso
lista = [12, 11, 13, 5, 6]
print("Lista original:", lista)
print("Lista ordenada:", insertion_sort(lista))

Explicación del Código

  1. Inicialización: Itera desde el segundo elemento hasta el final de la lista.
  2. Comparación e Inserción: Compara el elemento actual con los elementos de la lista ordenada y lo inserta en la posición correcta.

Complejidad

  • Peor caso: O(n²)
  • Mejor caso: O(n) (cuando la lista ya está ordenada)
  • Promedio: O(n²)

  1. Ordenamiento Rápido (Quick Sort)

Descripción

El ordenamiento rápido es un algoritmo de divide y vencerás. Selecciona un "pivote" y reordena la lista de modo que todos los elementos menores que el pivote estén antes que él y todos los mayores estén después. Luego, aplica recursivamente el mismo proceso a las sublistas.

Ejemplo de Código

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

# Ejemplo de uso
lista = [3, 6, 8, 10, 1, 2, 1]
print("Lista original:", lista)
print("Lista ordenada:", quick_sort(lista))

Explicación del Código

  1. Condición base: Si la lista tiene uno o cero elementos, ya está ordenada.
  2. Selección del pivote: Elige el elemento central como pivote.
  3. Partición: Divide la lista en tres sublistas: menores, iguales y mayores que el pivote.
  4. Recursión: Aplica el mismo proceso recursivamente a las sublistas.

Complejidad

  • Peor caso: O(n²) (cuando el pivote es el menor o mayor elemento)
  • Mejor caso: O(n log n)
  • Promedio: O(n log n)

  1. Ordenamiento por Mezcla (Merge Sort)

Descripción

El ordenamiento por mezcla es otro algoritmo de divide y vencerás. Divide la lista en dos mitades, las ordena recursivamente y luego las combina en una lista ordenada.

Ejemplo de Código

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Ejemplo de uso
lista = [38, 27, 43, 3, 9, 82, 10]
print("Lista original:", lista)
print("Lista ordenada:", merge_sort(lista))

Explicación del Código

  1. Condición base: Si la lista tiene uno o cero elementos, ya está ordenada.
  2. División: Divide la lista en dos mitades.
  3. Recursión: Ordena recursivamente cada mitad.
  4. Mezcla: Combina las dos mitades ordenadas en una lista ordenada.

Complejidad

  • Peor caso: O(n log n)
  • Mejor caso: O(n log n)
  • Promedio: O(n log n)

Ejercicios Prácticos

Ejercicio 1: Implementar Bubble Sort

Implementa el algoritmo de ordenamiento por burbuja y prueba con la lista [5, 1, 4, 2, 8].

Ejercicio 2: Implementar Selection Sort

Implementa el algoritmo de ordenamiento por selección y prueba con la lista [29, 10, 14, 37, 13].

Ejercicio 3: Implementar Insertion Sort

Implementa el algoritmo de ordenamiento por inserción y prueba con la lista [12, 11, 13, 5, 6].

Ejercicio 4: Implementar Quick Sort

Implementa el algoritmo de ordenamiento rápido y prueba con la lista [3, 6, 8, 10, 1, 2, 1].

Ejercicio 5: Implementar Merge Sort

Implementa el algoritmo de ordenamiento por mezcla y prueba con la lista [38, 27, 43, 3, 9, 82, 10].

Conclusión

En esta sección, hemos explorado varios algoritmos de ordenamiento, cada uno con sus propias características y complejidades. Es importante entender cómo y cuándo utilizar cada algoritmo para optimizar el rendimiento de nuestras aplicaciones. Practicar la implementación de estos algoritmos te ayudará a comprender mejor sus mecanismos y a elegir el más adecuado para cada situación.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados