Az algoritmusok a megrendelő egydimenziós tömbök - Műszaki Fórum

Az algoritmusok a megrendelő egydimenziós tömbök

Gyakran az oktatási feladatok, amelyek forgalmazása fórumunkon megragadja rendezett tömb, azaz forrás tömbben elrendezett növekvő vagy csökkenő sorrendben. Sok olyan módszer (algoritmusok) e probléma megoldásának: 20-30 évvel ezelőtt, ők találták nehéz, megpróbálja megtalálni az „optimális”, gyors, stb Ma, figyelembe véve a sebesség a modern számítógépek, az ilyen tevékenységek IMHO nincs értelme, és ésszerűnek tűnik, hogy a vonat a diákok birtokában legalább egy eljárás, akkor a legjobb, „buborék”, mint a legnyilvánvalóbb és egyszerű, de nem - tanítani tovább kínozza ukazulyami gyermekek, mint a „használat behelyezés módszer. " Nos, nézzük foglalkozik az alapvető.

Úgy vettem észre, hogy ez az egyszerű és elegáns módja sok kezdő nehéz megérteni, sőt kérdésekre, mint „miért dupla loop - dimenziós tömb valamit?!” stb Néhányan azonban inkább esztelenül valahol perekatal program részletben így hajlamosak összekeverni a két hurok változó, ami természetesen „nem jó”. Közben, ha megnézi, mindenki könnyen írni, ez a megrendelő csak „ki a fejemből.”
Csináljunk egy példát az elemzés. Nyelv - Pascal (amely egyébként nem igazán számít).
Tegyük fel, hogy ez szükséges növekvő sorrendben a következő tömböt:
Április 3 5 2 1
Az elemek száma (5) jelöli n.
A kód:

Úgy vélem, hogy a jelentését a hurok test világos: ha az előző elem nem követik, azok felcserélődnek. Ebben az esetben vegye figyelembe, hogy a külső hurok i változó indexként nem használják, ez - csak egy számláló. De ahhoz, hogy igazán világos, mi a sorrendet a program:

Tehát ne feledd, az eredeti helye:

Az első járat a belső hurok (i = 1, j változik egy 4 = 5-1):
3 4 5 1 2 (kicserélt pozíciók az elemek az 1. és 2.)
Április 3 5 2 1 (a második és harmadik helyesek)
3 4 2 5 1 (kicserélt 3-as és 4 elem)
3 4 2 1 5 (kicserélt 4. és 5. pozícióban elem)

Ez könnyen belátható, hogy ahol van egy maximális elem, vége után az első belső ciklusban ez lesz az utolsó, vagyis ahova tartozik. Több, ezt a pozíciót nem érintette, mert a következő belső hurok megy 1-től 5-2 = 3:
Április 3 2 1 5 (első és második állvány helyes)
3 2 4 1 5 (kicserélt 2es és 3 elemek)
3 2 1 4 5 (kicserélt 3-as és 4 elem)

Ez a második legnagyobb elem (4) helyére. A következő ciklusban a j - 1 5-3 = 2:
2 3 1 4 5 (cserélt számokkal 1 és 2 elem)
2 1 3 4 5 (kicserélt 2es és 3 elemek)

És végül, az utolsó járat a j - 1 és 1:
1 2 3 4 5 (cserélt számokkal 1 és 2 elem)

Mindent! Mint látható, az elrendezés rendezve, a probléma megoldódott.
Miért van még mindig az úgynevezett „buborék” módszer? És képzeljétek el tömb formájában egy keskeny függőleges tartály folyadékkal, ahol az alsó indexek - az „alulról”, a vének - a „top”. Ezután a mozgás az elem mentén a tömb a lebegő, mint egy légbuborék az edényben. Egyszerű vizuális analógia.
Természetesen, ha meg kell rendezni az elemek nincsenek növekvő sorrendben és csökkenő sorrendben, arra van szükség, hogy módosítsa a jele egyenlőtlenség feltételes utasítást.

Ez lényegesen rosszabb, mint a „buborék” egyszerűsége és tisztasága, és ezenkívül, használatát igényli mesterséges vétel - extra járulékos elemmel (nélkül lehetséges, de akkor a program válik nehézkes). A lényeg: legyen az első n elem már „rendezett”, azaz Az első helyen a legkisebb elem. Ezután kezdve a második további módon, mint a „buborék” lánc páronkénti permutációs „üldözött” jobb, az elemek - első, második, majd a harmadik, és így tovább, amíg az n-edik. De hogyan teljesítette a feltételt, hogy az első helyen volt a legkisebb elem? De ez a „front”, és ragaszkodik a tömb egyszer „nulla” egy sorban elem, természetesen kevesebb, mint a többiek. kód:

