Rychlé řazení v Javě vysvětleno

Konvence na polovinu

Když je počet prvků v seznamu sudý, půlení seznamu na polovinu znamená doslovnou první polovinu seznamu první polovinu a doslovnou druhou polovinu seznamu druhou polovinu. Střední (střední) prvek celého seznamu je posledním prvkem prvního seznamu. To znamená, že střední index je délka / 2 - 1, protože počítání indexu začíná od nuly. Délka je počet prvků v seznamu. Pokud je například počet prvků 8, pak první polovina seznamu má 4 prvky a druhá polovina seznamu má také 4 prvky. To je v pořádku. Protože počítání indexů začíná od 0, střední index je 3 = 8/2 - 1.

A co ten případ, když je počet prvků v seznamu nebo v pod-seznamu lichý? Na začátku je délka stále dělena číslem 2. Podle konvencí je počet prvků v první polovině tohoto dělení délka / 2 + 1/2. Počítání indexů začíná od nuly. Střední index je dán délkou / 2 - 1/2. To je konvencí považováno za střednědobý termín. Pokud je například počet prvků v seznamu 5, pak je střední index 2 = 5/2 - 1/2. A v první polovině seznamu jsou tři prvky a ve druhé polovině dva prvky. Prostřední prvek celého seznamu je třetí prvek v indexu 2, což je prostřední index, protože počítání indexů začíná od 0.

Dělení tímto způsobem je příkladem celočíselné aritmetiky.

Medián tří hodnot

Otázka: Jaký je medián sekvence:

C B A

Řešení:
Uspořádejte seznam vzestupně:

A B C

Středový termín, B, je medián. Je to velikost, která leží mezi dalšími dvěma magnitudami.

Hledání mediánu v seznamu není takové. Například v seznamu 19 netříděných prvků může být vyžadován medián pro první prvek, prostřední prvek a poslední prvek. Tyto tři hodnoty nemusí být ve vzestupném pořadí; a tak je třeba vzít v úvahu jejich indexy.

Při rychlém třídění je vyžadován medián celého seznamu a dílčích seznamů. Pseudokód, který má hledat medián tří hodnot rozmístěných v seznamu (poli), je:

Termín arr znamená pole. Tento segment kódu hledá medián a také provádí určité třídění. Tento segment kódu vypadá jednoduše, ale může být docela matoucí. Věnujte tedy pozornost následujícímu vysvětlení:

Třídění v tomto kurzu vytvoří seznam, kde první hodnota je nejmenší hodnota a poslední hodnota je největší hodnota. U abecedy je A menší než Z.

Zde je pivot výsledným mediánem. Low je nejnižší index seznamu nebo dílčího seznamu (ne nutně pro nejnižší hodnotu); high je nejvyšší index seznamu nebo dílčího seznamu (ne nutně pro nejvyšší hodnotu) a middle je konvenční střední index (ne nutně pro střední hodnotu celého seznamu).

Medián, který se má získat, je tedy mezi hodnotou nejnižšího indexu, hodnotou středního indexu a hodnotou nejvyššího indexu.

V kódu je nejprve získán konvenční střední index. Na tomto začátku je seznam netříděný. Porovnání a určité přeskupení tří hodnot ve vzestupném pořadí má proběhnout současně. První příkaz if porovnává hodnotu pro nejnižší index a pro střední index. Pokud je střední index nižší než nejnižší index, pak obě hodnoty prohodí pozice. Tím se zahájí třídění a změní se uspořádání hodnot v seznamu nebo v dílčím seznamu. Druhý příkaz if porovnává hodnotu pro nejvyšší index a nejnižší index. Pokud je nejvyšší index nižší než nejnižší index, obě hodnoty si vymění pozice. To provádí určité třídění a změnu uspořádání hodnot v seznamu nebo v dílčím seznamu. Třetí příkaz if porovnává hodnotu pro střední index a nejvyšší index. Pokud je nejvyšší index nižší než střední index, obě hodnoty si vymění pozice. Může zde také dojít k nějakému třídění nebo přeskupení. Tato třetí podmínka if není jako předchozí dvě.

Na konci těchto tří swapů bude střední hodnota tří dotyčných hodnot A [vysoká], jejíž původní obsah mohl být v segmentu kódu změněn. Zvažte například netříděnou sekvenci:

C B A

Už víme, že medián je B. To by však mělo být prokázáno. Cílem je zde získat medián těchto tří hodnot pomocí výše uvedeného segmentu kódu. První příkaz if porovnává B a C. Pokud je B menší než C, pak je třeba pozice B a C prohodit. B je menší než C, takže nové uspořádání se stane:

