Tudd Intuíció, előadás, rendezési algoritmusok tömbök
Abstract: Az előadás tárgyalja a meghatározása és osztályozása algoritmusok válogatás tömbök, különösen a gyors rendezés, tanulmányozta a jellemző paramétereket algoritmusok bonyolultsága, válogatás, tartják a leírás és a programkód-példákat következő algoritmusok gyors válogatás: bináris kupacrendezés, összeolvad a fajta, héj sort és rendezés Hoare.
A cél az előadás. megtanulják az alapvető algoritmusokat belső rendezési és megtanulják, hogyan kell megoldani a problémát, válogatás tömbök különböző módszerekkel (bináris kupacrendezés. Shell módszer, gyors válogatás Hoare, összeolvad sort).
A rendezés egyik alapvető algoritmikus programozási feladatok. Cím kapcsolatos problémák válogatás, a téma számos tudományos vizsgálat, kifejlesztett egy sor algoritmusok.
Általában, a rendezési kell érteni, mint egy átrendezését egy előre meghatározott számú objektum egy adott sorrendben. Rendezés használt kivétel nélkül minden programozási területen, legyen az adatbázis, vagy egy matematikai programot.
Válogató algoritmus egy algoritmus rendelésére elemek sokaságát. Általában a rendezési algoritmus azt értjük rendelési algoritmus azon elemek növekvő vagy csökkenő sorrendben.
Abban az esetben, elemek azonos értékkel a rendezett sorrendben vannak elhelyezve egymás mellett bármilyen sorrendben. Azonban néha hasznos megőrizni az eredeti elemek sorrendje azonos értékeket.
A rendezési algoritmusok csak az adatok egy részét használják a sorrendet. A kulcs attribútum nevezett válogató (vagy több attribútum) által az érték, amely határozza meg a sorrendben elemek. Így írásakor a tömbök rendezési algoritmusok kell jegyezni, hogy a kulcs teljesen vagy részben egybeesik az adatokat.
Gyakorlatilag minden rendezési algoritmus három részre osztható:
- összehasonlításával meghatározzuk a megrendelt elem-pár;
- permutáció. Felcseréli elempár;
- megfelelő rendezési algoritmus, amely elvégzi az összehasonlítást és a permutáció elemek, amíg az összes halmaz elemeit rendezettek.
Rendezési algoritmusok nagy a gyakorlati használatra. Ők is ott található, ahol jön a kezelése és tárolása nagy mennyiségű információ. Néhány adatfeldolgozási feladatok könnyebb, ha az adatok előzetes megrendelésre.
Értékelése rendezési algoritmusok
További probléma nem szült ennyi különböző megoldásokat, mint a rendezés feladata. Universal, a legjobb rendezés algoritmus jelenleg nem létezik. Azonban, miután a hozzávetőleges jellemzőit a bemeneti adatokat. akkor válassza ki a módszert, amely optimálisan működik. Ehhez ismerni kell a paramétereket, amelyek értékelését tartalmazó algoritmusok.
- válogatás ideje - a legfőbb jellemző a teljesítmény az algoritmus.
- Memória - az egyik paraméter, amely jellemzi az a tény, hogy számos rendezési algoritmusok az elosztása további memória ideiglenes adatok tárolása. Értékelésekor memóriahasználat nem veszik figyelembe a hely, hogy úgy az eredeti adatsor, és független a bemeneti sorozat a költségeket, például tárolására program kódját.
- Fenntarthatóság - a paraméter, amely felelős milyen nem változtatja meg a kölcsönös helyzete azonos elemet.
- Természetes viselkedés - olyan paraméter, amely hatékonyságát jelzi a módszer a feldolgozás már rendezve van, vagy részben rendezett adatokat. Az algoritmus viselkedik természetesen, ha ez a funkció lehetővé teszi a bemeneti sorozat és jobban működik.
Osztályozása rendezési algoritmusok
Minden fajta és sokfélesége rendezési algoritmusok sorolható különböző kritériumok szerint, mint például a stabilitás a viselkedés, az alkalmazott összehasonlításokra, hogy további tárolási követelményeknek, ahogy azt a tudást az adatszerkezetet, túl az összehasonlítás működését, és mások.
A legrészletesebb pillantást a besorolás rendezési algoritmusok körét. Ebben az esetben a főbb rendelési következő csoportokra oszthatók.
- Belső válogatás - válogató algoritmus az adatok feldolgozására rendelési használ csak véletlen hozzáférésű memória (RAM) a számítógép. Azaz, a RAM elegendő tartalmazó kiválogatott adatbázisba véletlenszerű hozzáférést minden sejt és megfelelő elvégzéséhez az algoritmus. Belső válogatás használják minden esetben, kivéve a menetben olvasni az adatokat, és az egy-pass felvétel a rendezett adatokat. Attól függően, hogy az algoritmus és annak végrehajtása az adatokat lehet válogatni az ugyanazon a memórián, vagy a plusz RAM.
- Külső sort - egyfajta algoritmus, amely a külső memória adatátvitel közben válogatás. Általában a merevlemezeket. Külső válogatás célja, hogy kezeli a nagy adatok jegyzékét, amelyek nem férnek be a memóriába. Fellebbezés a különböző médiumok szab néhány további korlátozásokat az algoritmus: Hozzáférés a média végezzük következetes módon, azaz bármikor, el tudja olvasni vagy írni csak elem követi az aktuális; az adatok mennyisége nem teszi lehetővé számukra, hogy maradjon RAM.
Belső válogatás az alapja a külső rendezési algoritmusnak - az egyes részek vannak sorolva adatok tömb a memóriában, és egy speciális algoritmus összefűzve egyetlen tömbben. megrendelt gombot.
Meg kell jegyezni, hogy a belső rendezési lényegesen hatékonyabb külső, például a címet a memóriában fordított sokkal kevesebb időre a fuvarozók.
Tekintsük az alapvető algoritmusok belső válogatás, az úgynevezett haladó (logaritmikus).
Binary kupacrendezés
Ezt a válogatási eljárást által javasolt George. W. J. Williams és RW Floyd 1964-ben. Kupacrendezés valamilyen módon egy módosítása ezt a megközelítést, mivel a rendezési opciót. azzal a különbséggel, hogy a minimális (vagy maximális) elemet szelektálatlan kiválasztott szekvencia a minimális műveletek száma. Az ilyen gyors kiválasztását bizonyos a szelektálatlan szekvencia struktúra. Ez a lényege ennek a módszer abból áll, az építőiparban egy ilyen szerkezet, amely az úgynevezett egy piramis.
Piramis (válogatás fa, bináris kupac) - bináris fa rendezett levelek (a gyökér a fa - a legkisebb vagy a legnagyobb elem). Piramis is képviselteti magát egy tömbben. Az első elem a piramis a legkisebb vagy a legnagyobb, attól függ, hogy a sorrendet.
Bemutató - az, hogy létrejöjjön egy új piramis a következő algoritmus: egy új elem kerül a fa tetejére, akkor mozog ( „árnyékolt”) az úton lefelé képest gyerekek. A süllyedés befejeződött, ha az összehasonlítás eredménye a gyermek elemek megfelelnek a sorrendet.
Sorszámok xi, xi + 1. xn alkotó egy piramis. ha minden k = i, i + 1. n / 2 következő egyenlőtlenségeket xk> x2k. xk> xi (vagy xk A tömb a számok 12 10 7 5 8 7 3 egy piramis. Egy ilyen tömb kényelmesen képviselt, mint egy fa. Az első elem, amely elem együtt egy piramist. Ez a legnagyobb (vagy kisebb). Ha a tömb formájában bemutatott egy piramis. a tömb könnyű rendezni. kupacrendezés algoritmus. Előállítás 1. lépés: a tömb a piramis (ábra. 42.1. A).Kapcsolódó cikkek