Flokkun tækni í forritun: flokkun "kúla"

kúla tegund er ekki aðeins talin vera hraðasta aðferð, auk þess að það lokast á lista yfir the hægur leiðir til að skipuleggja. Hins vegar hefur það sína kosti. Þannig aðferð við flokkun kúla - sem mest að hvorki er eðlilegt og rökrétt lausn á því vandamáli, ef þú vilt að raða hlutum í ákveðna röð. Venjuleg manneskja höndunum, til dæmis, mun það nota þá - bara af innsæi.

Þar gerði svo óvenjulegt nafn?

Aðferðin nafn kom upp, nota líkingar af loftbólur í vatni. Það er samlíking. Rétt eins og litlu loftbólur rísa upp - því þéttleiki þeirra er meiri en vökva (í þessu tilviki - er vatn), og hvert fylki frumefni, því minni er það gildi, hægari leið til the toppur af the listi númer.

Lýsing á reiknirit

kúla tegund er framkvæmd á eftirfarandi hátt:

• í fyrstu umferð: þætti af the array tölum er tekin af tvö pör og einnig í samanburði. Ef sumir þættir í tveggja manna lið fyrsta gildi er meiri en annar, the program gerir þá skipti stöðum;
• Þar af leiðandi, mesta fjölda saknar lok array. En allir aðrir þættir haldast eins og þeir voru, í óskipulegur hátt, og þurfa fleiri flokka;
• og því þurfa annað skot: það er gert á hliðstæðan hátt með fyrri (þegar lýst) og hefur fjölda samanburðar - mínus einn;
• á siglingu númer þrjú samanburð, einn minna en á öðrum, og þau tvö, en hin fyrri. Og svo framvegis;
• draga að hver leið hefur (öll gildi í fylkinu, einkum tala) mínus (Passage NUMBER) samanburð.

Jafnvel styttri reiknirit a program er hægt að skrifa sem:

• An array af tölum er merkt eins lengi og einhverjar tvær tölur er að finna, annað þeirra er skylt að vera meiri en fyrsta;
• rangt staðsettur í tengslum við hvora aðra þætti í array hugbúnaður skiptasamninga.

Sauðakóðanum byggt á algrími sem lýst

Einfaldasta útfærsla fer fram sem hér segir:

Sortirovka_Puzirkom aðferð;

hefst

hringrás fyrir J frá nachalnii_index til konechii_index;

hringrás fyrir I Frá nachalnii_index til konechii_index-1;

ef Massiv [i]> Massiv [i + 1] (fyrsti þáttur meiri en úr sekúndu), þá:

(Breyting leggur gildi);

enda

Auðvitað, þetta einfaldleiki aggravates aðeins ástandið: einfaldara reiknirit, því meira sem það birtist alla galla. Hlutfall fjárfestingar af tímanum er of mikill, jafnvel fyrir lítið array (hér kemur í afstæðiskenningin: Tíminn fyrir leikmaður kann að virðast lítið, en í raun forritara annað eða jafnvel millísekúnda á talningar).

Það tók betri framkvæmd. Til dæmis, að teknu tilliti skipti á gildum í array stöðum:

Sortirovka_Puzirkom aðferð;

hefst

sortirovka = true;

hringrás þar til sortirovka = true;

sortirovka = false;

hringrás fyrir I Frá nachalnii_index til konechii_index-1;

ef Massiv [i]> Massiv [i + 1] (fyrsti þáttur meiri en úr sekúndu), þá:

(Breyting þætti stöðum);

sortirovka = true; (Sem að gengi hefur verið gert).

End.

takmarkanir

Helstu gallar - lengd ferlisins. Hversu mikill tími fer fram flokkun reiknirit kúla?

Afgreiðslutími er reiknað út frá fjölda Square tölur í array - niðurstaðan af það er í réttu hlutfalli.

Ef versta tilfelli array er liðinn eins oft og það hefur þætti mínus eitt gildi. Þetta gerist vegna þess að í lok það er aðeins einn þáttur, sem hafa ekkert til að bera saman, og síðasta umferð í gegnum array verður gagnslaus aðgerð.

Að auki, áhrifarík aðferð flokka einföld skipti, eins og það er kallað, aðeins fyrir fylki smæðar. Mikið magn af gögnum með hjálp ferli mun ekki virka: útkoman verður annaðhvort villa eða bilun af the program.

reisn

kúla tegund er mjög auðvelt að skilja. Námskrár tækniháskólum rannsókn á panta þætti array fara í fyrsta sæti. Aðferðin er auðvelt að framkvæma bæði Delphi forritunarmál (L (Delphi), og C / C ++ (C / C plús plús), ótrúlega einföld gildum staðsetningu reiknirit í réttri röð og á Pascal (Pascal). Bubble tegund er tilvalin fyrir byrjendur.

Vegna göllum reiknirit er ekki notað í félagsstörfum tilgangi.

Visual flokkun meginreglu

Upphafleg view array 8 22 4 74 44 37 1 7

Skref 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

Skref 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

Skref 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

Skref 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

Skref 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

Skref 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Skref 7 1 4 7 8 22 37 44 74

kúla raða dæmi í Pascal

dæmi:

const kol_mas = 10;

Var Massiv: array [1..kol_mas] af heiltala;

a, b, K: heiltala;

byrja

writeln ( 'input', kol_mas, 'þætti af array');

fyrir a: = 1 til kol_mas gera readln (Massiv [a ]);

fyrir a: = 1 í kol_mas-1 gera að byrja

fyrir b: = a + 1 til kol_mas gera byrja

ef Massiv [a]> Massiv [ b] þá byrja

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

enda;

enda;

enda;

writeln ( 'eftir tegund');

fyrir a: = 1 til kol_mas gera writeln (Massiv [a ]);

enda.

EXAMPLE kúla efla flokkun C tungumál (C)

dæmi:

#include

#include

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

{

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

fyrir (;;) {

FF = 0;

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

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

skipti (Massiv [i], Massiv [i- 1]);

FF ++;

}

}

ef (FF == 0) brjóta;

}

getch (); // sýna seinkun

aftur 0;

}.