Válogatás fogalmak
A rendezés az egyik alapvető algoritmikus programozási feladat. Az egyes készletek elemeinek rendezésével kapcsolatos problémák megoldása nagyszámú vizsgálatra irányul, és számos algoritmust határozunk meg.
Szelektálás kell érteni, mint az átrendeződési folyamat egy adott sor tárgyak egy adott sorrendben, hogy megkönnyíti a későbbi keresés egy adott elem egy adott halmazában, és az elemek alatt rendezhető tetszőleges tárgyakat lehet érteni a számok és szimbólumok a matematikai képleteket. Mindenesetre a válogatás a következőképpen ábrázolható:
- Számos elemet (A1, A2, ..., An) adunk meg. Permutációt kell végrehajtani a sorrendben (Ak1, Ak2, ... Akn), hogy az elemek betartsák az F (Ak1) rendelési funkciókat, <= F(Ak2) <= … <= F(Akn), при этом вводят понятие "ключ сортировки".
- A sort kulcs az elem attribútuma, amelynek értéke a megrendelés.
Minden rendezési algoritmus 3 részből áll:
1) összehasonlítás. egy pár elem rendelése;
2) permutáció. lehetővé téve néhány elem cseréjét (A2 helyett A1, A1 helyett A2);
3) megfelelő rendezési algoritmus. amely összehasonlítja és átrendezi az elemeket, amíg a készlet összes elemét el nem rendelik.
Van egy meglehetősen széles körű válogatási algoritmus, amelyek mindegyike rendelkezik bizonyos jellemzőkkel és kényelmes használatra ebben az esetben. A szortírozási algoritmusok kiértékeléséhez és összehasonlításához egy sor paramétert kell megadni:
1) rendezési idő - az algoritmus sebességét jellemző fő paraméter.
2) a memória egy olyan paraméter, melyre jellemző, hogy az algoritmus további memóriát igényel a rendezett értékek ideiglenes tárolásához. Az alkalmazott memória értékelésekor az eredeti tömb tárolására használt memória mennyiségét nem veszik figyelembe.
3) stabilitás - az a paraméter, amely felelős azért, hogy a válogatás nem változtatja meg az elemek relatív helyzetét. A stabilitás helyes, ha az elemeket másodlagos kulcsokkal rendeli el, azaz A fő rendezési kulcsban nem szereplő attribútumokkal.
1a 3q 1b 1c 2z: az eredeti tömb (index, érték)
1a 1b 1c 2z 3q: stabil válogatás
1c 1b 1a 2z 3q: instabil válogatás
4) viselkedési természetesség - olyan paraméter, amely a rendezés hatékonyságát jelzi, amikor feldolgozza a már rendezett vagy részben rendezett adatokat. Úgy véljük, hogy az algoritmus természetesen viselkedik, ha figyelembe veszi a bemeneti szekvencia jellemzőjét (jobb vagy rosszabb).
Valamennyi végrehajtható rendezési algoritmus két fő osztályra osztható:
1) belső válogatás. a belső rendezési algoritmusok határozzák meg a számítástechnikai eszköz működési memóriájában található elemek megrendelését. Feltételezzük, hogy bármikor hozzáférhet a rendezett elem bármely eleméhez. Belső rendezést használ minden esetben, kivéve az egyablakos olvasást és a rendezett adatok írását.
2) külső válogatás. az adatszekvenálás során történő szétválogatás külső adathordozókat használ. Külső rendezés lehetővé teszi nagy mennyiségű adat feldolgozását, amely nem illeszkedik a RAM-ba. Ez olyan korlátozást ír elő, amely abból adódik, hogy a rendezett elemekhez való hozzáférés csak egymást követően történik, azaz. Egy tetszőleges időpontban csak az 1 aktuálisan rendezett tétel érhető el.
A belső osztályozás módszereit univerzálisan és speciálisan osztják fel. Univerzális -> egyszerű és javított. Az egyszerű és javított módszerek különböznek hatékonyságukban. A speciális módszereket úgy tervezték meg, hogy egy adott struktúra információit rendezzék.
Egyszerű módszerek a tömbök rendezésére.
A töredékek egyszerű rendszere a következők:
A buborék válogatás a legegyszerűbb rendezési algoritmus a megvalósításhoz és a megértéshez, de csak a kis tömbök esetében hatékony. Az algoritmus összetettsége n ^ 2.
Ezt az algoritmust oktatónak tekintik, és gyakorlatilag nem alkalmazzák az oktatási szakirodalomon kívül; Ehelyett hatékonyabb rendezési algoritmusokat alkalmaznak a gyakorlatban. Ugyanakkor ez az algoritmus néhány fejlettebb algoritmust, például a piramisos rendezést és a gyors válogatást alapoz meg.
Az algoritmus a rendezett tömbön átmenő ismétlésekből áll. Minden lépésnél az elemeket párhuzamosan egymással hasonlítjuk össze, és ha a páros sorrendje helytelen, az elemeket kicseréljük. A tömbön átmenő áthaladások N-1 alkalommal ismétlődnek, vagy addig, amíg a következő lépés azt mutatja, hogy a cserékre nincs szükség, ami azt jelenti, hogy a tömb sorrendben van. Minden lépésben a algoritmus a belső hurok, a következő legnagyobb tömb elem kerül a helyére végén egy tömb mellett a korábbi „legnagyobb elem”, és azt a legkisebb elemet egy pozícióval a tetején a tömb ( „lebeg” a kívánt helyzetbe, mint egy fiola vízben, így és az algoritmus neve).
A buborék szerinti rendezés nem változtatja meg az egyenlő elemek relatív pozícionálását, és nem használ további memóriát.
- Az algoritmus természetes és stabil.
- Az algoritmus magas számítási komplexitása.
A választás szerinti rendezés az összehasonlítási művelet egyik klasszikus szekvenáló módszere.
Stabil és instabil lehet.
- A szekvencia minimális (maximális) eleme megtalálható. Ehhez az első elemet összehasonlítjuk a második, az első a harmadik, és így tovább. A talált elem száma megjelölve.
- Ha az első elem indexje nem egyezik meg ezzel az elemével, akkor értékeket cserél.
- A rendezés folytatódik a tömb rendezett részében.
Összehasonlítások száma: N ^ 2
- Ez a módszer a válogatásnál előnyösebb azokban az esetekben, amikor a fájlrekordok hatalmasak, és a kulcsok kis helyet foglalnak el.
- Ez az algoritmus a legkevesebb adatmozgást eredményezi, nem pedig a kiválasztási módszert.
- A minimális elem egy átjáróban való megkeresése nem ad tájékoztatást arra vonatkozóan, hogy hova kerül a következő minimális elem.
- Nagy mennyiségű adat esetén ez a válogatás nem hatékony.
Ez az algoritmus egyszerre egy elemhez igazítja az eredményül kapott tömböt. A nagy listáknál sokkal kevésbé hatékony, mint a jobb szortírozási módszerek (qsort / hsort). Azonban ez az algoritmus a következő előnyökkel rendelkezik:
- Hatékony a kis adatkészletekre
- A legjobb esetben O (n)
- Csak O (1) memóriát igényel
Hátrányok - nagy számítási komplexitás O (n ^ 2).
Minden lépésben az egyik bemeneti adatelemet kiválasztja és beilleszti a kívánt helyzetbe a már sorba rendezett listában, amíg a bemeneti adatok kimerülnek. A következő elem kiválasztása a forrás tömbből önkényes; szinte bármilyen választási algoritmust használhatunk. Általában az elemek beillesztésre kerülnek a megjelenés sorrendjében a bemeneti tömbben.
A Merge sorting olyan rendezési algoritmus, amely bizonyos sorrendben rendezi a listákat (vagy más olyan adatokat, amelyek csak egymás után érhetők el). Először kisebb feladatokra osztják fel a feladatot, majd rekurzív hívással vagy közvetlenül, ha méretük elég kicsi. Ezután megoldásainkat egyesítjük, és megoldást találunk az eredeti probléma megoldására. Külső rendezésre használható.
A legrosszabb eset O (n log (n)).
Az osztható tömb két azonos méretű tömbre osztható. A kapott részek mindegyike ugyanazzal az algoritmussal van felosztva, amíg az egyes részek hossza 1; akkor a tömb ezen részei egybe rendeződnek és sorba rendezhetők.
- A rendezés stabil.
- Hatékony a hosszú hozzáférési idővel rendelkező adatok feldolgozása során.
- A legmegfelelőbb mód a rendezett linkek rendezésére.
- Az algoritmus olyan struktúrákra alkalmas, amelyek egymás utáni hozzáférést biztosítanak az elemekhez.
- További hely szükséges (O (1)).
- Kevesebb, mint a gyors válogatás sebessége.