Burbuļu kārtošana ir vienkāršs kārtošanas algoritms, kas vairākas reizes pāriet cauri sarakstam, salīdzina blakus esošos elementus un apmaina tos, ja tie atrodas nepareizā secībā. Tas ir nosaukts par 'Burbuļu kārtošanu', jo mazāki elementi 'burbulē' saraksta augšdaļā. Lai gan tas nav visefektīvākais šķirošanas algoritms, to ir viegli saprast un ieviest, tāpēc tas ir labs sākumpunkts, lai uzzinātu par šķirošanas algoritmiem. Šajā rakstā mēs iedziļināsimies burbuļu kārtošanas jēdzienā, nodrošināsim Python ieviešanu ar izvadi un apspriedīsim algoritma laika sarežģītību.

Izpratne par burbuļu kārtošanu

Bubble Sort pamatideja ir atkārtot sarakstu vairākas reizes, salīdzinot blakus esošos elementus un apmainot tos, ja tie nav kārtībā. Process turpinās, līdz vairs nav nepieciešami mijmaiņas darījumi, norādot, ka saraksts tagad ir sakārtots. Algoritms savu nosaukumu ieguvis no tā, kā mazāki elementi pakāpeniski pārvietojas uz saraksta augšdaļu, līdzīgi kā burbuļi, kas paceļas virspusē.

Sadalīsim burbuļu kārtošanas algoritma darbības:

1. Atkārtojiet sarakstu: sāciet no saraksta sākuma un salīdziniet katru blakus esošo elementu pāri.
2. Salīdzināt un nomainīt: ja elementi ir nepareizā secībā, nomainiet tos. Tas nodrošina, ka lielākais elements “burbuļo uz augšu”, bet mazākais virzās uz leju.
3. Turpināt atkārtošanu: atkārtojiet procesu katram blakus esošo elementu pārim, līdz tiek sasniegts saraksta beigas.
4. Atkārtojiet, līdz esat sakārtots: turpiniet atkārtot sarakstu, līdz vairs nav nepieciešami mijmaiņas darījumi. Šajā brīdī saraksts ir sakārtots.

Lai gan Bubble Sort ir viegli saprotams, tas nav visefektīvākais kārtošanas algoritms, jo īpaši lielām datu kopām. Tās laika sarežģītība sliktākajā gadījumā ir O(n^2), kur 'n' ir elementu skaits sarakstā. Šī kvadrātiskā laika sarežģītība padara to mazāk piemērotu lielām datu kopām, salīdzinot ar progresīvākiem kārtošanas algoritmiem.

Python Bubble Sort ieviešana

Tagad ieviesīsim Bubble Sort programmā Python un novērosim tās darbību, izmantojot parauga sarakstu:

 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) 

Šajā īstenošanā funkcija bubble_sort izmanto sarakstu (arr) kā savu parametru un sakārto to savā vietā. Ligzdotā cilpa salīdzina blakus esošos elementus un apmaina tos, ja tie atrodas nepareizā secībā. Ārējā cilpa nodrošina, ka process tiek atkārtots, līdz viss saraksts ir sakārtots.

Izvade un skaidrojums

Palaidīsim sniegto Python kodu ar paraugu sarakstu un novērojam izvadi:

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

Šeit sākotnējais saraksts [64, 34, 25, 12, 22, 11, 90] tiek veiksmīgi sakārtots, izmantojot burbuļu kārtošanas algoritmu, kā rezultātā tiek iegūts sakārtotais saraksts [11, 12, 22, 25, 34, 64, 90].

Algoritms atkārto sarakstu vairākas reizes, salīdzinot un mainot elementus, līdz viss saraksts ir sakārtots. Katrā piegājienā lielākais nešķirotais elements “izburbuļo” pareizajā vietā. Šis process turpinās, līdz vairs nav nepieciešami mijmaiņas darījumi, norādot, ka saraksts ir pilnībā sakārtots.

Lai gan Bubble Sort veiksmīgi sakārto sarakstu, ir svarīgi ņemt vērā, ka tā laika sarežģītība padara to mazāk efektīvu lielām datu kopām salīdzinājumā ar citiem šķirošanas algoritmiem, piemēram, sapludināšanas kārtošanu vai ātro kārtošanu.

Burbuļu kārtošanas laika sarežģītība

Algoritma laika sarežģītības izpratne ir ļoti svarīga, lai novērtētu tā efektivitāti, īpaši, ja tiek izmantotas lielas datu kopas. Bubble Sort laika sarežģītība sliktākajā gadījumā ir O(n^2), kur “n” ir elementu skaits sarakstā.

Sadalīsim laika sarežģītības analīzi:

• Ārējā cilpa darbojas “n” iterācijās, kur “n” ir elementu skaits sarakstā.
• Sliktākajā gadījumā iekšējā cilpa darbojas arī “n” iterācijām. Tomēr, algoritmam progresējot, iterāciju skaits iekšējā cilpā samazinās, jo lielākais nešķirotais elements katrā piegājienā tiek novietots pareizajā vietā.
• Sliktākajā gadījumā salīdzinājumu un mijmaiņas darījumu skaits ir proporcionāls saraksta elementu skaita kvadrātam, kā rezultātā rodas O(n^2) laika sarežģītība. Tas padara Bubble Sort neefektīvu lielām datu kopām, un reālās pasaules lietojumprogrammās bieži tiek doti priekšroka uzlabotākiem kārtošanas algoritmiem ar labāku laika sarežģītību.

Secinājums

Šajā rakstā mēs izpētījām burbuļu kārtošanas koncepciju — vienkāršu kārtošanas algoritmu, kas atkārtoti salīdzina un maina blakus esošos elementus, līdz tiek sakārtots viss saraksts. Mēs nodrošinājām Python Bubble Sort ieviešanu, palaidām to ar izlases sarakstu un analizējām izvadi. Turklāt mēs apspriedām Bubble Sort laika sarežģītību, uzsverot tās O(n^2) sliktākā gadījuma laika sarežģītību un tās ietekmi uz efektivitāti.