Třídění metod v programování: třídění podle bubliny

Třídění bublinou není považováno za nejrychlejší metodu, ale navíc zavírá seznam nejpomalejších způsobů objednávání. Má však také své výhody. Takže třídění metodou bubliny je nejlogičtějším a přirozenějším řešením problému, pokud chcete uspořádat prvky v určitém pořadí. Jeden obyčejný člověk například použije ručně, jednoduše pomocí intuice.

Odkud pochází toto neobvyklé jméno?

Název metody byl vynalezen pomocí analogie se vzduchovými bublinami ve vodě. To je metafora. Stejně jako malé vzduchové bubliny vznikají na vrchol - protože jejich hustota je větší než jakákoliv kapalina (v tomto případě voda) a každý prvek pole, tím menší je hodnota, tím více se postupně dostává na začátek seznamu čísel.

Popis algoritmu

Třídění podle bubliny se provádí následovně:

• první průchod: prvky pole čísel se odeberou ve dvou a porovnávají se také ve dvojicích. Pokud v některých dvou prvcích je první hodnota větší než druhá, program provádí jejich výměnu míst;
• proto, největší počet spadá do konce pole. Zatímco všechny ostatní prvky zůstávají v chaotickém pořádku a vyžadují další třídění;
• proto je potřeba druhý průchod: je vyroben analogicky s předchozím (již popsaným) a má řadu srovnání - mínus jeden;
• při průchodu jsou srovnávání číslo tři menší než druhá a dvě než první. A tak dále;
• Zkusme shrnout, že každý průkaz má (v poli, konkrétní číslo) mínus (počet průchodů) srovnání.

Dokonce i kratší algoritmus budoucího programu lze psát následovně:

• pole čísel je kontrolováno, dokud nenaleznou dvě čísla, z nichž druhá musí být větší než první;
• které se nesprávně nacházejí ve vztahu k ostatním prvkům pole, program swapy.

Pseudokód založený na popsaném algoritmu

Nejjednodušší implementace je následující:

Postup Sortirovka_Puzirkom-

Začátek

cyklus pro j od nachalnii_index až do konechii_index-

cyklus pro i od nachalnii_index až do konechii_index-1-

pokud masiv [i]> masiv [i + 1] (první prvek je větší než druhý), potom:

(změna hodnot na místě) -

Konec

Samozřejmě zde jednoduše situaci jen zhoršuje: čím jednodušší je algoritmus, tím více ukazuje všechny nedostatky. Časově náročné je příliš velké i pro malé pole (tady přichází relativita: pro průměrného člověka se čas může zdát malý, ale v programátoru každou sekundu nebo dokonce milisekund na účtu).

Brali lepší implementaci. Například při zohlednění výměny hodnot v poli v některých místech:

Postup Sortirovka_Puzirkom-

Začátek

sortirovka = true-

cyklus až do sortirovka = true-

sortirovka = lži-

cyklus pro i od nachalnii_index až do konechii_index-1-

pokud masiv [i]> masiv [i + 1] (první prvek je větší než druhý), potom:

(měníme prvky na místech) -

sortirovka = true- (znamená, že výměna byla provedena).

Konec.

Nevýhody metody

Hlavní nevýhodou - doba trvání procesu. Jak dlouho trvá? třídící algoritmus bublina?

Doba provedení se vypočítá ze čtverce počtu čísel v poli - konečný výsledek je úměrný.

Při nejhorším scénáři bude pole procházet tolikrát, kolikrát jsou v něm prvky, mínus jedna hodnota. Je to proto, že na konci je pouze jeden prvek, který nemá nic srovnat a poslední průchod přes pole se stává zbytečnou akcí.

Kromě toho metoda třídění jednoduchými výměnami, jak se také nazývá, je účinná pouze pro pole malých rozměrů. Velké množství dat nemůže být zpracováno s využitím: výsledek bude buď chyba, nebo selhání programu.

Výhody

Třídění bubliny je velmi jednoduché. Ve studijních plánech technických vysokých škol při průchodu prvků pole přechází nejprve. Metoda je snadno implementována jak v programovacím jazyce Delphi (D (Delphi), tak v C / C ++ (C / C plus plus), což je neuvěřitelně jednoduchý algoritmus pro uspořádání hodnot ve správném pořadí a na Pascal (Pascal). Třídění bublin je ideální pro začátečníky.

Z důvodu nedostatků se algoritmus nepoužívá pro mimoškolní účely.

Jasná zásada třídění

Počáteční pohled pole je 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

Příklad třídění bubliny v Pascalu

Příklad:

const kol_mas = 10-

var masiv: array [1..kol_mas] z integer-

a, b, k: integer-

začít

writeln (`vstup`, kol_mas, `prvky pole`) -

pro: = 1 až kol_mas do readln (massiv [a]) -

pro: = 1 do kol_mas-1 začít

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

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

k = masiv [a] - masiv [a]: = masiv [b] - massiv [b]: = k-

end-

end-

end-

writeln ("po třídění") -

pro: = 1 k kol_mas do writeln (massiv [a]) -

konce.

Příklad třídění bublinou v C (C)

Příklad:

#include

#include

int hlavní (int argc, char * argv [])

{{

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

pro (- -) {

ff = 0-

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

pokud (massiv [i] < masiv [i-1]) {

swap (masiv [i], massiv [i-1]) -

ff ++ -

}}

}}

pokud (ff == 0)

}}

getch () - // zpoždění obrazovky

návrat 0-

}.