Gyors rendezés Java nyelven - magyarázat

Felezési egyezmény

Ha a lista elemeinek száma páros, a lista felezése azt jelenti, hogy a lista szó szerinti első fele az első fele, a lista szó szerinti második fele pedig a második fele. A teljes lista középső (középső) eleme az első lista utolsó eleme. Ez azt jelenti, hogy a középső index hossz / 2 - 1, mivel az indexszámlálás nulláról indul. A hossz a lista elemeinek száma. Például, ha az elemek száma 8, akkor a lista első felében 4, a lista második felében szintén 4 elem található. Az jó. Mivel az indexszámlálás 0 -tól kezdődik, a középső index 3 = 8 /2 - 1.

Mi a helyzet azzal az esettel, amikor a lista vagy az allista elemeinek száma páratlan? Kezdetben a hossz még mindig 2 -vel van osztva. Megállapodás szerint ennek a felosztásnak az első felében az elemek száma a hossz / 2 + 1/2. Az indexszámlálás nulláról indul. A középső indexet a hossz / 2 - 1/2 adja meg. Ez egyezmény szerint középső kifejezés. Például, ha a lista elemeinek száma 5, akkor a középső index 2 = 5/2 - 1/2. És a lista első felében három, a második felében két elem található. A teljes lista középső eleme a harmadik elem az indexnél, 2, amely a középső index, mivel az indexszámlálás 0 -tól kezdődik.

Az ilyen módon történő osztás példa az egész számtani módszerre.

Három érték mediánja

Kérdés: Mennyi a sorozat mediánja:

C B A

Megoldás:
Rendezze a listát növekvő sorrendbe:

A B C

A középső tag, B, a medián. Ez a nagyság a másik két nagyság között.

A medián keresése a listában nem ilyen. Például egy 19 nem rendezett elemből álló listában szükség lehet az első elem, a középső és az utolsó elem mediánjára. Ez a három érték nem lehet növekvő sorrendben; és ezért figyelembe kell venni az indexeiket.

A Gyors rendezésnél a teljes lista és az allisták mediánja kötelező. A pszeudokód, amely a listában (tömbben) elosztott három érték mediánját keresi:

Az arr kifejezés tömböt jelent. Ez a kódszegmens keresi a mediánt, és némi rendezést is végez. Ez a kódrészlet egyszerűnek tűnik, de meglehetősen zavaró lehet. Tehát figyeljen a következő magyarázatra:

Az oktatóanyag rendezése olyan listát készít, ahol az első érték a legkisebb, az utolsó pedig a legnagyobb érték. Az ábécével A kisebb, mint Z.

Itt a pivot az eredményül kapott medián. Az alacsony a lista vagy az allista legalacsonyabb indexe (nem feltétlenül a legalacsonyabb érték esetén); a magas a lista vagy az allista legmagasabb indexe (nem feltétlenül a legmagasabb érték esetén), a középső pedig a hagyományos középső index (nem feltétlenül a teljes lista középső értéke).

Tehát a kapott medián a legalacsonyabb index értéke, a középső index értéke és a legmagasabb index értéke között van.

A kódban először a hagyományos középső indexet kapjuk meg. Ekkor a lista nem rendezett. A három érték összehasonlítását és némi átrendeződését növekvő sorrendben kell elvégezni. Az első if-utasítás összehasonlítja a legalacsonyabb és a középső index értékét. Ha a középső index értéke kisebb, mint a legalacsonyabbé, akkor a két érték pozíciót cserél. Ez megkezdi a rendezést, és megváltoztatja a lista vagy az allista értékeinek elrendezését. A második if-utasítás összehasonlítja a legmagasabb és a legalacsonyabb index értékét. Ha a legmagasabb index értéke kisebb, mint a legalacsonyabbé, a két érték pozíciót cserél. Ez folytatja a lista vagy az allista értékeinek némi rendezését és megváltoztatását. A harmadik if-utasítás összehasonlítja a középső és a legmagasabb index értékét. Ha a legmagasabb index értéke kisebb, mint a középső index, akkor a két érték pozíciót cserél. Némi rendezés vagy átrendezés itt is előfordulhat. Ez a harmadik if-feltétel nem olyan, mint az előző kettő.

E három csereügylet végén a szóban forgó három érték középső értéke A [magas] lesz, amelynek eredeti tartalma a kódszegmensben megváltozhatott. Vegyük például a nem rendezett sorrendet:

C B A

Már tudjuk, hogy a medián B. Ezt azonban be kell bizonyítani. A cél e három érték mediánjának megszerzése a fenti kódszegmens használatával. Az első if-utasítás összehasonlítja B-t és C-t. Ha B kisebb, mint C, akkor B és C pozícióját fel kell cserélni. B kisebb, mint C, így az új elrendezés a következő lesz:

B C A

