Ievads burbuļu šķirošanas algoritmā

Kārtošana ir viena no vienkāršākajām darbībām, kuru varat izmantot datiem. Jūs varat kārtot elementus dažādās programmēšanas valodās, izmantojot dažādus šķirošanas algoritmus, piemēram, Quick Sort, Bubble Sort, Merge Sort, Insertion Sort utt. Bubble Sort ir visvienkāršākais algoritms starp visiem šiem.

Šajā rakstā jūs uzzināsiet par Bubble Sort algoritma - Bubble Sort pseidokoda - darbību algoritms, tā laika un telpas sarežģītība un ieviešana dažādās programmēšanas valodās, piemēram, C ++, Python, C un JavaScript.

Kā darbojas burbuļu šķirošanas algoritms?

Bubble Sort ir vienkāršākais šķirošanas algoritms, kas atkārtoti iziet cauri sarakstam, salīdzina blakus esošos elementus un apmaina tos, ja tie atrodas nepareizā secībā. Šo jēdzienu var efektīvāk izskaidrot ar piemēra palīdzību. Apsveriet nešķirotu masīvu ar šādiem elementiem: {16, 12, 15, 13, 19}.

Piemērs:

Šeit tiek salīdzināti blakus esošie elementi, un, ja tie nav augošā secībā, tie tiek nomainīti.

Burbuļu šķirošanas algoritma pseidokods

Pseidokodā, Bubble Sort algoritmu var izteikt šādi:

bubbleSort (Arr [], izmērs)
// cilpa, lai piekļūtu katram masīva elementam
i = 0 līdz 1. izmēram:
// cilpa, lai salīdzinātu masīva elementus
j = 0 līdz izmēram i-1 darīt:
// salīdziniet blakus esošos elementus
ja Arr [j]> Arr [j + 1], tad
// apmaini tos
mijmaiņa (Arr [j], Arr [j + 1])
beigties, ja
beigas uz
beigas uz
beigas

Iepriekš minētais algoritms apstrādā visus salīdzinājumus, pat ja masīvs jau ir sakārtots. To var optimizēt tālāk, apturot algoritmu, ja iekšējā cilpa neizraisīja nekādu mijmaiņu. Tas samazinās algoritma izpildes laiku.

Tādējādi optimizētā Bubble Sort algoritma pseidokodu var izteikt šādi:

bubbleSort (Arr [], izmērs)
// cilpa, lai piekļūtu katram masīva elementam
i = 0 līdz 1. izmēram:
// pārbaudiet, vai notiek maiņa
nomainīts = nepatiesa
// cilpa, lai salīdzinātu masīva elementus
j = 0 līdz izmēram i-1 darīt:
// salīdziniet blakus esošos elementus
ja Arr [j]> Arr [j + 1], tad
// apmaini tos
mijmaiņa (Arr [j], Arr [j + 1])
nomainīts = taisnība
beigties, ja
beigas uz
// ja neviens elements nav apmainīts, tas nozīmē, ka masīvs tagad ir sakārtots, tad pārtrauciet cilpu.
ja (nav samainīts) tad
pārtraukums
beigties, ja
beigas uz
beigas

Burbuļu šķirošanas algoritma laika sarežģītība un papildu telpa

Bubble Sort algoritma vissliktākā laika sarežģītība ir O (n ^ 2). Tas notiek, kad masīvs ir dilstošā secībā un vēlaties to kārtot augošā secībā vai otrādi.

Bubble Sort algoritma vislabākā laika sarežģītība ir O (n). Tas notiek, kad masīvs jau ir sakārtots.

Saistīts: Kas ir Big-O apzīmējums?

Bubble Sort algoritma vidējā gadījuma laika sarežģītība ir O (n ^ 2). Tas notiek, ja masīva elementi ir sajaukti secībā.

Bubble Sort algoritmam nepieciešamā papildu telpa ir O (1).

C ++ Bubble Sort algoritma ieviešana

