Bevezetés a Bubble Sort algoritmusba

A rendezés az egyik legalapvetőbb művelet, amelyet az adatokra alkalmazhat. Különféle rendezési algoritmusok segítségével rendezheti az elemeket különböző programozási nyelveken, például Gyors rendezés, Bubble Sort, Merge Sort, Insertion Sort stb. A Bubble Sort a legegyszerűbb algoritmus ezek közül.

Ebben a cikkben megismerheti a Bubble Sort algoritmus működését, a Bubble Sort ál kódját algoritmus, annak idő- és térbonyolultsága, valamint megvalósítása különböző programozási nyelveken, például C ++, Python, C és JavaScript.

Hogyan működik a Bubble Sort algoritmus?

A Bubble Sort a legegyszerűbb rendezési algoritmus, amely többször lépeget a listán, összehasonlítja a szomszédos elemeket és felcseréli őket, ha rossz sorrendben vannak. Ez a koncepció hatékonyabban magyarázható egy példa segítségével. Vegyünk egy rendezetlen tömböt a következő elemekkel: {16, 12, 15, 13, 19}.

Példa:

Itt összehasonlítják a szomszédos elemeket, és ha nem növekvő sorrendben vannak, akkor felcserélik őket.

A Bubble Sort algoritmus álkódja

Álkódban, a Bubble Sort algoritmus a következőképpen fejezhető ki:

bubbleSort (Arr [], méret)
// ciklus az egyes tömb elemek eléréséhez
i = 0 esetén az 1-es méretig:
// ciklus a tömb elemek összehasonlításához
j = 0 esetén az i-1 méret:
// hasonlítsa össze a szomszédos elemeket
ha Arr [j]> Arr [j + 1] akkor
// cserélje fel őket
csere (Arr [j], Arr [j + 1])
vége, ha
vége
vége
vége

A fenti algoritmus az összes összehasonlítást akkor is feldolgozza, ha a tömb már rendezve van. Tovább optimalizálható az algoritmus leállításával, ha a belső hurok nem okozott cserét. Ez csökkenti az algoritmus végrehajtási idejét.

Így az optimalizált Bubble Sort algoritmus álkódja a következőképpen fejezhető ki:

bubbleSort (Arr [], méret)
// ciklus az egyes tömb elemek eléréséhez
i = 0 esetén az 1-es méretig:
// ellenőrizze, hogy felcserélődik-e
cserélve = hamis
// ciklus a tömb elemek összehasonlításához
j = 0 esetén az i-1 méret:
// hasonlítsa össze a szomszédos elemeket
ha Arr [j]> Arr [j + 1] akkor
// cserélje fel őket
csere (Arr [j], Arr [j + 1])
cserélve = igaz
vége, ha
vége
// ha egyetlen elem sem került felcserélésre, az azt jelenti, hogy a tömb most rendezve van, akkor szakítsa meg a ciklust.
ha (nem cserélik) akkor
szünet
vége, ha
vége
vége

A buborék rendezési algoritmus időbeli komplexitása és segédtere

A Bubble Sort algoritmus legrosszabb eset-időbeli összetettsége O (n ^ 2). Akkor fordul elő, amikor a tömb csökkenő sorrendben van, és növekvő sorrendbe kívánja rendezni, vagy fordítva.

A Bubble Sort algoritmus időbeli bonyolultsága a legjobb esetben O (n). Akkor fordul elő, amikor a tömb már rendezve van.

Összefüggő: Mi a Big-O jelölés?

A Bubble Sort algoritmus átlagos eset-összetettsége O (n ^ 2). Akkor fordul elő, amikor a tömb elemei összetévesztett sorrendben vannak.

A Bubble Sort algoritmushoz szükséges kiegészítő hely O (1).

A Bubble Sort algoritmus C ++ megvalósítása

Az alábbiakban látható a Bubble Sort algoritmus C ++ megvalósítása:

