Triedenie techniky v programovaní: triedenie "bublina"

bubble sort nie je len považovaný za najrýchlejší spôsob, okrem toho uzatvára zoznam najpomalších spôsobov, ako organizovať. Avšak, to má svoje výhody. To znamená, že spôsob triedenia bublina - najviac, že ani je prirodzeným a logickým riešením tohto problému, ak chcete usporiadať položky v určitom poradí. Obyčajný človek manuálne, napríklad, že bude používať - len intuíciou.

Kde sa také nezvyčajné meno?

Názov metódy prišiel za použitia analógie vzduchových bublín vo vode. Je to metafora. Rovnako ako malé vzduchové bubliny hore - pretože ich hustota je väčšia ako tekutina (v tomto prípade - sa voda), a každý prvok poľa, tým menšia je hodnota, tým pozvoľnejší až na vrchol čísiel zoznamu.

Popis algoritmu

bubble sort sa uskutočňuje nasledovne:

• Prvý priechod: prvky čísel pole je urobený dvoma pármi a tiež v porovnaní. Ak sú niektoré prvky tímu prvej hodnoty dvojčlennú je väčší ako druhý, program umožňuje im výmenu miest;
• v dôsledku toho, najväčší počet minie koniec poľa. Zatiaľ čo všetky ostatné prvky zostávajú tak, ako boli, v chaotickom spôsobom, a vyžadujú ďalšie triedenie;
• a preto vyžadujú druhý priechod: je analogicky s predchádzajúcou (už bolo popísané) a má rad porovnávanie - mínus jedna
• na počet pasáží tri porovnanie, je jedným menšie ako druhý, a dva, než prvý. A tak ďalej;
• zhrnúť, že každý priechod má (všetky hodnoty v poli, konkrétne číslo) mínus (počet priechod) porovnanie.

Ešte kratšie Algoritmus programu možno zapísať ako:

• rad čísel, sa kontroluje, ak sú nájdené dve čísla, druhý z nich je viazaný na väčší ako prvé;
• nesprávne umiestnené vo vzťahu k sebe navzájom prvky rady softwarových swap.

Pseudocode na základe algoritmu opísanom

Najjednoduchšie implementácie je vykonať takto:

Sortirovka_Puzirkom postup;

začiatok

cyklus pre j od nachalnii_index na konechii_index;

cyklus i z nachalnii_index do konechii_index-1;

ak Massiv [i]> massiv [i + 1] (prvý prvok väčšia ako druhá), potom:

(Zmena umiestni hodnoty);

koniec

Samozrejme, že táto jednoduchosť zhoršuje iba situácia: čím jednoduchší algoritmus, tým viac sa prejaví všetky nedostatky. Investičné pomer času je príliš veľký aj pre malé pole (tu prichádza v relativity: Doba pre laika môže zdať malé, ale v skutočnosti programátor každý druhý alebo dokonca milisekunda sa počíta).

Trvalo lepšiu implementáciu. Napríklad s prihliadnutím k výmene hodnôt v miestach poľa:

Sortirovka_Puzirkom postup;

začiatok

sortirovka = true;

cyklus, kým sortirovka = TRUE;

sortirovka = false;

cyklus i z nachalnii_index do konechii_index-1;

ak Massiv [i]> massiv [i + 1] (prvý prvok väčšia ako druhá), potom:

(Zmeniť prvky miesta);

sortirovka = true; (Zistil, že výmena bola vykonaná).

Koniec.

obmedzenia

Hlavnou nevýhodou - doba trvania procesu. Koľko času je vykonávané triedenie algoritmus bublina?

Dodacia lehota sa počíta z počtu štvorcových čísel v poli - konečný výsledok toho je priamo úmerná.

V prípade, že v najhoršom prípade je matica odovzdaný toľkokrát, koľkokrát je to má prvky mínus jednu hodnotu. To sa deje preto, že na konci je len jeden prvok, ktorý má s čím porovnávať, a posledný priechod pole bude k ničomu akcie.

Okrem toho, efektívny spôsob triedenia jednoduchú výmenu, ako sa tomu hovorí, len pre pole malých rozmerov. Veľké objemy dát s pomocou procesu nebude fungovať: výsledkom bude buď k chybe alebo zlyhaniu programu.

dôstojnosť

bubble sort je veľmi ľahké pochopiť. Učebné osnovy technických univerzít v štúdiu zadávacieho prvky svoje pole prejsť v prvom rade. Táto metóda je ľahko implementovať aj programovací jazyk Delphi (L (Delphi) a C / C ++ (C / C a plus), neuveriteľne jednoduchá hodnoty umiestnenie algoritmu v správnom poradí a vo Pascal (Pascal). Bubble sort je ideálny pre začiatočníkov.

Vzhľadom k nevýhodám algoritmu sa nepoužíva v mimoškolských účely.

Vizuálne princíp triedenia

Počiatočná pohľad na maticu 8 22 4 74 44 37 1 7

Krok 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

Krok 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

Krok 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

Krok 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

Krok 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

Krok 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Krok 7 1 4 7 8 22 37 44 74

bubble sort príklad v Pascale

príklad:

const kol_mas = 10;

var Massiv: array [1..kol_mas] o celé číslo;

a, b, k: celé číslo;

začať

writeln ( 'vstup', kol_mas, 'prvky pole');

pre a: = 1 až kol_mas urobiť readln (massiv [a ]);

pre a: = 1 až kol_mas-1 cieľ začať

pre b: = a + 1 až kol_mas sa začať

ak Massiv [a]> massiv [ b] a začne

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

skončiť;

skončiť;

skončiť;

writeln ( 'po akejsi');

pre a: = 1 až kol_mas robiť writeln (massiv [a ]);

end.

Príklad bublina radenie v jazyku C (C)

príklad:

#include

#include

int main (int argc, char * argv [])

{

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

pre (;;) {

ff = 0;

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

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

Odkladacia (Massiv [i], massiv [i- 1]);

ff ++;

}

}

if (ff == 0) break;

}

getch (); // Oneskorenie display

return 0;

}.