Třídění techniky v programování: třídění „bublina“

bubble sort není jen považován za nejrychlejší způsob, kromě toho uzavírá seznam nejpomalejších způsobů, jak organizovat. Nicméně, to má své výhody. To znamená, že způsob třídění bublina - nejvíce, že ani je přirozeným a logickým řešením tohoto problému, pokud chcete uspořádat položky v určitém pořadí. Obyčejný člověk manuálně, například, že bude používat - jen intuicí.

Kde se takové neobvyklé jméno?

Název metody přišel za použití analogie vzduchových bublin ve vodě. Je to metafora. Stejně jako malé vzduchové bubliny vzhůru - protože jejich hustota je větší než tekutina (v tomto případě - se voda), a každý prvek pole, tím menší je hodnota, tím pozvolnější až na vrchol čísel seznamu.

Popis algoritmu

bubble sort se provádí následovně:

• První průchod: prvky čísel pole je pořízena dvěma páry a také ve srovnání. Pokud jsou některé prvky týmu první hodnoty dvoučlennou je větší než druhý, program umožňuje jim výměnu míst;
• v důsledku toho, největší počet mine konec pole. Zatímco všechny ostatní prvky zůstávají tak, jak byly, v chaotickém způsobem, a vyžadují další třídění;
• a proto vyžadují druhý průchod: je analogicky s předchozí (již bylo popsáno) a má řadu srovnávání - mínus jedna
• na počet pasáží tři srovnání, je jedním menší než druhý, a dva, než první. A tak dále;
• shrnout, že každý průchod má (všechny hodnoty v poli, konkrétní číslo) mínus (počet průchod) srovnání.

Ještě kratší Algoritmus programu lze zapsat jako:

• řada čísel, se kontroluje, pokud jsou nalezeny dvě čísla, druhý z nich je vázán na větší než první;
• nesprávně umístěné ve vztahu k sobě navzájem prvky řady softwarových swap.

Pseudocode na základě algoritmu popsaném

Nejjednodušší implementace je prováděno následujícím způsobem:

Sortirovka_Puzirkom postup;

začátek

cyklus pro j od nachalnii_index na konechii_index;

cyklus i z nachalnii_index do konechii_index-1;

pokud Massiv [i]> massiv [i + 1] (první prvek větší než druhá), potom:

(Změna umístí hodnoty);

konec

Samozřejmě, že tato jednoduchost zhoršuje pouze situace: čím jednodušší algoritmus, tím více se projeví všechny nedostatky. Investiční poměr času je příliš velký i pro malé pole (zde přichází v relativity: Doba pro laika může zdát malé, ale ve skutečnosti programátor každý druhý nebo dokonce milisekunda se počítá).

Trvalo lepší provádění. Například s přihlédnutím k výměně hodnot v místech pole:

Sortirovka_Puzirkom postup;

začátek

sortirovka = true;

cyklus, dokud sortirovka = TRUE;

sortirovka = false;

cyklus i z nachalnii_index do konechii_index-1;

pokud Massiv [i]> massiv [i + 1] (první prvek větší než druhá), potom:

(Změnit prvky místa);

sortirovka = true; (Zjistil, že výměna byla provedena).

Konec.

omezení

Hlavní nevýhodou - doba trvání procesu. Kolik času je prováděno třídění algoritmus bublina?

Dodací lhůta se počítá z počtu čtverečních čísel v poli - konečný výsledek toho je přímo úměrná.

V případě, že v nejhorším případě je matice předán tolikrát, kolikrát je to má prvky minus jednu hodnotu. To se děje proto, že na konci je jen jeden prvek, který má s čím srovnávat, a poslední průchod pole bude k ničemu akce.

Kromě toho, efektivní způsob třídění jednoduchou výměnu, jak se tomu říká, pouze pro pole malých rozměrů. Velké objemy dat s pomocí procesu nebude fungovat: výsledkem bude buď k chybě nebo selhání programu.

důstojnost

bubble sort je velmi snadné pochopit. Učební osnovy technických univerzit ve studiu zadávacího prvky své pole projít v první řadě. Tato metoda je snadno implementovat jako programovací jazyk Delphi (D (Delphi) a C / C ++ (C / C a plus), neuvěřitelně jednoduchý algoritmus pro umístění hodnot ve správném pořadí a ve Pascal (Pascal). Bubble sort je ideální pro začátečníky.

Vzhledem k nevýhodám algoritmu se nepoužívá v mimoškolních účelům.

Vizuální princip třídění

Počáteční pohled na matici 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 příklad v Pascalu

příklad:

const kol_mas = 10;

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

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

zahájit

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

pro a: = 1 až kol_mas udělat readln (massiv [a ]);

pro a: = 1 až kol_mas-1 cíl zahájit

pro b: = a + 1 až kol_mas se začít

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

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

skončit;

skončit;

skončit;

writeln ( 'po jakési');

pro a: = 1 až kol_mas dělat writeln (massiv [a ]);

end.

Příklad bublina řazení v jazyce C (C)

příklad:

#include

#include

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

{

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

pro (;;) {

ff = 0;

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

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

Odkládací (Massiv [i], massiv [i- 1]);

ff ++;

}

}

if (ff == 0) break;

}

getch (); // Zpoždění display

return 0;

}.