B C A

Všimněte si, že hodnoty pro nejnižší index a střední index se změnily. Druhý příkaz if porovnává A a B. Pokud je A menší než B, pak je třeba pozice A a B prohodit. A je menší než B, takže nové uspořádání se stane:

A C B

Všimněte si, že hodnoty pro nejvyšší index a nejnižší index se změnily. Třetí příkaz if porovnává C a B. Pokud je C menší než B, pak je třeba pozice C a B prohodit. C není menší než B, takže k výměně nedochází. Nové uspořádání zůstává jako předchozí, tj.

A C B

B je medián, což je A [vysoký], a je to pivot. Pivot se tedy rodí na extrémním konci seznamu nebo dílčího seznamu.

Funkce Swapping

Další funkcí, kterou Quick Sort potřebuje, je funkce swapování. Funkce swapování vyměňuje hodnoty dvou proměnných. Pseudokód pro funkci výměny je:

Zde x a y odkazují na skutečné hodnoty a ne na kopie.

Třídění v tomto článku vytvoří seznam, kde první hodnota je nejmenší hodnota a poslední hodnota je největší hodnota.

Obsah článku

• Algoritmus rychlého řazení
• Rozdělovací pseudokód
• Ilustrace rychlého řazení
• Java kódování
• Závěr

Algoritmus rychlého řazení

Normální způsob řazení netříděného seznamu je vzít v úvahu první dvě hodnoty. Pokud nejsou v pořádku, dejte je do pořádku. Dále zvažte první tři hodnoty. Naskenujte první dva, abyste zjistili, kde se třetí hodnota hodí, a vhodně ji přizpůsobte. Poté zvažte první čtyři hodnoty. Naskenujte první tři hodnoty, abyste zjistili, kam zapadá čtvrtá hodnota, a vhodně ji přizpůsobte. Pokračujte v tomto postupu, dokud nebude celý seznam seřazen.

Tento postup, také známý jako třídění hrubou silou, v jazyce počítačového programování, je příliš pomalý. Algoritmus Quick Sort přichází s mnohem rychlejším postupem.

Kroky pro algoritmus rychlého řazení jsou následující:

1. Ujistěte se, že v netříděném seznamu jsou alespoň 2 čísla, která lze seřadit.
2. Získejte odhadovanou centrální hodnotu pro seznam, který se nazývá pivot. Medián, jak je popsán výše, je jedním ze způsobů získání čepu. Různé způsoby přicházejí s jejich výhodami a nevýhodami. - Viz později.
3. Rozdělte seznam. To znamená, umístěte pivot do seznamu. Tak jsou všechny prvky vlevo menší než pivotní hodnota a všechny prvky vpravo jsou větší nebo rovny kontingenční hodnotě. Existují různé způsoby dělení. Každá metoda rozdělení má své výhody a nevýhody. Rozdělování je dělení v paradigmatu rozděl a panuj.
4. Kroky 1, 2 a 3 opakujte rekurzivně pro nové páry dílčích seznamů, které se objeví, dokud nebude celý seznam seřazen. To je dobývání v paradigmatu rozděl a panuj.

Pseudokód Rychlého řazení je:

Rozdělovací pseudokód

Pseudokód oddílu použitý v tomto kurzu je:

Na obrázku níže Rychlé řazení se používá tento kód:

Ilustrace rychlého řazení

Zvažte následující netříděný seznam (pole) abecedních písmen:

Q W E R T Y U I O P

Podle kontroly je seřazený seznam:

E I O P Q R T U W Y

Řazený seznam bude nyní prokázán pomocí výše uvedených segmentů algoritmů a pseudokódů z netříděného seznamu:

Q W E R T Y U I O P

První pivot je určen z arr [0] = Q, arr [4] = T a arr [9] = P a je identifikován jako Q a umístěn v krajní pravé části seznamu. Seznam s jakýmkoli tříděním kontingenční funkce se tedy stane:

P W E R T Y U I O Q

Aktuální pivot je Q. Procedura pivot provedla nějaké malé třídění a umístila P na první pozici. Výsledný seznam musí být přeuspořádán (rozdělen) tak, aby všechny prvky nalevo měly menší hodnotu, pak čep a všechny prvky napravo od čepu byly stejné nebo větší než čep. Počítač nemůže provádět rozdělení podle kontroly. Dělá to tedy pomocí indexů a výše uvedeného algoritmu oddílu.

