A Bubble Sort egy egyszerű rendezési algoritmus, amely ismételten végiglép a listán, összehasonlítja a szomszédos elemeket, és felcseréli őket, ha rossz sorrendben vannak. A „Buborékos rendezés” nevet kapta, mivel a kisebb elemek „buborékolnak” a lista elejére. Bár nem a leghatékonyabb rendezési algoritmus, könnyen megérthető és megvalósítható, így jó kiindulópont a rendezési algoritmusok megismeréséhez. Ebben a cikkben elmélyülünk a Bubble Sort koncepciójában, egy Python implementációt biztosítunk kimenettel, és megvitatjuk az algoritmus időbeli összetettségét.

kiválasztási rendezés

A buborékok rendezése

A Bubble Sort alapötlete a lista többszöri átfutása, összehasonlítva a szomszédos elemeket, és felcserélve őket, ha nem működnek. A folyamat addig folytatódik, amíg nincs szükség több swapra, jelezve, hogy a lista most rendezve van. Az algoritmus nevét onnan kapta, ahogyan a kisebb elemek fokozatosan a lista elejére kerülnek, hasonlóan a felszínre emelkedő buborékokhoz.

Bontsuk fel a buborékrendezési algoritmus lépéseit:

1. Iteráció a listán: Kezdje a lista elejétől, és hasonlítsa össze a szomszédos elempárokat.
2. Összehasonlítás és csere: Ha az elemek rossz sorrendben vannak, cserélje ki őket. Ez biztosítja, hogy a nagyobb elem „felfelé buborékoljon”, a kisebb pedig lefelé mozogjon.
3. Az iteráció folytatása: Ismételje meg a folyamatot minden szomszédos elempárnál, amíg el nem éri a lista végét.
4. Ismételje a rendezésig: Folytassa az iterációt a listán, amíg nincs szükség több swapra. Ezen a ponton a lista rendezve van.

Bár a Bubble Sort könnyen érthető, nem a leghatékonyabb rendezési algoritmus, különösen nagy adatkészletek esetén. Időbeli összetettsége a legrosszabb esetben O(n^2), ahol 'n' a lista elemeinek száma. Ez a négyzetes időbonyolultság a fejlettebb rendezési algoritmusokhoz képest kevésbé alkalmas nagy adathalmazokhoz.

A Bubble Sort Python megvalósítása

Most pedig hajtsuk végre a Bubble Sort funkciót a Pythonban, és figyeljük meg a viselkedését egy példalistával:

 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) 

Ebben a megvalósításban a bubble_sort függvény egy listát (arr) vesz paraméterként, és a helyére rendezi. A beágyazott hurok összehasonlítja a szomszédos elemeket, és felcseréli őket, ha rossz sorrendben vannak. A külső ciklus biztosítja, hogy a folyamat mindaddig ismétlődik, amíg a teljes lista rendezve nem lesz.

Kimenet és magyarázat

Futtassuk a megadott Python kódot a mintalistával, és figyeljük meg a kimenetet:

 Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90] 

Itt az eredeti lista [64, 34, 25, 12, 22, 11, 90] sikeresen rendeződik a Buborékos rendezés algoritmussal, ami a rendezett listát [11, 12, 22, 25, 34, 64, 90] eredményezi.

próbáld meg elkapni a javat

Az algoritmus többször végigfut a listán, összehasonlítja és felcseréli az elemeket, amíg a teljes lista rendeződik. Minden menetben a legnagyobb rendezetlen elem „felbuborékol” a megfelelő pozícióba. Ez a folyamat addig folytatódik, amíg nincs szükség több swapra, jelezve, hogy a lista teljesen rendezve van.

Míg a Bubble Sort sikeresen rendezi a listát, fontos megjegyezni, hogy időbeli összetettsége miatt kevésbé hatékony a nagy adathalmazok esetében, mint más rendezési algoritmusok, például az egyesített rendezés vagy a gyorsrendezés.

A buborékos rendezés időbeli összetettsége

Egy algoritmus időbeli összetettségének megértése kulcsfontosságú a hatékonyságának értékeléséhez, különösen nagy adatkészletek kezelésekor. A Bubble Sort időbeli összetettsége a legrosszabb esetben O(n^2), ahol 'n' a lista elemeinek száma.

Bontsuk fel az időbonyolultság elemzését:

• A külső ciklus 'n' iterációra fut, ahol az 'n' a lista elemeinek száma.
• A belső ciklus a legrosszabb esetben 'n' iterációra is fut. Az algoritmus előrehaladtával azonban csökken az iterációk száma a belső ciklusban, mivel a legnagyobb rendezetlen elem minden lépésben a megfelelő helyre kerül.
• A legrosszabb esetben az összehasonlítások és cserék száma arányos a lista elemeinek számának négyzetével, ami az O(n^2) időbonyolultságot eredményezi. Emiatt a Bubble Sort nem hatékony nagy adathalmazok esetén, és a valós alkalmazásokban gyakran előnyben részesítik a fejlettebb, jobb időbonyolítású rendezési algoritmusokat.

Következtetés

Ebben a cikkben a Bubble Sort (buborékos rendezés) koncepcióját vizsgáltuk meg, egy egyszerű rendezési algoritmussal, amely ismételten összehasonlítja és felcseréli a szomszédos elemeket, amíg a teljes lista rendeződik. Megadtuk a Bubble Sort Python megvalósítását, lefuttattuk egy mintalistával, és elemeztük a kimenetet. Ezenkívül megvitattuk a Bubble Sort időbonyolultságát, kiemelve az O(n^2) legrosszabb eset időbeli összetettségét és a hatékonyságra gyakorolt ​​hatásait.