Figyelem, a legalacsonyabb és a középső index értékei megváltoztak. A második if-állítás összehasonlítja A-t és B-t. Ha A kisebb, mint B, akkor A és B pozícióját fel kell cserélni. A kisebb, mint B, így az új elrendezés a következő lesz:

A C B

Figyelem, a legmagasabb és a legalacsonyabb index értékei megváltoztak. A harmadik if-állítás összehasonlítja C-t és B-t. Ha C kisebb, mint B, akkor C és B pozícióját fel kell cserélni. C nem kevesebb, mint B, ezért nem történik csere. Az új elrendezés az előzőekhez hasonlóan marad, vagyis:

A C B

B a medián, azaz A [magas], és ez a pivot. Tehát a pivot a lista vagy az allista legvégén születik.

A csere funkció

A gyors rendezéshez szükséges másik funkció a csere funkció. A swapping funkció kicseréli két változó értékét. A csere funkció pszeudokódja:

Itt x és y a tényleges értékekre utal, nem pedig a másolatokra.

A cikk szerinti rendezés olyan listát állít elő, ahol az első érték a legkisebb, az utolsó pedig a legnagyobb érték.

Cikk tartalma

• Gyors rendezési algoritmus
• Partíció pszeudokód
• A Gyors rendezés illusztrációja
• Java kódolás
• Következtetés

Gyors rendezési algoritmus

A rendetlen lista rendezésének szokásos módja az első két érték figyelembevétele. Ha nincsenek rendben, tegyük sorba. Ezután vegye figyelembe az első három értéket. Olvassa be az első kettőt, hogy megtudja, hol illeszkedik a harmadik érték, és illessze be megfelelően. Ezután vegye figyelembe az első négy értéket. Olvassa be az első három értéket, hogy lássa, hol illeszkedik a negyedik érték, és illessze be megfelelően. Folytassa ezt az eljárást, amíg a teljes lista rendezésre nem kerül.

Ez az eljárás, más néven brute-force sort, a számítógépes programozás nyelvén túl lassú. A Quick Sort algoritmus sokkal gyorsabb eljárást tartalmaz.

A gyorsort algoritmus lépései a következők:

1. Győződjön meg arról, hogy a rendezési listában legalább 2 számot kell rendezni.
2. Szerezzen be egy becsült központi értéket a listához, amelyet pivotnak hívnak. A medián, amint azt fentebb leírtuk, az egyik módja a pivot megszerzésének. Különböző módok jönnek előnyökkel és hátrányokkal. - Viszlát.
3. Ossza fel a listát. Ez azt jelenti, hogy helyezze el a csuklót a listában. Ily módon a bal oldalon lévő összes elem kisebb, mint a pivot érték, és a jobb oldalon lévő elemek nagyobbak vagy egyenlőek a pivot értékkel. A particionálásnak különböző módjai vannak. Minden partíciós módszer előnyökkel és hátrányokkal jár. A particionálás megosztó a megosztás és hódítás paradigmájában.
4. Ismételje meg rekurzívan az 1., 2. és 3. lépést a megjelenő új allistapároknál, amíg a teljes lista rendezésre nem kerül. Ez a megosztás és győzelem paradigmájában hódító.

A Quick Sort pszeudokód:

Partíció pszeudokód

Az oktatóanyagban használt partíció pszeudokód:

Az alábbi ábrán a Gyors rendezés ezt a kódot használja:

A Gyors rendezés illusztrációja

Tekintsük az alábbi ábécé betűkkel nem rendezett listáját (tömbjét):

Q W E R T Y U I O P

Ellenőrzés alapján a rendezett lista a következő:

E I O P Q R T U W Y

A rendezett lista most a fenti algoritmus és pszeudokódszegmensek segítségével bizonyításra kerül a nem rendezett listából:

Q W E R T Y U I O P

Az első pivotot arr [0] = Q, arr [4] = T és arr [9] = P alapján határozzák meg, és Q -ként azonosítják, és a lista jobb szélén helyezkednek el. Tehát a lista bármely pivot függvény rendezéssel a következő lesz:

P W E R T Y U I O Q

A jelenlegi pivot Q. A pivot eljárás kis rendezést hajtott végre, és P -t helyezte az első helyre. A kapott listát át kell rendezni (fel kell osztani) úgy, hogy a bal oldalon lévő összes elem kisebb értékű legyen, majd a pivot és a pivot jobb oldalán lévő elemek egyenlők vagy nagyobbak legyenek. A számítógép nem végezhet particionálást ellenőrzéssel. Tehát az indexek és a fenti partíciós algoritmus használatával.