Nízké a vysoké indexy jsou nyní 0 a 9. Počítač tedy začne skenováním z indexu 0, dokud nedosáhne indexu, jehož hodnota je stejná nebo větší než pivot a dočasně se tam zastaví. Bude také skenovat z horního (pravého) konce, index 9, sestupně, dokud nedosáhne indexu, jehož hodnota je menší nebo rovná pivotě, a dočasně se tam zastaví. To znamená dvě polohy zastavení. Pokud i, inkrementální indexová proměnná, od low ještě není stejná nebo větší než klesající indexová proměnná, j od high, pak jsou tyto dvě hodnoty prohozeny. V současné situaci se skenování z obou konců zastavilo na W a O. Seznam se tedy stává:

P O E R T Y U I W Q

Pivot je stále Q. Skenování v opačných směrech pokračuje a podle toho se zastaví. Pokud i ještě není rovno nebo větší než j, pak jsou dvě hodnoty, při kterých se skenování z obou konců zastavilo, prohozeny. Tentokrát se skenování z obou konců zastavilo na R a I. Uspořádání seznamu se tedy stává:

P O E I T Y U R W Q

Pivot je stále Q. Skenování v opačných směrech pokračuje a podle toho se zastaví. Pokud i ještě není rovno nebo větší než j, pak se vymění dvě hodnoty, při kterých se skenování zastavilo. Tentokrát se skenování z obou konců zastavilo na T pro i a já na j. já a j jsme se setkali nebo jsme křížili. K výměně tedy nemůže dojít. Seznam zůstává stejný jako:

P O E I T Y U R W Q

V tomto okamžiku musí být pivot Q umístěn v konečné poloze při třídění. To se provádí záměnou arr [i] s arr [high], záměnou T a Q. Seznam se stává:

P O E I Q Y U R W T

V tomto okamžiku rozdělení celého seznamu skončilo. Pivot = Q hraje svou roli. Nyní existují tři dílčí seznamy, které jsou:

P O E I Q Y U R W T

Oddíl je rozdělení a dobývání (třídění) v paradigmatu. Q je ve správné poloze třídění. Každý prvek nalevo od Q je menší než Q a každý prvek napravo od Q je větší než Q. Levý seznam však stále není seřazen; a správný seznam stále není seřazen. Aby bylo možné třídit levý a pravý dílčí seznam, musí být celá funkce Rychlé řazení volána rekurzivně. Toto odvolávání Rychlého třídění musí pokračovat; nové dílčí seznamy se budou vyvíjet, dokud nebude celý původní seznam zcela seřazen. Při každém vyvolání funkce Rychlé řazení se nejprve provede levý dílčí seznam, než se provede odpovídající pravý dílčí seznam. Pro každý dílčí seznam je třeba získat nový pivot.

Pro dílčí seznam:

P O E I

Je určen pivot (medián) pro P, O a I. Pivot by byl O. Pro tento dílčí seznam a vztahující se k úplnému seznamu je nové arr [nízké] arr [0] a nové arr [vysoké] je poslední arr [i-1] = arr [ 4-1] = arr [3], kde i je konečný pivot index z předchozího oddílu. Po vyvolání funkce pivot () bude nová hodnota pivot pivot = O. Nezaměňujte funkci pivot s hodnotou pivot. Funkce pivot může provést malé třídění a umístit pivot úplně vpravo od dílčího seznamu. Tento dílčí seznam se stává,

I P E O

S tímto schématem pivot vždy končí na pravém konci dílčího seznamu nebo seznamu po jeho volání funkce. Skenování z obou konců začíná od arr [0] a arr [3], dokud se i a j nesetkají nebo nekříží. Porovnání se provádí s pivot = O. První zastávky jsou na P a E. Jsou prohozeny a nový dílčí seznam se stává:

I E P O

Skenování z obou konců pokračuje a nové zastávky jsou na P pro i a na E na j. Teď jsme se setkali nebo se křížili. Dílčí seznam tedy zůstává stejný jako:

I E P O

Rozdělení dílčího seznamu nebo seznamu končí, když byl pivot umístěn do své konečné polohy. Nové hodnoty pro arr [i] a arr [high] jsou tedy prohozeny. To znamená, že P a O jsou prohozeny. Nový dílčí seznam se stává:

I E O P

O je nyní v konečné pozici pro celý seznam. Jeho role pivotky skončila. Dílčí seznam je v současné době rozdělen na další tři seznamy, kterými jsou:

I E O P

V tomto okamžiku musí být vyvoláno Rychlé řazení prvního pravého dílčího seznamu. Nebude však volána. Místo toho bude uvedeno a rezervováno, bude voláno později. Když byly prováděny příkazy funkce dělení, v horní části funkce je to nyní Rychlé řazení pro levý dílčí seznam, které musí být voláno nyní (po volání pivot ()). Bude vyvolán do seznamu:

