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

Ordenació Ràpida (Quick Sort)

Següent ►
►

Introducció

L'ordenació ràpida, coneguda com a Quick Sort, és un algorisme d'ordenació eficient que utilitza la tècnica de "divideix i venceràs". És àmpliament utilitzat gràcies a la seva eficiència en la pràctica i la seva facilitat d'implementació.

Conceptes Clau

  1. Pivoteig: Seleccionar un element de la llista com a pivot.
  2. Partició: Reorganitzar els elements de manera que tots els elements menors que el pivot es col·loquin abans d'ell i tots els elements majors es col·loquin després.
  3. Recursivitat: Aplicar l'algorisme recursivament a les subllistes de menors i majors.

Algorisme

Pseudocodi

QUICKSORT(A, low, high)
    if low < high
        pivot_index = PARTITION(A, low, high)
        QUICKSORT(A, low, pivot_index - 1)
        QUICKSORT(A, pivot_index + 1, high)

PARTITION(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high - 1
        if A[j] <= pivot
            i = i + 1
            swap A[i] with A[j]
    swap A[i + 1] with A[high]
    return i + 1

Explicació del Pseudocodi

  1. QUICKSORT(A, low, high):

    • Si low és menor que high, es procedeix amb la partició.
    • Es crida la funció PARTITION per obtenir l'índex del pivot.
    • Es crida recursivament QUICKSORT per a les subllistes abans i després del pivot.

  2. PARTITION(A, low, high):

    • Es selecciona el pivot com l'últim element de la llista.
    • Es mouen els elements menors que el pivot a l'esquerra i els majors a la dreta.
    • Es col·loca el pivot en la seva posició correcta i es retorna el seu índex.

Exemple Pràctic

Codi en Python

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 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

# Exemple d'ús
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quicksort(arr, 0, n - 1)
print("Array ordenat:", arr)

Explicació del Codi

  1. Funció quicksort:

    • Comprova si la subllista té més d'un element (low < high).
    • Obté l'índex del pivot mitjançant partition.
    • Aplica recursivament quicksort a les subllistes abans i després del pivot.

  2. Funció partition:

    • Selecciona el pivot com l'últim element de la llista.
    • Mou els elements menors que el pivot a l'esquerra i els majors a la dreta.
    • Col·loca el pivot en la seva posició correcta i retorna el seu índex.

Exercicis Pràctics

Exercici 1

Implementa l'algorisme Quick Sort per a una llista de nombres enters i prova'l amb la següent llista: [3, 6, 8, 10, 1, 2, 1].

Solució

arr = [3, 6, 8, 10, 1, 2, 1]
quicksort(arr, 0, len(arr) - 1)
print("Array ordenat:", arr)

Exercici 2

Modifica l'algorisme Quick Sort per seleccionar el pivot com l'element del mig en lloc de l'últim element.

Solució

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    mid = (low + high) // 2
    arr[mid], arr[high] = arr[high], arr[mid]
    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

# Exemple d'ús
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quicksort(arr, 0, n - 1)
print("Array ordenat:", arr)

Errors Comuns i Consells

  1. No actualitzar correctament els índexs: Assegura't que els índexs i i j s'actualitzin correctament durant la partició.
  2. Selecció del pivot: La selecció del pivot pot afectar significativament el rendiment. Prova diferents estratègies (primer element, últim element, element del mig, etc.).
  3. Recursivitat: Assegura't que les crides recursives cobreixin correctament les subllistes abans i després del pivot.

Conclusió

L'ordenació ràpida és un algorisme potent i eficient per a l'ordenació de llistes. Comprendre el seu funcionament i implementació és fonamental per a qualsevol professional de la programació. Practica amb diferents llistes i estratègies de selecció de pivot per dominar aquest algorisme.

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