Introducció
L'ordenació per mescla, coneguda en anglès com a "Merge Sort", és un algorisme d'ordenació eficient, estable i basat en la tècnica de "Divideix i Venceràs". Aquest algorisme té una complexitat temporal de \(O(n \log n)\) en el pitjor dels casos, el que el fa molt adequat per a l'ordenació de grans conjunts de dades.
Conceptes Clau
- Divideix i Venceràs: L'algorisme divideix la llista en subllistes més petites fins que cada subllista conté un sol element. Després, aquestes subllistes es combinen (es mesclen) de manera ordenada per formar la llista final ordenada.
- Complexitat Temporal: \(O(n \log n)\)
- Complexitat Espacial: \(O(n)\) degut a l'ús de memòria addicional per a les subllistes.
Funcionament de Merge Sort
- Divisió: Divideix la llista en dues subllistes de mida similar.
- Recursió: Aplica Merge Sort recursivament a cada subllista fins que cada subllista conté un sol element.
- Mescla: Combina les subllistes ordenades en una sola llista ordenada.
Exemple de Codi en Python
A continuació es mostra un exemple de codi en Python que implementa l'algorisme Merge Sort:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Troba el punt mig de la llista
L = arr[:mid] # Divideix la llista en dues meitats
R = arr[mid:]
merge_sort(L) # Ordena la primera meitat
merge_sort(R) # Ordena la segona meitat
i = j = k = 0
# Mescla les dues meitats
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Comprova si queda algun element
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# Exemple d'ús
arr = [12, 11, 13, 5, 6, 7]
print("Llista original:", arr)
merge_sort(arr)
print("Llista ordenada:", arr)Explicació del Codi
-
Divisió:
mid = len(arr) // 2: Troba el punt mig de la llista.L = arr[:mid]iR = arr[mid:]: Divideix la llista en dues subllistes.
-
Recursió:
merge_sort(L)imerge_sort(R): Aplica recursivament Merge Sort a cada subllista.
-
Mescla:
- Utilitza tres índexs
i,jikper seguir la posició en les subllistesL,Ri la llista originalarr, respectivament. - Compara els elements de
LiRi els col·loca en ordre aarr. - Afegeix els elements restants de
LiRaarr.
- Utilitza tres índexs
Exercicis Pràctics
Exercici 1: Implementació Bàsica
Implementa l'algorisme Merge Sort en el teu llenguatge de programació preferit i prova'l amb diferents conjunts de dades.
Exercici 2: Anàlisi de Complexitat
Analitza la complexitat temporal i espacial de la teva implementació de Merge Sort. Compara els resultats amb altres algorismes d'ordenació com Bubble Sort i Quick Sort.
Exercici 3: Variants de Merge Sort
Explora variants de Merge Sort, com l'ordenació per mescla natural (Natural Merge Sort) i l'ordenació per mescla de múltiples vies (Multi-way Merge Sort).
Errors Comuns i Consells
- No dividir correctament la llista: Assegura't de dividir la llista en dues parts iguals o gairebé iguals.
- No mesclar correctament les subllistes: Comprova que tots els elements de les subllistes es mesclin correctament a la llista original.
- Ús ineficient de memòria: Tingues en compte la complexitat espacial de l'algorisme i optimitza l'ús de memòria si és possible.
Conclusió
L'ordenació per mescla és un algorisme d'ordenació eficient i estable que utilitza la tècnica de "Divideix i Venceràs". Amb una complexitat temporal de \(O(n \log n)\), és una opció excel·lent per a l'ordenació de grans conjunts de dades. Practicar la seva implementació i comprendre els seus principis fonamentals és essencial per a qualsevol professional de la informàtica.
Curs d'Anàlisi i Disseny d'Algorismes
Mòdul 1: Introducció als Algorismes
Mòdul 2: Anàlisi d'Algorismes
- Anàlisi de Complexitat Temporal
- Anàlisi de Complexitat Espacial
- Cases de Complexitat: Millor, Pitjor i Promig
Mòdul 3: Estratègies de Disseny d'Algorismes
Mòdul 4: Algorismes Clàssics
- Cerca Binària
- Ordenació per Inserció
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorisme de Dijkstra
- Algorisme de Floyd-Warshall