Sorting teknikat në programimin: sorting "flluskë"

lloj flluskë jo vetëm që konsiderohet të jetë metoda më të shpejtë, për më tepër, ajo mbyllet listën e mënyrave slowest për të organizuar. Megjithatë, ajo ka avantazhet e tij. Kështu, metoda e klasifikim flluskë - më se as është një zgjidhje e natyrshme dhe logjike për problemin, në qoftë se ju doni të rregulluar sendet në një mënyrë të veçantë. Një njeri i zakonshëm me dorë, për shembull, ajo do të përdorin ato - vetëm nga intuitë.

Ku ka një emër të tillë të pazakontë?

Emri metodë doli, duke përdorur analogjinë e flluska e ajrit në ujë. Kjo është një metaforë. Ashtu si flluska pak ajër të rritet lart - për shkak se dendësia e tyre është më i madh se një lëng (në këtë rast - ujë), dhe çdo element array, aq më i vogël është vlera, mënyra më gradual në krye të numrave listës.

Përshkrimi i algoritmit

flluskë lloj kryhet si më poshtë:

• kalojë së pari: elementet e numrave array është marrë nga dy çifte dhe krahasuar. Nëse disa elemente të dy-njeri ekip vlera e parë është më i madh se i dyti, programi i bën ata vende të këmbimit;
• Si rrjedhojë, numri më i madh i mungon fundi i vektorit. Ndërsa të gjitha elementet e tjera mbeten siç ishin, në një mënyrë kaotike, dhe kërkojnë më klasifikim;
• dhe për këtë arsye kërkojnë një pasim të dytë: ajo është bërë nga analogji me e mëparshme (përshkruar tashmë) dhe ka një numër të krahasimeve - minus një;
• në numrin kalimi tre krahasime, një më pak se i dyti, dhe dy, se e para. Dhe kështu me radhë;
• përmblidhni se çdo pasazh ka (të gjitha vlerat në rrjet, numri i veçantë) minus (numri pasazh) krahasime.

algorithm edhe më e shkurtër e një programi mund të shkruhet si:

• një grup i numrave është i kontrolluar për sa kohë që çdo dy numra janë gjetur, i dyti prej tyre është i detyruar të jetë më e madhe se e para;
• pozicionuar gabimisht në raport me çdo elemente të tjera të swap-eve array software.

Pseudokod bazuar në algoritmin e përshkruar

Zbatimi i thjeshtë kryhet si më poshtë:

Procedura Sortirovka_Puzirkom;

fillim

cikël për j nga nachalnii_index te konechii_index;

cikël për i nga nachalnii_index te konechii_index-1;

nëse massiv [i]> massiv [i + 1] (element i parë të madhe se një të dytë), atëherë:

(Ndryshimi vendos vlerat);

fund

Sigurisht, kjo thjeshtësi vetëm përkeqëson situatën: thjeshtë më të algorithm, aq më shumë ajo manifeston të gjitha të metat. Raporti investim i kohës është shumë i madh edhe për një grup të vogël (këtu vjen në relativitetin: Shuma e kohës për laik mund të duket e vogël, por në fakt një programues çdo akuza e dytë apo edhe milisekonda).

Ajo mori zbatimin më të mirë. Për shembull, duke marrë parasysh shkëmbimin e vlerave në lokacione array:

Procedura Sortirovka_Puzirkom;

fillim

sortirovka = vërtetë;

Cikli deri sortirovka = e vërtetë;

sortirovka = false;

cikël për i nga nachalnii_index te konechii_index-1;

nëse massiv [i]> massiv [i + 1] (element i parë të madhe se një të dytë), atëherë:

(Ndryshuar elemente vende);

sortirovka = vërtetë; (Identifikuar se shkëmbimi është bërë).

End.

kufizimet

Disavantazhi kryesor - kohëzgjatja e procesit. Sa kohë është kryer sorting algorithm flluskë?

koha Lead është llogaritur nga numri i numrave katrorë në grup - rezultati përfundimtar i saj është proporcional.

Nëse rasti më i keq array është kaluar si shumë herë si ajo ka elemente minus një vlerë. Kjo ndodh për shkak se në fund ka vetëm një element, që nuk kanë asgjë për të krahasuar, dhe të kalojë fundit nëpër rrjet bëhet veprim i kotë.

Përveç kësaj, metodë efektive e klasifikim një shkëmbim të thjeshtë, siç është quajtur, vetëm për vargjeve të madhësisë së vogël. sasi të mëdha të të dhënave me ndihmën e procesit nuk do të funksionojë: rezultati do të jetë ose një gabim apo dështim i programit.

dinjitet

flluskë lloj është shumë e lehtë për të kuptuar. Kurrikulat e universiteteve teknike në studimin e elementeve Renditja e grup e saj të kalojë në vendin e parë. Metoda është e lehtë për të zbatuar të dy gjuhë Delphi programimit (L (Delphi), dhe C / C ++ (C / C plus plus), një vlerat tepër e thjeshtë e lokacionit algorithm në mënyrë të duhur dhe në Pascal (Pascal). Bubble lloj është ideale për fillestar.

Për shkak të meta të algorithm nuk është përdorur në qëllime jashtëshkollore.

Parimi Visual sorting

Pikëpamja fillestar i vektorit 8 22 4 74 44 37 1 7

Hapi 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

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

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

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

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

6. 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

7. 1 4 7 8 22 37 44 74

flluskë lloj shembulli në Pascal

shembull:

kol_mas const = 10;

var massiv: grup [1..kol_mas] të integer;

a, b, k: integer;

filloj

writeln ( 'hyrje', kol_mas, 'elementet e vektorit');

për a: = 1 deri kol_mas bëjë readln (massiv [a ]);

për një: = 1 deri kol_mas-1 do të fillojnë

për b: = a + 1 deri kol_mas do të fillojnë

nëse MASSIV [a]> massiv [ b] pastaj të fillojë

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

fund;

fund;

fund;

writeln ( 'pas lloj');

për a: = 1 deri kol_mas bëjë writeln (massiv [a ]);

në fund.

SHEMBULL flluskë klasifikim në gjuhën C (C)

shembull:

#include

#include

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

{

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

për (;;) {

ff = 0;

për (i = 7; i> 0; i -) {

nëse (massiv [i] [i- 1]) {

shkëmbimit (massiv [i], massiv [i- 1]);

ff ++;

}

}

nëse (ff == 0) thyer;

}

getch (); // vonesë ekran

kthimin 0;

}.