// a C ++ megvalósítása
// optimalizált Bubble Sort algoritmus
#include 
névtér használata std;
// Funkció a Bubble Sort végrehajtására
void bubbleSort (int arr [], int méret) {
// Hurok a tömb minden eleméhez való hozzáféréshez
for (int i = 0; i // Változó annak ellenőrzésére, hogy történik-e csere
bool cserélve = hamis;
// ciklus a tömb két szomszédos elemének összehasonlításához
for (int j = 0; j // Két szomszédos tömbelem összehasonlítása
if (arr [j]> arr [j + 1]) {
// Cserélje mindkét elemet, ha vannak
// nem megfelelő sorrendben
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = hőmérséklet;
cserélve = igaz;
}
}
// Ha nem cseréltek elemeket, az azt jelenti, hogy a tömb most rendezve van,
// majd szakítsa meg a hurkot.
ha (felcserélve == hamis) {
szünet;
}
}
}
// Kinyomtatja a tömb elemeit
void printArray (int arr [], int méret) {
for (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// A tömb hosszának megkeresése
int size = sizeof (arr) / sizeof (arr [0]);
// Az adott rendezetlen tömb kinyomtatása
cout << "Válogatás nélküli tömb:" << endl;
printArray (arr, méret);
// A bubbleSort () függvény hívása
bubbleSort (arr, méret);
// A rendezett tömb kinyomtatása
cout << "Rendezett tömb növekvő sorrendben:" << endl;
printArray (arr, méret);
visszatér 0;
}

Kimenet:

Válogatás nélküli tömb: 
16 12 15 13 19 
Rendezett tömb növekvő sorrendben:
12 13 15 16 19

A Bubble Sort algoritmus Python megvalósítása

Az alábbiakban bemutatjuk a Bubble Sort algoritmus Python-megvalósítását:

# A Python implementációja
# optimalizált Bubble Sort algoritmus
# Funkció a Bubble Sort végrehajtására
def bubbleSort (arr, méret):
# Hurok a lista minden elemének eléréséhez
i tartományban (1-es méret):
# Változó annak ellenőrzésére, hogy történik-e csere
cserélve = hamis
# ciklus a lista két szomszédos elemének összehasonlításához
j tartományban (méret-i-1):
# Két szomszédos listaelem összehasonlítása
ha arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = hőmérséklet
cserélve = Igaz
# Ha nem cseréltek elemeket, az azt jelenti, hogy a lista most rendezve van,
# majd szakítsa meg a hurkot.
ha felcserélik == Hamis:
szünet
# Kinyomtatja a lista elemeit
def printArray (arr):
az arr-ban lévő elemhez:
print (elem, vég = "")
nyomtatás("")
arr = [16, 12, 15, 13, 19]
# A lista hosszának megkeresése
méret = len (arr)
# A megadott rendezetlen lista kinyomtatása
nyomtatás ("Rendezetlen lista:")
printArray (arr)
# A bubbleSort () függvény hívása
bubbleSort (arr, méret)
# A rendezett lista nyomtatása
nyomtatás ("Rendezett lista növekvő sorrendben:")
printArray (arr)

Kimenet:

Válogatás nélküli lista:
16 12 15 13 19 
Rendezett lista növekvő sorrendben:
12 13 15 16 19

Összefüggő: Hogyan kell használni a Python hurkokhoz

C A Bubble Sort algoritmus megvalósítása

Az alábbiakban látható a Bubble Sort algoritmus C megvalósítása:

// A C megvalósítása
// optimalizált Bubble Sort algoritmus
#include 
#include 
// Funkció a Bubble Sort végrehajtására
void bubbleSort (int arr [], int méret) {
// Hurok a tömb minden eleméhez való hozzáféréshez
for (int i = 0; i // Változó annak ellenőrzésére, hogy történik-e csere
bool cserélve = hamis;
// ciklus a tömb két szomszédos elemének összehasonlításához
for (int j = 0; j // Két szomszédos tömbelem összehasonlítása
if (arr [j]> arr [j + 1]) {
// Cserélje mindkét elemet, ha vannak
// nem megfelelő sorrendben
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = hőmérséklet;
cserélve = igaz;
}
}
// Ha nem cseréltek elemeket, az azt jelenti, hogy a tömb most rendezve van,
// majd szakítsa meg a hurkot.
ha (felcserélve == hamis) {
szünet;
}
}
}
// Kinyomtatja a tömb elemeit
void printArray (int arr [], int méret) {
for (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// A tömb hosszának megkeresése
int size = sizeof (arr) / sizeof (arr [0]);
// Az adott rendezetlen tömb kinyomtatása
printf ("Nem rendezett tömb: \ ⁠n");
printArray (arr, méret);
// A bubbleSort () függvény hívása
bubbleSort (arr, méret);
// A rendezett tömb kinyomtatása
printf ("Rendezett tömb növekvő sorrendben: \ ⁠n");
printArray (arr, méret);
visszatér 0;
}

Kimenet:

Válogatás nélküli tömb: 
16 12 15 13 19 
Rendezett tömb növekvő sorrendben: 
12 13 15 16 19

A Bubble Sort algoritmus JavaScript megvalósítása

Az alábbiakban a Bubble Sort algoritmus JavaScript-implementációja található:

// a JavaScript JavaScript implementációja
// optimalizált Bubble Sort algoritmus
// Funkció a Bubble Sort végrehajtására
function bubbleSort (arr, size) {
// Hurok a tömb minden eleméhez való hozzáféréshez
for (legyen i = 0; én// Változó annak ellenőrzésére, hogy történik-e csere
var cserélve = hamis;
// ciklus a tömb két szomszédos elemének összehasonlításához
for (legyen j = 0; j// Két szomszédos tömbelem összehasonlítása
if (arr [j]> arr [j + 1]) {
// Cserélje mindkét elemet, ha vannak
// nem megfelelő sorrendben
hagyjuk temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = hőmérséklet;
cserélve = igaz;
}
// Ha nem cseréltek elemeket, az azt jelenti, hogy a tömb most rendezve van,
// majd szakítsa meg a hurkot.
ha (felcserélve == hamis) {
szünet;
}
}
}
}
// Kinyomtatja a tömb elemeit
függvény printArray (arr, méret) {
for (legyen i = 0; éndocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// A tömb hosszának megkeresése
var size = arr.length;
// Az adott rendezetlen tömb kinyomtatása
document.write ("Nem rendezett tömb: 
");
printArray (arr, méret);
// A bubbleSort () függvény hívása
bubbleSort (arr, méret);
// A rendezett tömb kinyomtatása
document.write ("Rendezett tömb növekvő sorrendben: 
");
printArray (arr, méret);

Kimenet:

Válogatás nélküli tömb:
16 12 15 13 19
Rendezett tömb növekvő sorrendben:
12 15 13 16 19

Most már megérti a Bubble Sort algoritmus működését

A Bubble Sort a legegyszerűbb rendezési algoritmus, és elsősorban a rendezés alapjainak megértésére szolgál. A Bubble Sort rekurzív módon is megvalósítható, de ehhez nem nyújt további előnyöket.

A Python használatával könnyedén megvalósíthatja a Bubble Sort algoritmust. Ha nem ismeri a Python-t, és meg akarja kezdeni az utazást, akkor a "Hello World" szkript használatával kezdeni remek választás.

A Python használatának megkezdése "Hello World" szkript használatával

A Python az egyik legnépszerűbb programozási nyelv, amelyet ma használnak. Kövesse ezt az oktatóanyagot az első Python szkript használatának megkezdéséhez.

Olvassa el a következőt

A szerzőről