- Vienkāršs un stabils algoritms, kas kārto, salīdzinot un mainot blakus esošos elementus, ideāli piemērots pamatu apguvei.
- Tās sarežģītība ir O(n^2), tāpēc tā ir neefektīva lielās kopās un veic daudz nevajadzīgu salīdzinājumu.
- Tika parādīta tā ieviešana C, Java un Python valodās; lielākām datu kopām pastāv efektīvākas alternatīvas, piemēram, ātrā kārtošana un apvienošanas kārtošana.
Burbuļu kārtošanas algoritms ir viens no vienkāršākajiem un visvienkāršākajiem algoritmiem, ko izmanto saraksta elementu kārtošanai. Tā vienkāršība padara to par lielisku izvēli, lai izprastu šķirošanas algoritmu pamatjēdzienus. Šo algoritmu parasti izmanto lietojumprogrammās un programmās, kurās ir mazs kārtojamo elementu skaits.
Šajā rakstā mēs pievērsīsimies burbuļu kārtošanas algoritma ieviešanai divās populārās programmēšanas valodās: C un Java. Mēs izpētīsim soļus, kas nepieciešami, lai ieviestu šo algoritmu katrā no šīm valodām, analizējot pirmkodu un sniedzot detalizētus skaidrojumus.
Burbuļu kārtošanas algoritms C un Java
Burbuļu kārtošanas algoritms, kā norāda nosaukums, darbojas, salīdzinot blakus esošo elementu pārus sarakstā un veicot mijmaiņas darījumus, ja tie atrodas nepareizā secībā. Šo procesu atkārto, līdz saraksts ir pilnībā sakārtots.
Kā burbuļu kārtošanas algoritms darbojas C un Java?
Burbuļu kārtošanas algoritms ievēro vienkāršu, bet efektīvu pieeju elementu šķirošanai. Algoritma vispārīgā darbība ir parādīta zemāk:
- Mēs sākam ar nesakārtotu preču sarakstu.
- Mēs atkārtojam sarakstu, salīdzinot katru blakus esošo elementu pāri.
- Ja elementi ir nepareizā secībā, mēs tos apmainām.
- Mēs turpinām atkārtot sarakstu, līdz tas ir pilnībā sakārtots.
- Iterācijas process tiek atkārtots tik reižu, cik nepieciešams, līdz pilnā pārejā vairs netiek veikti mijmaiņas darījumi.
Burbuļu kārtošanas algoritma ieviešana programmā C
Zemāk mēs piedāvājam burbuļu kārtošanas algoritma ieviešanu C valodā :
#include <stdio.h>
void bubbleSort(int array[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int main() {
int array[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(array) / sizeof(array[0]);
bubbleSort(array, size);
printf("Array ordenado: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
return 0;
}
Šajā burbuļa algoritma kodā mēs esam definējuši funkciju, ko sauc bubbleSort kas par parametriem ņem masīvu un tā lielumu. Funkcija veic burbuļu kārtošanas algoritmu, izmantojot divas cilpas for. Pirmā cilpa for atkārtojas pār masīva elementiem un otro cilpu for veikt nepieciešamos salīdzinājumus un apmaiņu.
Visbeidzot, funkcijā main, esam izveidojuši piemēru masīvu un aprēķinājuši tā lielumu. Tad mēs izsaucam funkciju bubbleSort nododot masīvu un tā lielumu kā argumentus. Visbeidzot, mēs izdrukājam sakārtoto masīvu uz ekrāna.
Burbuļu kārtošanas algoritma ieviešana Java
Tālāk mēs iepazīstinām ar burbuļu kārtošanas algoritma ieviešanu Java valodā:
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] array) {
int size = array.length;
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(array);
System.out.println("Array ordenado: " + Arrays.toString(array));
}
}
Šajā kodā mēs esam definējuši klasi ar nosaukumu BubbleSort. Šajā klasē mēs esam deklarējuši statisku metodi, ko sauc bubbleSort kas par parametru ņem masīvu. Metode bubbleSort veic burbuļu kārtošanas algoritmu, izmantojot divas cilpas for, tāpat kā C ieviešanā.
Metodē main, esam izveidojuši piemēru masīvu un izsaucām metodi bubbleSort masīva nodošana kā arguments. Visbeidzot, mēs izmantojam Arrays.toString(array) lai izdrukātu sakārtoto masīvu konsolē.
Burbuļu kārtošanas algoritma ieviešana programmā Python
Python burbuļu kārtošanas algoritma ekvivalents:
def bubble_sort(array):
size = len(array)
for i in range(size - 1):
for j in range(size - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print("Array ordenado:", array)
Burbuļu kārtošanas algoritma priekšrocības
Burbuļu kārtošanas algoritmam ir dažas priekšrocības, piemēram:
- Vienkāršība: burbuļu kārtošanas algoritmu ir viegli saprast un ieviest. Tas neprasa sarežģītas zināšanas un ir piemērots programmēšanas iesācējiem.
- Zema koda sarežģītība: kods, kas nepieciešams, lai ieviestu burbuļu kārtošanas algoritmu, ir salīdzinoši īss un kodolīgs. Tas padara to par ātru iespēju neliela vienumu skaita šķirošanai.
Burbuļu kārtošanas algoritma trūkumi
Neskatoties uz vienkāršību, burbuļu kārtošanas algoritmam ir arī daži trūkumi:
- Neefektivitāte lielās datu kopās: Burbuļu kārtošanas algoritms nav efektīvs izpildes laika ziņā, strādājot ar lielām datu kopām. Tās laika sarežģītība ir O(n^2), kas nozīmē, ka izpildes laiks strauji palielinās, palielinoties datu kopas lielumam.
- Salīdzinājumu skaits: burbuļu kārtošanas algoritms veic lielu skaitu salīdzinājumu pat tad, ja masīvs jau ir sakārtots. Tas var izraisīt nevajadzīgu veiktspējas un resursu zudumu.
Alternatīvas burbuļu kārtošanas algoritmam
Tā kā datu kopas kļūst lielākas un sarežģītākas, ir svarīgi apsvērt efektīvākas alternatīvas burbuļu kārtošanas algoritmam. Dažas no populārākajām alternatīvām ir:
- Ievietošanas kārtošanas algoritms: Šis algoritms sadala sarakstu sakārtotā daļā un nesakārtotajā daļā un ievieto katru nesakārtotās daļas elementu pareizajā vietā sakārtotajā daļā. Sliktākajā gadījumā tā laika sarežģītība ir O(n^2), taču vairumā gadījumu tas ir efektīvāks par burbuļu kārtošanas algoritmu.
- Atlases kārtošanas algoritms: Šis algoritms sadala sarakstu pasūtītajā un nesakārtotajā daļā un atkārtoti atlasa mazāko elementu no nesakārtotās daļas un ievieto to pasūtītās daļas beigās. Sliktākajā gadījumā tā laika sarežģītība ir O(n^2), taču vairumā gadījumu tas ir arī efektīvāks par burbuļu kārtošanas algoritmu.
Bubble Algorithm FAQ
1. Kāda ir burbuļu kārtošanas algoritma laika sarežģītība?
Burbuļu kārtošanas algoritma laika sarežģītība ir O(n^2), kur “n” ir kārtojamo elementu skaits. Tas nozīmē, ka, palielinoties saraksta lielumam, algoritma darbības laiks palielinās kvadrātiski.
2. Kad ir lietderīgi izmantot burbuļu kārtošanas algoritmu?
Burbuļu kārtošanas algoritms ir piemērots, ja kārtojamo elementu saraksts ir mazs. Laika sarežģītības dēļ to nav ieteicams izmantot lielām datu kopām, jo ir pieejami efektīvāki algoritmi.
3. Vai burbuļu kārtošanas algoritms ir stabils?
Jā, burbuļu kārtošanas algoritms ir stabils kārtošanas algoritms. Tas nozīmē, ka kārtošanas procesā tā saglabā elementu relatīvo secību ar vienādiem taustiņiem.
4. Kāda ir labākā alternatīva burbuļu kārtošanas algoritmam?
Labākās alternatīvas burbuļu kārtošanas algoritmam izvēle ir atkarīga no konteksta un problēmas īpašajām prasībām. Tomēr daži efektīvāki algoritmi, piemēram, ātrā kārtošana un apvienošanas kārtošana , tiek plaši izmantoti to zemākās laika sarežģītības dēļ.
5. Vai burbuļu kārtošanas algoritmu var uzlabot?
Jā, ir burbuļu kārtošanas algoritma varianti un optimizācijas, piemēram, “divvirzienu burbuļu kārtošana” un “uzlabota burbuļu kārtošana”. Šīs optimizācijas samazina salīdzinājumu skaitu un atkārtojumu skaitu, kas nepieciešams saraksta kārtošanai.
6. Kur es varu atrast vairāk informācijas par šķirošanas algoritmiem?
Plašāku informāciju par šķirošanas algoritmiem varat atrast uzticamos avotos, piemēram, Wikipedia. Šeit ir dažas noderīgas saites:
Secinājums
Šajā rakstā mēs esam izpētījuši burbuļu kārtošanas algoritmu C un Java programmēšanas valodās. Mēs esam iemācījušies, kā šis algoritms darbojas soli pa solim, un esam redzējuši tā praktisko ieviešanu abās valodās. Mēs esam arī apsprieduši burbuļu kārtošanas algoritma priekšrocības un trūkumus, kā arī izpētījuši efektīvākas alternatīvas.
Lai gan burbuļu kārtošanas algoritms ir vienkāršs un viegli īstenojams, ir svarīgi ņemt vērā tā efektivitāti lielākām datu kopām. Šādos gadījumos ir ieteicams apsvērt efektīvākus kārtošanas algoritmus, piemēram, ievietošanas kārtošanu vai atlases kārtošanu.
Mēs ceram, ka šis raksts ir devis jums skaidru izpratni par burbuļu kārtošanas algoritmu.