Sissejuhatus mullide sorteerimise algoritmi

Sorteerimine on üks põhilisemaid toiminguid, mida saate andmetele rakendada. Elemente saab sorteerida erinevates programmeerimiskeeltes, kasutades erinevaid sorteerimisalgoritme, nagu Kiire sortimine, Mullide sortimine, Ühenda sortimine, Lisamissort jne Mullide sorteerimine on kõige lihtsam algoritm nende kõigi seas.

Selles artiklis saate teada Bubble Sort algoritmi, mullide sorteerimise pseudokoodi töötamise kohta algoritm, selle aja ja ruumi keerukus ning rakendamine erinevates programmeerimiskeeltes nagu C ++, Python, C ja JavaScripti.

Kuidas mullide sorteerimise algoritm töötab?

Mullisorteerimine on kõige lihtsam sorteerimisalgoritm, mis sirvib loendit korduvalt, võrdleb külgnevaid elemente ja vahetab need vales järjekorras. Seda mõistet saab näite abil tõhusamalt seletada. Vaatleme sorteerimata massiivi, millel on järgmised elemendid: {16, 12, 15, 13, 19}.

Näide:

Siin võrreldakse külgnevaid elemente ja kui need pole kasvavas järjekorras, vahetatakse need omavahel.

Mullide sorteerimise algoritmi pseudokood

Pseudokoodis, Bubble Sort algoritmi saab väljendada järgmiselt:

mullSorteeri (Arr [], suurus)
// silmus, et pääseda juurde iga massiivi elemendile
kui i = 0 kuni suurus 1, tehke järgmist:
// loop massiivi elementide võrdlemiseks
kui j = 0 suurusele i-1, tehke järgmist:
// võrrelda külgnevaid elemente
kui Arr [j]> Arr [j + 1] siis
// vahetage need
vahetada (Arr [j], Arr [j + 1])
lõpp, kui
lõpp
lõpp
lõpp

Ülaltoodud algoritm töötleb kõiki võrdlusi isegi siis, kui massiiv on juba sorteeritud. Seda saab veelgi optimeerida, peatades algoritmi, kui sisemine silmus ei põhjustanud vahetust. See vähendab algoritmi täitmisaega.

Seega saab optimeeritud Bubble Sort algoritmi pseudokoodi väljendada järgmiselt:

mullSorteeri (Arr [], suurus)
// silmus, et pääseda juurde iga massiivi elemendile
kui i = 0 kuni suurus 1, tehke järgmist:
// kontrollige, kas vahetamine toimub
vahetatud = vale
// loop massiivi elementide võrdlemiseks
kui j = 0 suurusele i-1, tehke järgmist:
// võrrelda külgnevaid elemente
kui Arr [j]> Arr [j + 1] siis
// vahetage need
vahetada (Arr [j], Arr [j + 1])
vahetatud = tõene
lõpp, kui
lõpp
// kui ühtegi elementi ei vahetatud, see tähendab, et massiiv on nüüd sorteeritud, siis katkestage silmus.
kui (ei vahetata) siis
murda
lõpp, kui
lõpp
lõpp

Mullide sorteerimise algoritmi ajaline keerukus ja abiruum

Mullide sorteerimise algoritmi halvim ajaline keerukus on O (n ^ 2). See tekib siis, kui massiiv on kahanevas järjekorras ja soovite sortida kasvavas järjekorras või vastupidi.

Mullide sorteerimise algoritmi parim aeg-keerukus on O (n). See tekib siis, kui massiiv on juba sorteeritud.

Seotud: Mis on Big-O tähistamine?

Mullide sorteerimise algoritmi keskmine juhtumi keerukus on O (n ^ 2). See tekib siis, kui massiivi elemendid on segamini aetud.

Bubble Sort algoritmi jaoks vajalik lisaruum on O (1).

C ++ Bubble Sort algoritmi rakendamine

Allpool on Bubble Sort algoritmi C ++ rakendamine:

