Sorteerimine tehnikat programmeerimine: sorteerimine "mull"

Mullsortimine on mitte ainult lugeda kiireim, pealegi sulgeb nimekirja aeglaseim võimalusi korraldada. Siiski on oma eelised. Seega meetod sorteerimine mull - kõige, et ei on loomulik ja loogiline lahendus, kui soovite korraldada esemeid kindlas järjekorras. Tavaline inimene käsitsi, näiteks siis neid kasutada - lihtsalt intuitsiooni.

Kust selline ebatavaline nimi?

Meetod nimi tuli, kasutades analoogiat õhumullid vees. See on metafoor. Just nii vähe õhumullid tõusevad ülespoole -, sest nende tihedus on suurem kui vedeliku (antud juhul - vesi), ja iga massiivi element, seda väiksem on väärtus, seda rohkem järkjärguline viis tippu numbrid.

Kirjeldus algoritm

Mullsortimine toimub järgmiselt:

• esmase: elementide omaduste numbrid on võetud kaks paari, ja ka võrreldes. Kui mõned elemendid kahe-mehe meeskond esimene väärtus on suurem kui teine programm teeb neist kohti vahetada;
• järelikult on kõige rohkem igatseb lõpuks massiiv. Kuigi kõik muud elemendid jäävad nagu nad olid, kaootiliselt, ja nõuavad rohkem sorteerimine;
• ning seetõttu on vaja teise pass: see on valmistatud analoogselt eelmise (juba kirjeldatud) ja on mitmeid võrdlusi - miinus üks;
• passaažid number kolm võrdlust, üks väiksem kui teine, ja kaks, kui esimene. Ja nii edasi;
• kokku, et iga läbipääsu on (kõik väärtused massiivi, konkreetse number) miinus (passaažinumbril) võrdlusi.

Isegi lühem algoritm programmi võib kirjutada:

• massiivi numbrid kontrollitakse nii kaua kui tahes kaks arvu on leitud, teine neist on kindlasti suurem kui esimene;
• valesti paigutatud üksteise suhtes elemendid massiivi tarkvara vahetustehingud.

Pseudokoodi põhineb kirjeldatud algoritmi

Lihtsaim rakendamise viiakse läbi järgmiselt:

Sortirovka_Puzirkom protseduuri;

algus

tsüklisse j alates nachalnii_index kuni konechii_index;

tsüklisse i alates nachalnii_index kuni konechii_index-1;

Kui massiv [i]> massiv [i + 1] (esimene element on suurem kui teine), siis:

(Muuda asetab väärtused);

lõpp

Muidugi, see lihtsus vaid raskendab olukorda: lihtsam algoritm, seda enam avaldub kõik vead. Investeeringute suhe on liiga suur isegi väikese hulga (siin on suhtelisus: Aja tavakodanikule võib tunduda väike, kuid tegelikult programmeerija iga teine või isegi millisekundi vähesus).

Kulus paremaks elluviimiseks. Näiteks, võttes arvesse vahetada väärtuste massiivi kohtades:

Sortirovka_Puzirkom protseduuri;

algus

sortirovka = true;

Tsükli kuni sortirovka = true;

sortirovka = false;

tsüklisse i alates nachalnii_index kuni konechii_index-1;

Kui massiv [i]> massiv [i + 1] (esimene element on suurem kui teine), siis:

(Muuta elemente kohad);

sortirovka = true; (Tuvastatud, et vahetada on tehtud).

End.

piirangud

Peamiseks puuduseks - kestus protsessi. Kui palju aega on läbi sorteerimisalgoritm mull?

Ooteaeg arvutatakse arvu ruudu numbrite massiiv - lõpptulemus see on proportsionaalne.

Kui halvimal juhul massiivi on möödas nii palju kordi kui ta on elementide miinus üks väärtus. See juhtub, sest lõpuks on ainult üks element, mis on midagi võrrelda, ning viimase läbida array muutub kasutuks meetmeid.

Lisaks tõhus meetod sorteerimine lihtne vahetada, nagu seda nimetatakse, ainult massiivid väiksus. Suurte andmemahtude abiga protsess ei toimi: tulemus on kas viga või rike programmi.

väärikus

Mullsortimine on väga lihtne aru saada. Õppekavad tehnikaülikoolide uuringu tellimise elemente oma massiivi edasi esiteks. Meetod on lihtne rakendada programmeerimiskeelt Delphi (D (Delphi) ja C / C ++ (C / C pluss pluss), uskumatult lihtne algoritm asukoha väärtuste õiges järjekorras ja kell Pascal (Pa). Mullsortimine on ideaalne algajatele.

Tänu puudused algoritm ei kasutata kooliväliste eesmärkidel.

Visual sortimise põhimõte

Põhiaknasse massiivi 8 22 4 74 44 37 1 7

Etapp 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Etapp 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Etapp 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Etapp 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Etapp 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Etapp 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Etapp 7 1 4 7 8 22 37 44 74

Mullsortimine näiteks Pascal

näiteks:

const kol_mas = 10;

var massiv: massiiv [1..kol_mas] of täisarv;

a, b, k: integer;

alustama

writeln ( 'input', kol_mas, "elemente massiivi ');

võtta vastu: = 1 to kol_mas teha readln (massiv [a ]);

jaoks: = 1 kol_mas-1 do alustada

B: = a + 1 kol_mas ei hakata

Kui massiv [a]> massiv [ b] siis algab

k: = massiv [a]; massiv [a]: = massiv [ b]; massiv [b]: = k;

lõpetamiseks;

lõpetamiseks;

lõpetamiseks;

writeln ( 'pärast omamoodi ");

võtta vastu: = 1 to kol_mas teha writeln (massiv [a ]);

lõpus.

Näide mulli sorteerimine C keeles (C)

näiteks:

#include

#include

int main (int Argc, paalia * argv [])

{

int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

for (;;) {

ff = 0;

for (i = 7; i> 0; i -) {

if (massiv [i] [i- 1]) {

konverteerimine (massiv [i] massiv [i- 1]);

ff ++;

}

}

if (ff == 0) murda;

}

getch (); // kuva viivitus

return 0;

}.