El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algoritmes d'Ordenació Avançats

Següent ►
►

En aquest tema, explorarem diversos algoritmes d'ordenació avançats que són fonamentals per a la manipulació eficient de dades. Aquests algoritmes són més sofisticats que els mètodes bàsics com la bombolla o la selecció, i són essencials per a aplicacions que requereixen un rendiment òptim.

Índex

  1. Introducció
  2. Ordenació per Fusió (Merge Sort)
  3. Ordenació Ràpida (Quick Sort)
  4. Ordenació per Radix (Radix Sort)
  5. Ordenació per Cistelles (Bucket Sort)
  6. Exercicis Pràctics
  7. Conclusió

Introducció

Els algoritmes d'ordenació avançats són dissenyats per ser més eficients en termes de temps i espai comparats amb els mètodes bàsics. Aquests algoritmes són crucials per a la gestió de grans volums de dades i per a aplicacions que requereixen una resposta ràpida.

Objectius d'Aprenentatge

  • Comprendre els principis fonamentals dels algoritmes d'ordenació avançats.
  • Implementar aquests algoritmes en codi.
  • Analitzar la complexitat temporal i espacial de cada algoritme.
  • Aplicar els algoritmes a problemes pràctics.

Ordenació per Fusió (Merge Sort)

Descripció

L'ordenació per fusió és un algoritme de tipus "divideix i venceràs" que divideix la llista en subllistes més petites fins que cada subllista conté un sol element, i després les fusiona en una llista ordenada.

Pseudocodi

MergeSort(arr):
    if length(arr) > 1:
        mid = length(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        MergeSort(left_half)
        MergeSort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

Implementació en Python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

Complexitat

  • Pitjor cas: O(n log n)
  • Millor cas: O(n log n)
  • Cas mitjà: O(n log n)
  • Espai: O(n)

Ordenació Ràpida (Quick Sort)

Descripció

L'ordenació ràpida és un altre algoritme de tipus "divideix i venceràs" que selecciona un element com a pivot i particiona la llista en dues subllistes: una amb elements menors que el pivot i una altra amb elements majors.

Pseudocodi

QuickSort(arr, low, high):
    if low < high:
        pi = Partition(arr, low, high)
        QuickSort(arr, low, pi - 1)
        QuickSort(arr, pi + 1, high)

Partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Implementació en Python

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Complexitat

  • Pitjor cas: O(n^2)
  • Millor cas: O(n log n)
  • Cas mitjà: O(n log n)
  • Espai: O(log n)

Ordenació per Radix (Radix Sort)

Descripció

L'ordenació per radix és un algoritme no comparatiu que ordena els nombres processant cada dígit individualment. És especialment útil per a ordenar nombres enters.

Pseudocodi

RadixSort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        CountingSort(arr, exp)
        exp *= 10

CountingSort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

Implementació en Python

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

Complexitat

  • Pitjor cas: O(nk)
  • Millor cas: O(nk)
  • Cas mitjà: O(nk)
  • Espai: O(n + k)

Ordenació per Cistelles (Bucket Sort)

Descripció

L'ordenació per cistelles distribueix els elements en diverses cistelles, les ordena individualment i després les combina. És especialment útil per a dades que es distribueixen uniformement.

Pseudocodi

BucketSort(arr):
    n = len(arr)
    max_val = max(arr)
    size = max_val / n

    buckets = [[] for _ in range(n)]

    for i in range(n):
        j = int(arr[i] / size)
        if j != n:
            buckets[j].append(arr[i])
        else:
            buckets[n - 1].append(arr[i])

    for i in range(n):
        InsertionSort(buckets[i])

    result = []
    for i in range(n):
        result.extend(buckets[i])

    return result

InsertionSort(bucket):
    for i in range(1, len(bucket)):
        up = bucket[i]
        j = i - 1
        while j >= 0 and bucket[j] > up:
            bucket[j + 1] = bucket[j]
            j -= 1
        bucket[j + 1] = up

Implementació en Python

def insertion_sort(bucket):
    for i in range(1, len(bucket)):
        up = bucket[i]
        j = i - 1
        while j >= 0 and bucket[j] > up:
            bucket[j + 1] = bucket[j]
            j -= 1
        bucket[j + 1] = up

def bucket_sort(arr):
    n = len(arr)
    max_val = max(arr)
    size = max_val / n

    buckets = [[] for _ in range(n)]

    for i in range(n):
        j = int(arr[i] / size)
        if j != n:
            buckets[j].append(arr[i])
        else:
            buckets[n - 1].append(arr[i])

    for i in range(n):
        insertion_sort(buckets[i])

    result = []
    for i in range(n):
        result.extend(buckets[i])

    return result

Complexitat

  • Pitjor cas: O(n^2)
  • Millor cas: O(n + k)
  • Cas mitjà: O(n + k)
  • Espai: O(n)

Exercicis Pràctics

Exercici 1: Implementació de Merge Sort

Implementa l'algoritme Merge Sort en el teu llenguatge de programació preferit i prova'l amb una llista de nombres enters.

Exercici 2: Anàlisi de Quick Sort

Implementa l'algoritme Quick Sort i analitza el seu rendiment amb diferents conjunts de dades, incloent llistes ja ordenades, llistes inversament ordenades i llistes amb elements aleatoris.

Exercici 3: Radix Sort amb Nombres Negatius

Modifica l'algoritme Radix Sort per a que pugui ordenar llistes que continguin nombres negatius.

Exercici 4: Bucket Sort per a Nombres Reals

Implementa l'algoritme Bucket Sort per a ordenar una llista de nombres reals entre 0 i 1.

Conclusió

En aquesta secció, hem explorat diversos algoritmes d'ordenació avançats, incloent Merge Sort, Quick Sort, Radix Sort i Bucket Sort. Aquests algoritmes són fonamentals per a la manipulació eficient de dades i tenen aplicacions en una àmplia varietat de camps. Hem vist com implementar-los, analitzar la seva complexitat i aplicar-los a problemes pràctics. Amb aquesta base, estàs preparat per abordar problemes d'ordenació més complexos i optimitzar el rendiment de les teves aplicacions.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats