Els algoritmes d'ordenació són fonamentals en la programació i la informàtica. Aquests algoritmes permeten organitzar una col·lecció de dades en un ordre específic, com ara numèric o alfabètic. En aquesta secció, explorarem alguns dels algoritmes d'ordenació més comuns, com el Bubble Sort, el Selection Sort i el Quick Sort.
Objectius d'aprenentatge
Al final d'aquest tema, hauràs de ser capaç de:
- Comprendre el concepte d'ordenació i la seva importància.
- Implementar diversos algoritmes d'ordenació.
- Comparar l'eficiència dels diferents algoritmes d'ordenació.
- Bubble Sort
Descripció
El Bubble Sort és un dels algoritmes d'ordenació més senzills. Funciona comparant parelles d'elements adjacents i intercanviant-los si estan en l'ordre incorrecte. Aquest procés es repeteix fins que la llista està ordenada.
Implementació
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
# Exemple d'ús
arr = [64, 34, 25, 12, 22, 11, 90]
print("Array original:", arr)
sorted_arr = bubble_sort(arr)
print("Array ordenat:", sorted_arr)Explicació del codi
- Inicialització:
nés la longitud de l'array. - Bucle extern: Itera sobre cada element de l'array.
- Bucle intern: Compara cada parell d'elements adjacents i els intercanvia si estan en l'ordre incorrecte.
- Intercanvi: Si
arr[j]és més gran quearr[j+1], es fa l'intercanvi.
Complexitat
- Pitjor cas: O(n^2)
- Millor cas: O(n) (quan l'array ja està ordenat)
- Cas mitjà: O(n^2)
- Selection Sort
Descripció
El Selection Sort funciona seleccionant repetidament el mínim (o màxim) element de la part no ordenada de l'array i intercanviant-lo amb el primer element no ordenat.
Implementació
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
# Exemple d'ús
arr = [64, 25, 12, 22, 11]
print("Array original:", arr)
sorted_arr = selection_sort(arr)
print("Array ordenat:", sorted_arr)Explicació del codi
- Inicialització:
nés la longitud de l'array. - Bucle extern: Itera sobre cada element de l'array.
- Trobar el mínim: Troba l'índex del mínim element en la part no ordenada de l'array.
- Intercanvi: Intercanvia el mínim element trobat amb el primer element no ordenat.
Complexitat
- Pitjor cas: O(n^2)
- Millor cas: O(n^2)
- Cas mitjà: O(n^2)
- Quick Sort
Descripció
El Quick Sort és un algoritme d'ordenació eficient que utilitza el mètode de divideix i venceràs. Tria un element com a pivot i particiona l'array en dues subarrays, un amb elements menors que el pivot i l'altre amb elements majors. Després, ordena les subarrays recursivament.
Implementació
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)
# Exemple d'ús
arr = [3, 6, 8, 10, 1, 2, 1]
print("Array original:", arr)
sorted_arr = quick_sort(arr)
print("Array ordenat:", sorted_arr)Explicació del codi
- Cas base: Si l'array té un o cap element, ja està ordenat.
- Pivot: Tria un element com a pivot (en aquest cas, el del mig).
- Partició: Divideix l'array en tres parts: elements menors que el pivot, elements iguals al pivot i elements majors que el pivot.
- Recursió: Ordena recursivament les subarrays i les combina.
Complexitat
- Pitjor cas: O(n^2) (quan l'array està ja ordenat o en ordre invers)
- Millor cas: O(n log n)
- Cas mitjà: O(n log n)
Comparació dels Algoritmes
| Algoritme | Pitjor cas | Millor cas | Cas mitjà | Espai addicional |
|---|---|---|---|---|
| Bubble Sort | O(n^2) | O(n) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Quick Sort | O(n^2) | O(n log n) | O(n log n) | O(log n) |
Exercicis Pràctics
Exercici 1: Implementa el Bubble Sort
Implementa el Bubble Sort per a una llista de nombres donada i comprova el seu funcionament amb diferents conjunts de dades.
Exercici 2: Implementa el Selection Sort
Implementa el Selection Sort per a una llista de nombres donada i comprova el seu funcionament amb diferents conjunts de dades.
Exercici 3: Implementa el Quick Sort
Implementa el Quick Sort per a una llista de nombres donada i comprova el seu funcionament amb diferents conjunts de dades.
Solucions
Solució Exercici 1
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 arrSolució Exercici 2
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 arrSolució Exercici 3
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)Conclusió
En aquesta secció, hem explorat tres dels algoritmes d'ordenació més comuns: Bubble Sort, Selection Sort i Quick Sort. Hem vist com implementar-los i hem comparat la seva eficiència. Aquests coneixements són fonamentals per a qualsevol programador, ja que l'ordenació és una operació bàsica en moltes aplicacions.
Fonaments de la Programació
Mòdul 1: Introducció a la Programació
- Què és la programació?
- Història de la programació
- Llenguatges de programació
- Entorns de desenvolupament