Bubble Sort és un algorisme d'ordenació senzill que passa repetidament per la llista, compara elements adjacents i els intercanvia si estan en l'ordre incorrecte. S'anomena 'Bubble Sort' perquè els elements més petits 'bubble' a la part superior de la llista. Tot i que no és l'algorisme d'ordenació més eficient, és fàcil d'entendre i implementar, el que el converteix en un bon punt de partida per aprendre sobre els algorismes d'ordenació. En aquest article, aprofundirem en el concepte de Bubble Sort, proporcionarem una implementació de Python amb sortida i parlarem de la complexitat temporal de l'algorisme.
Comprensió de l'ordenació de bombolles
La idea bàsica darrere de Bubble Sort és recórrer la llista diverses vegades, comparar elements adjacents i intercanviar-los si estan fora d'ordre. El procés continua fins que no calen més intercanvis, cosa que indica que ara la llista està ordenada. L'algorisme rep el seu nom de la manera com els elements més petits es mouen gradualment cap a la part superior de la llista, com les bombolles que pugen a la superfície.
Desglossem els passos de l'algorisme d'ordenació de bombolles:
- Itera per la llista: comença des del principi de la llista i compara cada parell d'elements adjacents.
- Compara i intercanvia: si els elements estan en l'ordre incorrecte, intercanvia'ls. D'aquesta manera s'assegura que l'element més gran 'bombolles' i el més petit es mogui cap avall.
- Continuar iterant: repetiu el procés per a cada parell d'elements adjacents fins que s'arribi al final de la llista.
- Repetiu fins que estigui ordenat: continueu iterant per la llista fins que no calgui més intercanvis. En aquest punt, la llista està ordenada.
Tot i que Bubble Sort és senzill d'entendre, no és l'algorisme d'ordenació més eficient, especialment per a grans conjunts de dades. La seva complexitat temporal és O(n^2) en el pitjor dels casos, on 'n' és el nombre d'elements de la llista. Aquesta complexitat de temps quadràtica fa que sigui menys adequat per a grans conjunts de dades en comparació amb algorismes d'ordenació més avançats.
Implementació de Bubble Sort en Python
Ara, implementem Bubble Sort a Python i observem el seu comportament amb una llista de mostra:
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
En aquesta implementació, la funció bubble_sort pren una llista (arr) com a paràmetre i l'ordena al seu lloc. El bucle imbricat compara elements adjacents i els intercanvia si estan en l'ordre incorrecte. El bucle exterior assegura que el procés es repeteix fins que s'ordena tota la llista.
Sortida i explicació
Executem el codi Python proporcionat amb la llista de mostra i observem la sortida:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Aquí, la llista original [64, 34, 25, 12, 22, 11, 90] s'ordena correctament mitjançant l'algorisme de classificació de bombolles, donant lloc a la llista ordenada [11, 12, 22, 25, 34, 64, 90].
L'algoritme itera la llista diverses vegades, comparant i intercanviant elements fins que s'ordena tota la llista. En cada passada, l'element més gran sense classificar 'bombolles' fins a la seva posició correcta. Aquest procés continua fins que no calen més intercanvis, cosa que indica que la llista està completament ordenada.
Tot i que Bubble Sort ordena correctament la llista, és important tenir en compte que la seva complexitat temporal fa que sigui menys eficient per a grans conjunts de dades en comparació amb altres algorismes d'ordenació com Merge Sort o Quick Sort.
Complexitat temporal de l'ordenació de bombolles
Entendre la complexitat temporal d'un algorisme és crucial per avaluar-ne l'eficiència, especialment quan es tracta de grans conjunts de dades. La complexitat temporal de Bubble Sort és O(n^2) en el pitjor dels casos, on 'n' és el nombre d'elements de la llista.
Desglossem l'anàlisi de la complexitat del temps:
- El bucle exterior s'executa per a 'n' iteracions, on 'n' és el nombre d'elements de la llista.
- El bucle intern també s'executa per a 'n' iteracions en el pitjor dels casos. Tanmateix, a mesura que avança l'algorisme, el nombre d'iteracions al bucle interior disminueix, ja que l'element no ordenat més gran es col·loca a la seva posició correcta a cada passada.
- En el pitjor dels casos, el nombre de comparacions i intercanvis és proporcional al quadrat del nombre d'elements de la llista, donant lloc a la complexitat temporal O(n^2). Això fa que Bubble Sort sigui ineficient per a grans conjunts de dades, i sovint es prefereixen algorismes d'ordenació més avançats amb millor complexitat de temps en aplicacions del món real.
Conclusió
En aquest article, hem explorat el concepte de Bubble Sort, un algorisme d'ordenació senzill que compara i intercanvia repetidament elements adjacents fins que s'ordena tota la llista. Vam proporcionar una implementació Python de Bubble Sort, la vam executar amb una llista de mostra i vam analitzar la sortida. A més, vam parlar de la complexitat temporal de Bubble Sort, destacant la seva complexitat temporal en el pitjor dels casos O (n ^ 2) i les seves implicacions per a l'eficiència.