Boblesortering er en af de enkleste sorteringsalgoritmer, der itererer gennem det givne array og sammenligner tilstødende elementer. Hvis elementerne er i den forkerte rækkefølge, ombyttes de for at bringe dem i den rigtige rækkefølge. Denne proces fortsætter, indtil hele arrayet er sorteret.
Algoritme:
Trin 1:Gentag over arrayet flere gange
I hver iteration skal du sammenligne tilstødende elementer (i og i + 1)
Trin 2:Hvis det aktuelle element (i) er større end det næste element (i + 1), skal du bytte dem
Gentag denne proces, indtil hele arrayet er sorteret
Tidskompleksitet:
O(n^2), da den itererer gennem arrayet flere gange og udfører sammenligninger og swaps i hver iteration.
Kodeeksempel i Python:
def bubble_sort(arr):
for i in range(len(arr) - 1):
# Iterér gennem arrayet for at sammenligne tilstødende elementer
for j i område(len(arr) - 1 - i):
# Sammenlign det aktuelle element med det næste element
hvis arr[j]> arr[j + 1]:
# Skift elementerne, hvis de er i den forkerte rækkefølge
arr[j], arr[j + 1] =arr[j + 1], arr[j]
# Returner det sorterede array
retur arr
Eksempel:
Input:
[5, 3, 1, 2, 4]
Produktion:
[1, 2, 3, 4, 5]
Boblesorteringsalgoritmen itererer gennem arrayet og sammenligner tilstødende elementer. Hvis de er i den forkerte rækkefølge, bliver de byttet. Denne proces gentages, indtil hele arrayet er sorteret.
Sådan fungerer algoritmen i dette eksempel:
Gentagelse 1:
- Sammenlign 5 og 3:Byt dem, da 5 er større end 3.
- Sammenlign 3 og 1:Byt dem, da 3 er større end 1.
- Sammenlign 2 og 4:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Array bliver:[3, 1, 2, 4, 5].
Gentagelse 2:
- Sammenlign 3 og 1:Byt dem, da 3 er større end 1.
- Sammenlign 1 og 2:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Sammenlign 2 og 4:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Array bliver:[1, 2, 3, 4, 5].
Gentagelse 3:
- Sammenlign 1 og 2:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Sammenlign 2 og 3:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Sammenlign 3 og 4:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Array bliver:[1, 2, 3, 4, 5].
Gentagelse 4:
- Sammenlign 1 og 2:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Sammenlign 2 og 3:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Sammenlign 3 og 4:Det er ikke nødvendigt at bytte, da de er i den rigtige rækkefølge.
- Array forbliver uændret.
Efter den fjerde iteration sorteres arrayet i stigende rækkefølge:[1, 2, 3, 4, 5].
