Válogató technikák programozás: válogatás „buborék”

buborék rendezés nem csak úgy, hogy a leggyorsabb módszer, sőt bezárja a listát a leglassabb módon megszervezni. Azonban megvannak az előnyei. Így a módszer válogatás buborék - a leginkább, hogy sem egy természetes és logikus megoldás a problémára, ha azt szeretné, hogy gondoskodjon a terméket egy adott sorrendben. Egy átlagember manuálisan, például, akkor használja őket - csak az intuíció.

Hol volt ilyen szokatlan név?

Módszer neve merült fel, az analógia légbuborékok a víz. Ez egy metafora. Ahogyan a kis légbuborékok felfelé -, mert a sűrűsége nagyobb, mint egy folyadék (ebben az esetben - a víz), és minden elemet egy kisebb ez az érték, annál fokozatos utat a lista tetején számokat.

Leírás az algoritmus

buborék a fajta az alábbiak szerint végezzük:

• első menetben: az elemek a tömb számok által hozott két pár, továbbá összehasonlítottuk. Ha egyes elemeit a két fős csapat első érték nagyobb, mint a második, a program teszi őket csere helyeken
• Következésképpen, a legtöbb hiányzik a végén a tömb. Míg az összes többi elem marad, mint volt, a kaotikus módon, és szükség több válogatás;
• és ezért egy második menetben: készül analóg módon az előző (a már ismertetett), és van egy összehasonlítások száma - mínusz egy;
• A járat száma három összehasonlítást, eggyel kevesebb, mint a második, és a két, mint az első. És így tovább;
• Összefoglalva, hogy minden egyes járatnak (minden érték a tömbben, az adott szám) mínusz (passzálási szám) összehasonlításokat.

Még rövidebb algoritmus a program felírható:

• egy sor számok ellenőrizzük mindaddig, amíg bármely két számok találhatók, a második közülük van kötve, hogy nagyobb, mint az első;
• helytelenül elhelyezkedésű egymáshoz képest elemeit a tömb szoftver swap.

Pszeudokódját algoritmus alapján leírt

A legegyszerűbb végrehajtásuk az alábbiak szerint:

Sortirovka_Puzirkom eljárás;

kezdet

ciklus j a nachalnii_index a konechii_index;

ciklus I nachalnii_index hogy konechii_index-1;

ha massiv [i]> massiv [i + 1] (első elem nagyobb, mint egy második), akkor:

(Változás helyezi értékek);

vég

Természetesen ez az egyszerűség csak súlyosbítja a helyzetet: az egyszerűbb az algoritmus, annál inkább megnyilvánul a hibákat. Beruházási ráta az idő túl nagy, még egy kis tömb (itt jön a relativitás: Az az idő, a laikusok számára tűnhet kicsi, de valójában egy programozó minden második vagy akár ezredmásodperc számít).

Azt a jobb végrehajtás érdekében. Például, figyelembe véve az értékek cseréjének tömbben helyeken:

Sortirovka_Puzirkom eljárás;

kezdet

sortirovka = true;

ciklus amíg sortirovka = true;

sortirovka = false;

ciklus I nachalnii_index hogy konechii_index-1;

ha massiv [i]> massiv [i + 1] (első elem nagyobb, mint egy második), akkor:

(Változtatni elemek helyeken);

sortirovka = true; (Megállapították, hogy a csere megtörtént).

Vége.

korlátozások

A fő hátránya - a szerint az eljárás időtartama. Mennyi idő van végre válogatás algoritmus buborék?

Átfutási idő számított száma négyzet számok a tömbben - a végeredmény ez arányos.

Ha a legrosszabb esetben a tömb vezetjük ahányszor vannak elemei mínusz egy értéket. Ez azért történik, mert a végén csak egy elem, aminek semmi összehasonlítani, és az utolsó áthaladás tömb használhatatlanná válik lépéseket.

Emellett hatékony módszer a válogatás egy egyszerű csere, ahogy nevezik, csak a tömbök a kis méret. Nagy mennyiségű adat segítségével folyamat nem fog működni: az lesz az eredmény, vagy egy hiba vagy meghibásodás a program.

méltóság

buborék rendezés nagyon könnyű megérteni. A tananyag a műszaki egyetemek, a tanulmány a rendelési elemeit tömb át az első helyen. A módszer könnyen alkalmazható, mind a Delphi programozási nyelv (L (Delphi) és a C / C ++ (C / C plus plus), egy hihetetlenül egyszerű értékeinek helyét algoritmus a megfelelő sorrendben, és a Pascal (Pascal). Bubble sort ideális kezdőknek.

Mivel a hátránya az algoritmus nem használják a tanórán kívüli célra.

Visual rendezési elv

A kezdeti nézete a tömb 8 22 4 74 44 37 1 7

1. lépés 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

2. lépés 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

3. lépés 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

4. lépés 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

5. lépés: 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

6. lépés 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

7. lépés 1 4 7 8 22 37 44 74

buborék a fajta például Pascal

például:

const kol_mas = 10;

var massiv: array [1..kol_mas] az egész;

a, b, k: integer;

kezdődik

writeln ( 'input', kol_mas, 'elemei tömb');

Egy: = 1 kol_mas do readln (massiv [a ]);

Egy: = 1 kol_mas-1 do kezdődik

A b: = a + 1 kol_mas nem kezdődik

ha massiv [a]> massiv [ b] akkor kezdődik

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

végén;

végén;

végén;

writeln ( 'után a fajta');

Egy: = 1 kol_mas do writeln (massiv [a ]);

végén.

Példa buborék válogató C nyelven (C)

például:

#include

#include

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

{

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

for (;;) {

ff = 0;

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

ha a (massiv [i] [i- 1]) {

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

ff ++;

}

}

ha (ff == 0) break;

}

getch (); // megjelenítés késleltető

vissza 0;

}.