Zemāk ir Bubble Sort algoritma C ++ ieviešana:

// C ++ programmas ieviešana
// optimizēts Bubble Sort algoritms
# iekļaut 
izmantojot nosaukumvietu std;
// Funkcija, lai veiktu burbuļu kārtošanu
void bubbleSort (int arr [], int izmērs) {
// Cilne, lai piekļūtu katram masīva elementam
par (int i = 0; i // Mainīgs, lai pārbaudītu, vai notiek maiņa
bool nomainīts = false;
// cilpa, lai salīdzinātu divus blakus esošus masīva elementus
par (int j = 0; j // Salīdzinot divus blakus esošus masīva elementus
ja (arr [j]> arr [j + 1]) {
// Apmainiet abus elementus, ja tie ir
// nav pareizā secībā
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
nomainīts = patiess;
}
}
// Ja neviens elements netika mainīts, tas nozīmē, ka masīvs ir sakārtots tagad,
// tad pārrauj cilpu.
ja (nomainīts == nepatiesa) {
pārtraukums;
}
}
}
// Izdrukā masīva elementus
void printArray (int arr [], int izmērs) {
par (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Masīva garuma atrašana
int izmērs = sizeof (arr) / sizeof (arr [0]);
// Iedrukā norādīto nešķiroto masīvu
cout << "Nesakārtots masīvs:" << endl;
printArray (arr, izmērs);
// Funkcijas bubbleSort () izsaukšana
bubbleSort (arr, izmērs);
// Kārtotā masīva izdrukāšana
cout << "Kārtots masīvs augošā secībā:" << endl;
printArray (arr, izmērs);
atgriešanās 0;
}

Izeja:

Nesakārtots masīvs: 
16 12 15 13 19 
Kārtots masīvs augošā secībā:
12 13 15 16 19

Bubble Sort algoritma Python ieviešana

Zemāk ir Bubble Sort algoritma Python ieviešana:

# Python ieviešana
# optimizēts Bubble Sort algoritms
# Funkcija, lai veiktu burbuļu kārtošanu
def bubbleSort (arr, izmērs):
# Loop, lai piekļūtu katram saraksta elementam
i diapazonā (1. izmērs):
# Mainīgs, lai pārbaudītu, vai notiek maiņa
nomainīts = Nepatiesa
# cilpa, lai salīdzinātu divus blakus esošos saraksta elementus
j diapazonā (izmērs-i-1):
# Salīdzinot divus blakus esošos saraksta elementus
ja arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
nomainīts = True
# Ja neviens elements netika mainīts, tas nozīmē, ka saraksts ir sakārtots tagad,
# tad pārrauj cilpu.
ja nomainīts == Nepatiesa:
pārtraukums
# Izdrukā saraksta elementus
def print Array (arr):
elementam arr:
drukāt (elements, beigas = "")
drukāt ("")
arr = [16, 12, 15, 13, 19]
# Saraksta garuma atrašana
izmērs = len (arr)
# Iedrukā norādīto nešķiroto sarakstu
drukāt ("Nešķirots saraksts:")
printArray (arr)
# Funkcija bubbleSort () izsaukšana
bubbleSort (arr, izmērs)
# Kārtotā saraksta drukāšana
drukāt ("Kārtots saraksts augošā secībā:")
printArray (arr)

Izeja:

Nesakārtots saraksts:
16 12 15 13 19 
Kārtots saraksts augošā secībā:
12 13 15 16 19

Saistīts: Kā izmantot cilpām Python

C Burbuļu šķirošanas algoritma ieviešana

Zemāk ir Bubble Sort algoritma C ieviešana:

// C ieviešana
// optimizēts Bubble Sort algoritms
# iekļaut 
# iekļaut 
// Funkcija, lai veiktu burbuļu kārtošanu
void bubbleSort (int arr [], int izmērs) {
// Cilne, lai piekļūtu katram masīva elementam
par (int i = 0; i // Mainīgs, lai pārbaudītu, vai notiek maiņa
bool nomainīts = false;
// cilpa, lai salīdzinātu divus blakus esošus masīva elementus
par (int j = 0; j // Salīdzinot divus blakus esošus masīva elementus
ja (arr [j]> arr [j + 1]) {
// Apmainiet abus elementus, ja tie ir
// nav pareizā secībā
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
nomainīts = patiess;
}
}
// Ja neviens elements netika mainīts, tas nozīmē, ka masīvs ir sakārtots tagad,
// tad pārrauj cilpu.
ja (nomainīts == nepatiesa) {
pārtraukums;
}
}
}
// Izdrukā masīva elementus
void printArray (int arr [], int izmērs) {
par (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Masīva garuma atrašana
int izmērs = sizeof (arr) / sizeof (arr [0]);
// Iedrukā norādīto nešķiroto masīvu
printf ("Nesakārtots masīvs: \ ⁠n");
printArray (arr, izmērs);
// Funkcijas bubbleSort () izsaukšana
bubbleSort (arr, izmērs);
// Kārtotā masīva izdrukāšana
printf ("Kārtots masīvs augošā secībā: \ ⁠n");
printArray (arr, izmērs);
atgriešanās 0;
}

Izeja:

Nesakārtots masīvs: 
16 12 15 13 19 
Kārtots masīvs augošā secībā: 
12 13 15 16 19

Bubble Sort algoritma ieviešana JavaScript

Zemāk ir Bubble Sort algoritma JavaScript ieviešana:

// JavaScript ieviešana
// optimizēts Bubble Sort algoritms
// Funkcija, lai veiktu burbuļu kārtošanu
funkcija bubbleSort (arr, size) {
// Cilne, lai piekļūtu katram masīva elementam
par (lai i = 0; i// Mainīgs, lai pārbaudītu, vai notiek maiņa
var mainīts = nepatiesa;
// cilpa, lai salīdzinātu divus blakus esošus masīva elementus
par (lai j = 0; j// Salīdzinot divus blakus esošus masīva elementus
ja (arr [j]> arr [j + 1]) {
// Apmainiet abus elementus, ja tie ir
// nav pareizā secībā
ļaujiet temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
nomainīts = patiess;
}
// Ja neviens elements netika mainīts, tas nozīmē, ka masīvs ir sakārtots tagad,
// tad pārrauj cilpu.
ja (nomainīts == nepatiesa) {
pārtraukums;
}
}
}
}
// Izdrukā masīva elementus
funkcija printArray (arr, izmērs) {
par (lai i = 0; idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Masīva garuma atrašana
var size = arr.length;
// Iedrukā norādīto nešķiroto masīvu
document.write ("Nesakārtots masīvs: 
");
printArray (arr, izmērs);
// Funkcijas bubbleSort () izsaukšana
bubbleSort (arr, izmērs);
// Kārtotā masīva izdrukāšana
document.write ("Kārtots masīvs augošā secībā: 
");
printArray (arr, izmērs);

Izeja:

Nesakārtots masīvs:
16 12 15 13 19
Kārtots masīvs augošā secībā:
12 15 13 16 19

Tagad jūs saprotat burbuļu šķirošanas algoritma darbību

Bubble Sort ir vienkāršākais šķirošanas algoritms, un to galvenokārt izmanto, lai izprastu šķirošanas pamatus. Bubble Sort var ieviest arī rekursīvi, taču tas nedod papildu priekšrocības, lai to izdarītu.

Izmantojot Python, jūs varat viegli ieviest Bubble Sort algoritmu. Ja neesat pazīstams ar Python un vēlaties sākt savu ceļojumu, lieliska izvēle ir sākt ar skriptu "Hello World".

Kā sākt darbu ar Python, izmantojot skriptu "Hello World"

Python ir viena no populārākajām programmēšanas valodām, kas tiek izmantota šodien. Izpildiet šo apmācību, lai sāktu darbu ar savu pirmo Python skriptu.

Lasiet Tālāk

Par autoru