A legalacsonyabb és a magas index most 0 és 9. Tehát a számítógép a 0 -as indexről kezd szkennelni, amíg el nem éri azt az indexet, amelynek értéke egyenlő vagy nagyobb, mint a pivot, és ideiglenesen leáll. Szintén a felső (jobb) végről, a 9 -es indexről fog lefelé menni, amíg el nem éri azt az indexet, amelynek értéke kisebb vagy egyenlő a pivot -al, és ott ideiglenesen leáll. Ez két állási helyzetet jelent. Ha i, az inkrementális index változója, az alacsony szinttől még nem egyenlő vagy nagyobb, mint a csökkenő indexváltozó, j a magasból, akkor ez a két érték felcserélődik. A jelenlegi helyzetben a szkennelés mindkét végéről W és O pontnál megállt. Így a lista a következő lesz:

P O E R T Y U I W Q

A pivot továbbra is Q. A szkennelés ellenkező irányba folytatódik és ennek megfelelően leáll. Ha i még nem egyenlő vagy nagyobb, mint j, akkor a két érték, amelynél a leolvasás mindkét végéről leállt, felcserélődik. Ezúttal a szkennelés mindkét végéről R és I -nél állt meg. Így a lista elrendezése a következő lesz:

P O E I T Y U R W Q

A pivot továbbra is Q. A szkennelés ellenkező irányba folytatódik és ennek megfelelően leáll. Ha i még nem egyenlő vagy nagyobb, mint j, akkor a két érték, amelynél a szkennelés leállt, felcserélődik. Ezúttal a szkennelés mindkét végéről megállt T -nél i -nél, I -nél pedig j -nél. én és j találkoztunk vagy kereszteztük egymást. Tehát nem lehet csere. A lista ugyanaz marad, mint:

P O E I T Y U R W Q

Ezen a ponton a Q csuklót a végső helyzetébe kell helyezni a rendezés során. Ez úgy történik, hogy az arr [i] -et arr [high] -ra cseréli, a T -t és a Q -t felcseréli.

P O E I Q Y U R W T

Ezen a ponton a teljes lista particionálása véget ért. A pivot = Q betöltötte a szerepét. Most három allista van, amelyek a következők:

P O E I Q Y U R W T

A partíció megosztás és hódítás (válogatás) a paradigmában. Q a megfelelő rendezési pozícióban van. A Q -tól balra lévő minden elem kisebb, mint a Q, és a Q -tól jobbra lévő elemek nagyobbak, mint a Q. A bal oldali lista azonban még mindig nincs rendezve; és a megfelelő lista még mindig nincs rendezve. A bal oldali és a jobb oldali lista rendezéséhez rekurzívan meg kell hívni az egész Gyors rendezés funkciót. A Gyors rendezés visszahívását folytatni kell; új allisták alakulnak ki, amíg a teljes eredeti lista teljesen rendbe nem kerül. A Gyors rendezés funkció minden egyes előhívásakor először a bal oldali allistára kell figyelni, mielőtt a megfelelő jobb allistára. Minden egyes allistához új pivot-ot kell beszerezni.

Az allistához:

P O E I

A P, O és I pivot (mediánja) meghatározott. A pivot az O. Ebben az allistában és a teljes listához kapcsolódóan az új arr [low] az arr [0], az új arr [high] pedig az utolsó arr [i-1] = arr [ 4-1] = arr [3], ahol i az előző partíció utolsó pivot indexe. A pivot () függvény meghívása után az új pivot érték, pivot = O. Ne keverje össze a pivot függvényt és a pivot értéket. A pivot függvény elvégezhet némi apró rendezést, és a pivotot az allista jobb szélére helyezheti. Ez az allista lesz,

I P E O

Ennél a sémánál a pivot mindig az allista vagy lista jobb végén ér véget a függvényhívása után. A szkennelés mindkét végétől arr [0] és arr [3] -tól kezdődik, amíg i és j találkoznak vagy keresztezik egymást. Az összehasonlítást pivot = O-val végezzük. Az első megállók P és E ponton vannak. Felcserélődnek, és az új allista a következő lesz:

I E P O

A szkennelés mindkét végéről folytatódik, és az új megállók P -nél i és E -nél j -nél vannak. Most én és j találkoztunk, vagy kereszteztük egymást. Tehát az allista ugyanaz marad, mint:

I E P O

Az allista vagy lista felosztása akkor fejeződik be, amikor a pivot végleges helyzetébe került. Tehát az arr [i] és arr [high] új értékei felcserélődnek. Vagyis P és O felcserélődnek. Az új allista a következő lesz:

I É O P

O most a végső pozícióban van a teljes listán. Forgatókönyve véget ért. Az allista jelenleg további három listára van felosztva, amelyek a következők:

I É O P

Ezen a ponton meg kell hívni az első jobb oldali lista gyorsrendezését. Azonban nem fogják hívni. Ehelyett megjegyzik és fenntartják, később hívják. Miközben a particionáló függvény utasításait végrehajtották, a függvény tetejéről a bal oldali lista gyors rendezését kell meghívni most (a pivot () meghívása után). Felhívják a listára:

I E

Az I és E mediánjának keresésével kezdődik. Itt, arr [low] = I, arr [mid] = I és arr [high] = E. Tehát a mediánt, a pivot -ot a pivot algoritmus határozza meg, mint , I. Azonban a fenti pivot pszeudokód határozza meg a pivotot E -ként. Ez a hiba azért fordul elő, mert a fenti pszeudokód három elemre vonatkozik, nem kettőre. Az alábbi megvalósításban van némi kiigazítás a kódon. Az allista lesz,

E I

A pivot függvényhívása után mindig az allista vagy lista jobb végén ér véget. A szkennelés mindkét végétől kezdődik arr [0] és arr [1] kizárólagosan, amíg i és j találkoznak vagy keresztezik egymást. Az összehasonlítást pivot = I. segítségével végezzük. Az első és egyetlen megállóhely az I és az E pontnál van: I -nél i -nél és E -nél j -nél. Most én és j találkoztunk vagy kereszteztük egymást. Tehát az allista ugyanaz marad, mint:

E I

Az allista vagy lista felosztása akkor fejeződik be, amikor a pivot végleges helyzetébe került. Tehát az arr [i] és arr [high] új értékei felcserélődnek. Itt előfordul, hogy arr [i] = I és arr [high] = I. Tehát ugyanazt az értéket felcseréli önmagával. Az új allista a következő lesz:

E I

A végleges állásponton vagyok a teljes listán. Forgatókönyve véget ért. Az allista most további két listára van felosztva, amelyek:

E I

Most a pivot -ok Q, O és I. A pivotsok végső pozíciójukon végződnek. Egyetlen elem allistája, mint például a fenti P, szintén a végső helyén ér véget.

Ezen a ponton az első bal oldali allista teljesen rendezett. És a válogatási eljárás most itt van:

E I O P Q Y U R W T

Az első jobb oldali allista:

Y U R W T

még rendezni kell.

Az első jobboldali allista meghódítása
Ne feledje, hogy a gyors rendezési hívást az első jobb oldali allistára feljegyezték és lefoglalták a végrehajtás helyett. Ezen a ponton végrehajtják. És így az új arr [low] = arr [5] = arr [QPivotIndex+1], and the new arr [high] marad arr [9]. Az első bal oldali allistához hasonló tevékenységek itt is megtörténnek. És ez az első jobb oldali allista a következőképpen van rendezve:

R T U W Y

És az eredeti rendezési lista a következőképpen lett rendezve:

E I O P Q R T U W Y

Java kódolás

Az algoritmus Java -ba helyezése csupán annyit tesz, hogy a fenti pszeudokódszegmenseket Java osztályba soroljuk. Ne felejtse el, hogy az osztályban kell lennie egy main () metódusnak, amely meghívja a quicksort () függvényt a nem rendezett tömbhöz.

A pivot () módszer

A pivot értéket visszaadó Java pivot () metódusnak a következőnek kell lennie:

A csere () módszer

A swap () metódusnak a következőnek kell lennie:

A quicksort () módszer

A quicksort () metódusnak a következőnek kell lennie:

A partíció () módszer

A partition () metódusnak a következőnek kell lennie:

A fő () módszer

A fő () módszer lehet:

A fenti módszerek mindegyike egy osztályba sorolható.

Következtetés

A Quick Sort egy osztó és hódító paradigmát használó rendezési algoritmus. Úgy kezdődik, hogy egy nem rendezett listát két vagy három allistára oszt. Ebben az oktatóanyagban a Gyors rendezés egy listát három allistára osztott: bal oldali listára, egyetlen elem középső listájára és jobb oldali allistára. A Gyors rendezésben való hódítás egy lista vagy allista felosztása egy rendezés során, egy pivot érték használatával. Ez az oktatóanyag elmagyarázta a Gyors rendezés egyik megvalósítását a Java számítógépes nyelvén.

A szerzőről

Chrysanthus Forcha

A matematika integrációjának felfedezője az első elvekből és a kapcsolódó sorozatokból. Mesterképzés műszaki oktatásban, elektronika és számítógépes szoftverek szakterülete. BSc Elektronika. Számítástechnika és telekommunikáció mester szintű ismeretekkel és tapasztalatokkal is rendelkezem. A 20 000 író közül én voltam a 37. legjobb író a devarticles.com -on. Több mint 10 éve dolgozom ezeken a területeken.

KAPCSOLÓDÓ LINUX Tippek

• A karakterláncok összehasonlítása a Java -ban
• A HashMap használata a Java -ban
• Gyors rendezés Java nyelven - magyarázat
• Bináris fa előrendelési bejárás Java nyelven
• Rendezés egyesítése Java Explainedben
• A szkenner használata Java -ban
• Java írás fájlba