// C ++ rakendamine
// optimeeritud mullide sorteerimise algoritm
# kaasata 
nimeruumi kasutamine std;
// Funktsioon mullide sorteerimise teostamiseks
void bubbleSort (int arr [], int size) {
// Loop massiivi igale elemendile juurdepääsuks
for (int i = 0; i // Muutuv, et kontrollida, kas vahetamine toimub
bool vahetatud = vale;
// loop massiivi kahe kõrvuti asetseva elemendi võrdlemiseks
for (int j = 0; j // Kahe kõrvuti asetseva massiivi elemendi võrdlemine
kui (arr [j]> arr [j + 1]) {
// Vahetage mõlemad elemendid, kui need on
// pole õiges järjekorras
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
vahetatud = tõene;
}
}
// Kui ühtegi elementi ei vahetatud, tähendab see, et massiiv on nüüd sorteeritud,
// siis katkesta silmus.
kui (vahetatud == vale) {
murda;
}
}
}
// Prindib massiivi elemendid
void printArray (int arr [], int suurus) {
for (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Massiivi pikkuse leidmine
int suurus = suurus (arr) / suurusof (arr [0]);
// Antud sorteerimata massiivi printimine
cout << "sortimata massiiv:" << endl;
printArray (arr, suurus);
// Funktsiooni bubbleSort () kutsumine
mullSorteeri (arr, suurus);
// Sorteeritud massiivi printimine
cout << "Sorteeritud massiiv kasvavas järjekorras:" << endl;
printArray (arr, suurus);
tagastus 0;
}

Väljund:

Sorteerimata massiiv: 
16 12 15 13 19 
Sorteeritud massiiv kasvavas järjekorras:
12 13 15 16 19

Mullide sorteerimise algoritmi Pythoni rakendamine

Allpool on Bubble Sort algoritmi Pythoni rakendus:

# Pythoni rakendamine
# optimeeritud mullide sorteerimise algoritm
# Funktsioon mullide sorteerimiseks
def mullSorteeri (arr, suurus):
# Loop loendi igale elemendile juurdepääsemiseks
i jaoks vahemikus (suurus-1):
# Muutuv, et kontrollida, kas vahetamine toimub
vahetatud = vale
# silmus loendi kahe külgneva elemendi võrdlemiseks
j jaoks vahemikus (suurus-i-1):
# Kahe kõrvuti asuva loendi elemendi võrdlemine
kui arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
vahetatud = tõene
# Kui ühtegi elementi ei vahetatud, tähendab see, et loend on nüüd sorditud,
# siis murra silmus.
vahetatuna == Vale:
murda
# Prindib loendi elemendid
def printArray (arr):
elemendi arr:
print (element, lõpp = "")
print ("")
arr = [16, 12, 15, 13, 19]
# Loendi pikkuse leidmine
suurus = len (arr)
# Antud sorteerimata loendi printimine
print ("Sorteerimata loend:")
printArray (arr)
# Funktsiooni bubbleSort () kutsumine
mullSorteeri (arr, suurus)
# Sorteeritud loendi printimine
print ("Sorteeritud loend kasvavas järjekorras:")
printArray (arr)

Väljund:

Sorteerimata loend:
16 12 15 13 19 
Sorteeritud loetelu kasvavas järjekorras:
12 13 15 16 19

Seotud: Kuidas kasutada Pythoni aasade jaoks

C Mullisorteerimise algoritmi rakendamine

Allpool on Bubble Sort algoritmi C-rakendus:

// C rakendamine
// optimeeritud mullide sorteerimise algoritm
# kaasata 
# kaasata 
// Funktsioon mullide sorteerimise teostamiseks
void bubbleSort (int arr [], int size) {
// Loop massiivi igale elemendile juurdepääsuks
for (int i = 0; i // Muutuv, et kontrollida, kas vahetamine toimub
bool vahetatud = vale;
// loop massiivi kahe kõrvuti asetseva elemendi võrdlemiseks
for (int j = 0; j // Kahe kõrvuti asetseva massiivi elemendi võrdlemine
kui (arr [j]> arr [j + 1]) {
// Vahetage mõlemad elemendid, kui need on
// pole õiges järjekorras
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
vahetatud = tõene;
}
}
// Kui ühtegi elementi ei vahetatud, tähendab see, et massiiv on nüüd sorteeritud,
// siis katkesta silmus.
kui (vahetatud == vale) {
murda;
}
}
}
// Prindib massiivi elemendid
void printArray (int arr [], int suurus) {
for (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Massiivi pikkuse leidmine
int suurus = suurus (arr) / suurusof (arr [0]);
// Antud sorteerimata massiivi printimine
printf ("sortimata massiiv: \ ⁠n");
printArray (arr, suurus);
// Funktsiooni bubbleSort () kutsumine
mullSorteeri (arr, suurus);
// Sorteeritud massiivi printimine
printf ("Sorteeritud massiiv kasvavas järjekorras: \ ⁠n");
printArray (arr, suurus);
tagastus 0;
}

Väljund:

Sorteerimata massiiv: 
16 12 15 13 19 
Sorteeritud massiiv kasvavas järjekorras: 
12 13 15 16 19

Mullide sorteerimise algoritmi JavaScripti rakendamine

Allpool on Bubble Sort algoritmi JavaScripti juurutamine:

// JavaScripti rakendamine
// optimeeritud mullide sorteerimise algoritm
// Funktsioon mullide sorteerimise teostamiseks
funktsioon bubbleSort (arr, size) {
// Loop massiivi igale elemendile juurdepääsuks
for (olgu i = 0; i// Muutuv, et kontrollida, kas vahetamine toimub
var vahetatud = vale;
// loop massiivi kahe kõrvuti asetseva elemendi võrdlemiseks
for (olgu j = 0; j// Kahe kõrvuti asetseva massiivi elemendi võrdlemine
kui (arr [j]> arr [j + 1]) {
// Vahetage mõlemad elemendid, kui need on
// pole õiges järjekorras
olgu temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
vahetatud = tõene;
}
// Kui ühtegi elementi ei vahetatud, tähendab see, et massiiv on nüüd sorteeritud,
// siis katkesta silmus.
kui (vahetatud == vale) {
murda;
}
}
}
}
// Prindib massiivi elemendid
funktsioon printArray (arr, suurus) {
for (olgu i = 0; idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Massiivi pikkuse leidmine
var size = arr.length;
// Antud sorteerimata massiivi printimine
document.write ("sortimata massiiv: 
");
printArray (arr, suurus);
// Funktsiooni bubbleSort () kutsumine
mullSorteeri (arr, suurus);
// Sorteeritud massiivi printimine
document.write ("Sorteeritud massiiv kasvavas järjekorras: 
");
printArray (arr, suurus);

Väljund:

Sorteerimata massiiv:
16 12 15 13 19
Sorteeritud massiiv kasvavas järjekorras:
12 15 13 16 19

Nüüd saate aru mullide sorteerimise algoritmi toimimisest

Mullisorteerimine on lihtsaim sorteerimisalgoritm ja seda kasutatakse peamiselt sorteerimise aluste mõistmiseks. Mullisorteerimist saab rakendada ka rekursiivselt, kuid see ei anna selleks täiendavaid eeliseid.

Pythoni abil saate hõlpsalt rakendada Bubble Sort algoritmi. Kui te pole Pythoniga tuttav ja soovite oma teekonda alustada, on stsenaariumiga "Hello World" alustamine suurepärane valik.

Kuidas alustada Pythoniga skripti "Hello World" kasutamist

Python on tänapäeval üks populaarsemaid programmeerimiskeeli. Esimese Pythoni skriptiga alustamiseks järgige seda õpetust.

Loe edasi

Autori kohta