TJ

Začne se hledáním mediánu I a E. Zde platí, že arr [low] = I, arr [mid] = I a arr [high] = E. Medián, pivot, by měl být určen pivotním algoritmem jako , I. Výše ​​uvedený pivotní pseudokód však určí pivot jako E. K této chybě zde dochází, protože výše uvedený pseudokód je určen pro tři prvky a ne pro dva. V níže uvedené implementaci dochází k určité úpravě kódu. Dílčí seznam se stává,

E já

Pivot vždy po volání funkce končí na pravém konci dílčího seznamu nebo seznamu. Skenování z obou konců začíná výhradně z arr [0] a arr [1], dokud se i a j nesetkají nebo nekříží. Porovnání se provádí s pivotem = I. První a jediné zastavení je na I a E: na I pro i a E na j. Teď jsme se setkali nebo křížili. Dílčí seznam tedy zůstává stejný jako:

E já

Rozdělení dílčího seznamu nebo seznamu končí, když byl pivot umístěn do své konečné polohy. Nové hodnoty pro arr [i] a arr [high] jsou tedy prohozeny. Zde se stává, že arr [i] = I a arr [high] = I. Stejná hodnota je tedy zaměněna sama se sebou. Nový dílčí seznam se stává:

E já

Nyní jsem v konečné pozici pro celý seznam. Jeho role pivotky skončila. Dílčí seznam je nyní rozdělen do dalších dvou seznamů, které jsou,

E já

Pivotky byly dosud Q, O a I. Pivotky končí na svých konečných pozicích. Dílčí seznam jednoho prvku, jako je P výše, také končí na své konečné pozici.

V tomto okamžiku byl první levý dílčí seznam zcela seřazen. A postup řazení je nyní na:

E I O P Q Y U R W T

První pravý dílčí seznam:

Y U R W T

ještě je třeba seřadit.

Dobytí prvního správného dílčího seznamu
Pamatujte, že volání Quick Sort pro první pravý dílčí seznam bylo zaznamenáno a rezervováno, místo aby bylo provedeno. V tomto okamžiku bude provedeno. A tak nový arr [low] = arr [5] = arr [QPivotIndex+1], a nový arr [vysoký] zůstává arr [9]. Podobný soubor aktivit, které se staly pro první levý dílčí seznam, se stane zde. A tento první pravý dílčí seznam je seřazen podle:

R T U W Y

A původní netříděný seznam byl seřazen podle:

E I O P Q R T U W Y

Java kódování

Uvedení algoritmu do Javy je pouze vložení všech výše uvedených segmentů pseudokódu do metod Java v jedné třídě. Nezapomeňte, že ve třídě musí existovat metoda main (), která bude volat funkci quicksort () s netříděným polem.

Metoda pivot ()

Metoda Java pivot (), která vrací hodnotu pivot, by měla být:

Metoda swap ()

Metoda swap () by měla být:

Metoda quicksort ()

Metoda quicksort () by měla být:

Metoda partition ()

Metoda partition () by měla být:

Metoda main ()

Metoda main () může být:

Všechny výše uvedené metody lze zařadit do jedné třídy.

Závěr

Quick Sort je algoritmus řazení, který používá paradigma rozděl a panuj. Začíná rozdělením netříděného seznamu na dva nebo tři dílčí seznamy. V tomto kurzu Quick Sort rozdělil seznam na tři dílčí seznamy: levý dílčí seznam, prostřední seznam jednoho prvku a pravý dílčí seznam. Dobývání v Rychlém třídění je rozdělení seznamu nebo dílčího seznamu při jeho třídění pomocí kontingenční hodnoty. Tento tutoriál vysvětlil jednu implementaci Rychlého třídění v počítačovém jazyce Java.

O autorovi

Chrysanthus Forcha

Objevitel integrace matematiky z Prvních principů a souvisejících sérií. Magisterský titul z technického vzdělávání se specializací na elektroniku a počítačový software. BSc elektronika. Mám také znalosti a zkušenosti na magisterské úrovni v oboru výpočetní techniky a telekomunikací. Z 20 000 spisovatelů jsem byl 37. nejlepším spisovatelem na devarticles.com. V těchto oborech pracuji více než 10 let.

SOUVISEJÍCÍ NÁZVY LINUX LINUX

• Porovnání řetězců v Javě
• Jak používat HashMap v Javě
• Rychlé řazení v Javě vysvětleno
• Přechod předobjednávky binárních stromů v Javě
• Sloučit třídění v Javě vysvětleno
• Jak používat skener v Javě
• Zápis Java do souboru