rendezési módszer kiválasztása

Ez mind nagyon egyszerű - megtalálják a legkisebb eleme, a változó helyeken az első, majd keresse meg a legkisebb a többi, változó helyeken a második, stb amíg az utolsó előtti, amely, ha szükséges, helyet cserél az utóbbi. kód:

Itt - figyelem! MÓDSZER Shelley megoldja a problémát Végül csak végez előzetes „durva” osztályozás, és végül az ügy által indított behelyezése vagy buborék. Essence: kezdetben felcseréljük emelkedő elemek elosztva n / 2-es helyzetben (azaz, ha n = 6, majd 1-től 4, 2 és 5, és 3 és 6), akkor a "távolság" osztva két (kerekítve, természetesen), és az eljárást meg kell ismételni, és így tovább mindaddig, amíg a „pitch” válik egyenlővé 1. kód:

A módszer gyorsrendezés (Hoare algoritmus)

Tartják az egyik leggyorsabb és leghatékonyabb. Ugyanakkor, nagyon nenaglyaden és nehezen érthető. Shell némileg hasonlít az algoritmus, de ellentétben az utóbbi hozza kereshetőség. Következő, én alapvetően kölcsön anyagot a Wikipedia. mind a leírás és a műsorújságot.
A lépések a következők:

1. Válasszon ki egy elemet a tömbben, mely lehet nevezni a tartóelem. A szempontból a helyességét az algoritmus választása a tartóelem közömbös.
2. Működés elválasztási tömb: átszervezi a tömb úgy, hogy az összes elem, amelynek értéke kisebb, vagy egyenlő, mint a referencia-tag, kiderült, hogy a bal oldalán is és az elemek mind a referenciaérték meghaladása - jobb. Normál működés algoritmus:
   1. Két index - l és r. egyenlő a minimális és maximális index a megosztott tömb, ill.
   2. Ez kiszámítja az index a referencia elem m.
   3. Index L növekszik egymás fel, amíg az L-edik eleme pedig nem lehet nagyobb, vagy egyenlő, mint a referencia.
   4. Az index R csökken szekvenciálisan, amíg a r-edik elem egyenlő vagy kisebb, mint a referencia.
   5. Ha az r = l - Talált tömb mid - elválasztási művelet befejeződött, mindkét index pont a tartóelemhez.
   6. Ha l
3. Rekurzívan rendelni az al-tömbök, feküdt a bal és jobb oldalán a tartóelem.
4. Base rekurzió olyan kitek, amelyek egy vagy két elem. Eredeti visszatér az eredeti formájában, a második, ha szükséges, válogatás csökkenti a váltási a két elem. Mindezek a szegmensek már rendelhető az elválasztási eljárás.

Mivel minden egyes iteráció (Minden következő szint rekurzió) hossza feldolgozott tömb intervallum csökken legalább egy, a rekurziót leágazó eléri, a feldolgozás, biztosítani kell teljes.

A végrehajtás az algoritmus lehet végrehajtani, mint a rekurzió, és nélküle. Az utóbbi esetben a program jelentősen bővült.

Itt rendelés a műsorok egész tömb emelkedő segítségével egy rekurzív eljárás:

Rábukkantam ide ma reggel egy másik módszerrel. Egyszerű és buta. Mivel én nem tudom, hogy hívják, és van-e bármilyen módon egyáltalán, nevezzük „módszer XXXX”.
Az alsó sorban: adjon meg egy logikai változó b-box és elkezd több járat a tömb elejétől a végéig swapping szomszédos „rendetlen” elemek, és így nem olyan hosszú, mint egy ilyen „rendezetlen” párok ne maradjanak, azaz adott, mielőtt a következő folyosón a flag értéke ugyanaz marad (ha megfelel legalább egy „véletlen” pár, a jelölőnégyzet be van kapcsolva). kód:

__________
Az alábbiakban képernyőképeken elrendelő azonos tömb az összes figyelembe vett módszerekkel. Ismét felhívjuk a figyelmet a „hiányos” a módszer a Shell.

__________________
A Mozilla Firefox - egyenesen a kommunizmus!