Introducció
L'ordenació per inserció és un algorisme senzill i intuïtiu que ordena una llista construint gradualment una llista ordenada, element per element. És especialment eficient per a llistes petites o gairebé ordenades.
Funcionament de l'Algorisme
L'algorisme d'ordenació per inserció funciona de la següent manera:
- Comença amb el segon element de la llista (assumint que el primer element ja està ordenat).
- Compara aquest element amb els elements anteriors i l'insereix en la posició correcta.
- Repeteix aquest procés per a cada element de la llista fins que tots els elements estiguin ordenats.
Pseudocodi
Per a i = 1 fins a n-1
clau = A[i]
j = i - 1
Mentre j >= 0 i A[j] > clau
A[j + 1] = A[j]
j = j - 1
A[j + 1] = clauExemple Pas a Pas
Considerem la llista: [5, 2, 4, 6, 1, 3]
- Inicialment:
[5, 2, 4, 6, 1, 3] - Primer pas (i=1): Clau = 2
- Compara 2 amb 5, mou 5 a la dreta.
- Insereix 2 a la primera posició.
- Llista:
[2, 5, 4, 6, 1, 3]
- Segon pas (i=2): Clau = 4
- Compara 4 amb 5, mou 5 a la dreta.
- Insereix 4 a la segona posició.
- Llista:
[2, 4, 5, 6, 1, 3]
- Tercer pas (i=3): Clau = 6
- 6 ja està en la posició correcta.
- Llista:
[2, 4, 5, 6, 1, 3]
- Quart pas (i=4): Clau = 1
- Compara 1 amb 6, mou 6 a la dreta.
- Compara 1 amb 5, mou 5 a la dreta.
- Compara 1 amb 4, mou 4 a la dreta.
- Compara 1 amb 2, mou 2 a la dreta.
- Insereix 1 a la primera posició.
- Llista:
[1, 2, 4, 5, 6, 3]
- Cinquè pas (i=5): Clau = 3
- Compara 3 amb 6, mou 6 a la dreta.
- Compara 3 amb 5, mou 5 a la dreta.
- Compara 3 amb 4, mou 4 a la dreta.
- Insereix 3 a la tercera posició.
- Llista:
[1, 2, 3, 4, 5, 6]
Implementació en Python
def ordenacio_per_insercio(llista):
for i in range(1, len(llista)):
clau = llista[i]
j = i - 1
while j >= 0 and llista[j] > clau:
llista[j + 1] = llista[j]
j -= 1
llista[j + 1] = clau
return llista
# Exemple d'ús
llista = [5, 2, 4, 6, 1, 3]
llista_ordenada = ordenacio_per_insercio(llista)
print(llista_ordenada)Anàlisi de Complexitat
-
Complexitat Temporal:
- Pitjor cas: O(n^2) (quan la llista està ordenada en ordre invers).
- Millor cas: O(n) (quan la llista ja està ordenada).
- Cas promig: O(n^2).
-
Complexitat Espacial:
- O(1) (només utilitza espai addicional per a variables temporals).
Exercici Pràctic
Exercici 1
Implementa l'algorisme d'ordenació per inserció en un altre llenguatge de programació de la teva elecció i prova'l amb diferents llistes d'entrada.
Exercici 2
Analitza la complexitat temporal de l'algorisme d'ordenació per inserció per a una llista de 10 elements ordenada en ordre invers. Explica cada pas i calcula el nombre total de comparacions i moviments.
Solucions
Solució a l'Exercici 1
public class OrdenacioPerInsercio {
public static void ordenacioPerInsercio(int[] llista) {
for (int i = 1; i < llista.length; i++) {
int clau = llista[i];
int j = i - 1;
while (j >= 0 && llista[j] > clau) {
llista[j + 1] = llista[j];
j--;
}
llista[j + 1] = clau;
}
}
public static void main(String[] args) {
int[] llista = {5, 2, 4, 6, 1, 3};
ordenacioPerInsercio(llista);
for (int num : llista) {
System.out.print(num + " ");
}
}
}Solució a l'Exercici 2
Per a una llista de 10 elements ordenada en ordre invers [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]:
- Primer pas: 9 comparacions, 9 moviments.
- Segon pas: 8 comparacions, 8 moviments.
- Tercer pas: 7 comparacions, 7 moviments.
- ...
- Novè pas: 1 comparació, 1 moviment.
Total de comparacions: 9 + 8 + 7 + ... + 1 = 45. Total de moviments: 9 + 8 + 7 + ... + 1 = 45.
Conclusió
L'ordenació per inserció és un algorisme simple i eficient per a llistes petites o gairebé ordenades. Tot i que no és adequat per a llistes grans no ordenades, és una eina útil en moltes situacions pràctiques.
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