Kiire sortimine Java keeles - seletatud

Konventsioon pooleks

Kui loendi elementide arv on paaris, tähendab loendi poole võrra vähendamine nimekirja sõnasõnalist esimest poolt esimene pool ja nimekirja sõnasõnaline teine ​​pool. Kogu loendi keskmine (keskmine) element on esimese loendi viimane element. See tähendab, et keskmine indeks on pikkus / 2 - 1, kuna indeksite loendamine algab nullist. Pikkus on loendis olevate elementide arv. Näiteks kui elementide arv on 8, siis loendi esimeses pooles on 4 ja loendi teises pooles ka 4 elementi. See on hea. Kuna indeksite loendamine algab nullist, on keskmine indeks 3 = 8 /2 - 1.

Mis saab juhtumist, kui loendi või alamloendi elementide arv on paaritu? Alguses jagatakse pikkus ikkagi kahega. Kokkuleppe kohaselt on selle jaotuse esimese poole elementide arv pikkus / 2 + 1/2. Indeksite lugemine algab nullist. Keskmise indeksi annab pikkus / 2 - 1/2. Kokkuleppel peetakse seda keskmiseks terminiks. Näiteks kui loendi elementide arv on 5, siis keskmine indeks on 2 = 5/2 - 1/2. Ja loendi esimeses pooles on kolm ja teises pooles kaks elementi. Kogu loendi keskmine element on indeksi 2 kolmas element, mis on keskmine indeks, kuna indeksite loendamine algab nullist.

Sel viisil jagamine on näide täisarvu aritmeetikast.

Kolme väärtuse mediaan

Küsimus: Mis on jada mediaan:

C B A

Lahendus:
Korraldage loend kasvavas järjekorras:

A B C

Keskmine termin B on mediaan. See suurusjärk jääb kahe teise suurusjärgu vahele.

Loendist mediaani otsimine pole selline. Näiteks 19 sortimata elemendi loendis võib nõuda esimese, keskmise ja viimase elemendi mediaani. Need kolm väärtust ei pruugi olla kasvavas järjekorras; seega tuleb nende indekseid arvesse võtta.

Kiire sortimise korral on nõutav kogu loendi ja alamloendite mediaan. Loendis (massiivis) jaotatud kolme väärtuse mediaani otsimiseks on pseudokood järgmine:

Mõiste arr tähendab massiivi. See koodisegment otsib mediaani ja ka sorteerib. See koodisegment tundub lihtne, kuid võib olla üsna segane. Niisiis, pöörake tähelepanu järgmisele selgitusele:

Selle õpetuse sortimine loob loendi, kus esimene väärtus on väikseim ja viimane väärtus on suurim. Tähestiku korral on A väiksem kui Z.

Siin on pöördpunkt tulemuseks olev mediaan. Madal on loendi või alamloendi madalaim indeks (mitte tingimata madalaima väärtuse korral); kõrge on loendi või alamloendi kõrgeim indeks (mitte tingimata kõrgeima väärtuse puhul) ja keskmine on tavaline keskmine indeks (mitte tingimata kogu loendi keskmise väärtuse jaoks).

Seega on saadaolev mediaan madalaima indeksi väärtuse, keskmise indeksi väärtuse ja kõrgeima indeksi väärtuse vahel.

Koodis saadakse kõigepealt tavaline keskmine indeks. Selle alguses on nimekiri sortimata. Kolme väärtuse võrdlemine ja mõningane ümberkorraldamine kasvavas järjekorras toimub samal ajal. Esimene if-lause võrdleb madalaima ja keskmise indeksi väärtust. Kui keskmise indeksi väärtus on väiksem kui madalaima indeksi oma, vahetavad need kaks väärtust positsioone. See alustab sortimist ja muudab väärtuste paigutust loendis või alamloendis. Teine if-lause võrdleb kõrgeima ja madalaima indeksi väärtust. Kui kõrgeima indeksi indeks on väiksem kui madalaima indeksi oma, vahetavad need kaks väärtust positsioone. See toob kaasa loendi või alamloendi väärtuste paigutuse teatud sorteerimise ja muutmise. Kolmas if-lause võrdleb keskmise indeksi ja kõrgeima indeksi väärtust. Kui kõrgeima indeksi indeks on väiksem kui keskmine indeks, vahetavad need kaks väärtust positsioone. Siin võib esineda ka sorteerimist või ümberkorraldamist. See kolmas if-tingimus ei ole nagu kaks eelmist.

Nende kolme vahetustehingu lõpus oleks kolme kõnealuse väärtuse keskmine väärtus A [kõrge], mille algset sisu võidi koodisegmendis muuta. Näiteks kaaluge sortimata järjestust:

C B A

Me juba teame, et mediaan on B. Seda tuleks siiski tõestada. Eesmärk on saada ülaltoodud koodisegmendi abil nende kolme väärtuse mediaan. Esimene if-väide võrdleb punkte B ja C. Kui B on väiksem kui C, tuleb B ja C positsioonid vahetada. B on väiksem kui C, seega saab uus paigutus:

B C A

Pange tähele, et madalaima ja keskmise indeksi väärtused on muutunud. Teine if-lause võrdleb punkte A ja B. Kui A on väiksem kui B, tuleb A ja B positsioonid vahetada. A on väiksem kui B, seega saab uus paigutus:

A C B

Pange tähele, et kõrgeima ja madalaima indeksi väärtused on muutunud. Kolmas if-lause võrdleb C ja B. Kui C on väiksem kui B, tuleb C ja B positsioonid vahetada. C ei ole väiksem kui B, seega vahetust ei toimu. Uus korraldus jääb samaks, st:

A C B

B on mediaan, mis on A [kõrge] ja see on pöördepunkt. Niisiis, pöördpunkt sünnib loendi või alamloendi äärmises otsas.

Vahetusfunktsioon

Teine funktsioon, mida Quick Sort vajab, on vahetusfunktsioon. Vahetusfunktsioon vahetab kahe muutuja väärtusi. Vahetusfunktsiooni pseudokood on järgmine:

Siin tähistavad x ja y tegelikke väärtusi, mitte koopiaid.

Selle artikli sortimine loob loendi, kus esimene väärtus on väikseim ja viimane väärtus on suurim.

Artikli sisu

• Kiire sortimise algoritm
• Partitsiooni pseudokood
• Kiire sortimise illustratsioon
• Java kodeerimine
• Järeldus

Kiire sortimise algoritm

Sorteerimata loendi sorteerimise tavaline viis on kahe esimese väärtuse arvestamine. Kui need pole korras, tehke need korda. Järgmisena kaaluge kolme esimest väärtust. Skaneerige kaks esimest, et näha, kuhu kolmas väärtus sobib, ja sobitage see sobivalt. Seejärel kaaluge nelja esimest väärtust. Skaneerige kolm esimest väärtust, et näha, kuhu neljas väärtus sobib, ja sobitage see sobivalt. Jätkake seda protseduuri, kuni kogu loend on sorteeritud.

See protseduur, mida arvutiprogrammide keeles räägitakse ka toore jõuga, on liiga aeglane. Quick Sort algoritm on varustatud palju kiirema protseduuriga.

Kiirvaliku algoritmi sammud on järgmised:

1. Veenduge, et sorteerimata loendis oleks vähemalt 2 sorteeritavat numbrit.
2. Hankige loendi hinnanguline keskväärtus, mida nimetatakse pöördeks. Keskmine, nagu eespool kirjeldatud, on üks pöördvõti saamiseks. Erinevatel viisidel on oma eelised ja puudused. - Vaata hiljem.
3. Eraldage loend. See tähendab, et asetage pöördpunkt loendisse. Sel viisil on kõik vasakpoolsed elemendid pöördväärtusest väiksemad ja parempoolsed elemendid on pöördväärtusest suuremad või sellega võrdsed. Eraldamiseks on erinevaid viise. Igal jaotamismeetodil on oma eelised ja puudused. Jaotamine on jagamise ja vallutamise paradigmas jagunemine.
4. Korrake samme 1, 2 ja 3 rekursiivselt uute alamloendipaaride puhul, mis ilmuvad, kuni kogu loend on sorteeritud. See on vallutamine jaga ja valluta paradigmas.

Kiire sortimise pseudokood on:

Partitsiooni pseudokood

Selles õpetuses kasutatav partitsiooni pseudokood on järgmine:

Kiirsortimise alloleval joonisel kasutatakse seda koodi:

Kiire sortimise illustratsioon

Mõelge järgmisele sorteerimata tähestikuliste tähtede loendile (massiivile):

Q W E R T Y U I O P

Kontrollimise järgi on sorteeritud loend järgmine:

E I O P Q R T U W Y

Sorteeritud loend on nüüd tõestatud, kasutades ülaltoodud algoritmi ja pseudokoodi segmente sorteerimata loendist:

Q W E R T Y U I O P

Esimene pöördeväärtus määratakse asukohast arr [0] = Q, arr [4] = T ja arr [9] = P ning see identifitseeritakse kui Q ja paigutatakse loendi paremasse serva. Niisiis muutub kõigi pöördfunktsioonide sorteerimisega loend järgmiselt:

P W E R T Y U I O Q

Praegune liigend on Q. Pöördprotseduur tegi väikese sorteerimise ja asetas P esimesse kohta. Saadud loend tuleb ümber paigutada (osadeks jaotada) nii, et kõik vasakpoolsed elemendid on väiksema väärtusega, siis on liigend ja kõik pöördel paremal asuvad elemendid võrdsed või suuremad. Arvuti ei saa kontrollimisel eraldada. Niisiis, see toimub indeksite ja ülaltoodud partitsioonialgoritmi abil.

Madalad ja kõrged indeksid on praegu 0 ja 9. Niisiis, arvuti skannib indeksist 0, kuni jõuab indeksini, mille väärtus on võrdne või suurem kui pöördeosa ja peatub seal ajutiselt. See skaneerib ka ülemisest (paremast) otsast, indeksist 9 allapoole, kuni jõuab indeksini, mille väärtus on väiksem või võrdne pöördega, ja peatub seal ajutiselt. See tähendab kahte peatumisasendit. Kui i, kasvav indeksi muutuja madalalt, ei ole veel võrdne või suurem kui vähenev indeksi muutuja, j kõrgest, siis need kaks väärtust vahetatakse. Praeguses olukorras peatus skannimine mõlemast otsast punktides W ja O. Nii et loend saab järgmine:

P O E R T Y U I W Q

Pöörd on endiselt Q. Vastassuundades skaneerimine jätkub ja peatub vastavalt. Kui i pole veel võrdne või suurem kui j, vahetatakse kaks väärtust, mille juures skaneerimine mõlemast otsast peatati. Seekord peatus skannimine mõlemast otsast punktides R ja I. Niisiis muutub loendi paigutus järgmiselt:

P O E I T Y U R W Q

Pöörd on endiselt Q. Vastassuundades skaneerimine jätkub ja peatub vastavalt. Kui i pole veel võrdne või suurem kui j, vahetatakse kaks väärtust, mille juures skannimine peatati. Seekord peatus skaneerimine mõlemast otsast T jaoks i ja I j jaoks. i ja j on kohtunud või ületanud. Niisiis, vahetust ei saa olla. Nimekiri jääb samaks:

P O E I T Y U R W Q

Siinkohal tuleb telg Q paigutada sorteerimisel lõppasendisse. Selleks vahetage arr [i] arr [high] -ga, vahetades T ja Q. Loend muutub järgmiselt:

P O E I Q Y U R W T

Siinkohal on kogu loendi jaotamine lõppenud. Pivot = Q on oma rolli mänginud. Nüüd on kolm alamloendit, mis on järgmised:

P O E I Q Y U R W T

Eraldamine on paradigmas jagamine ja vallutamine (sorteerimine). Q on õiges sorteerimisasendis. Iga Q -st vasakul olev element on väiksem kui Q ja iga Q -st paremal olev element on suurem kui Q. Kuid vasakpoolne loend pole endiselt sorteeritud; ja õiget nimekirja pole ikka veel sorteeritud. Vasaku alamloendi ja parema alamloendi sortimiseks tuleb rekursiivselt välja kutsuda kogu kiirsortimise funktsioon. Seda Quick Sorti tagasikutsumist tuleb jätkata; uued alamloendid arenevad seni, kuni kogu algne loend on täielikult sorteeritud. Funktsiooni Kiirsortimine iga tagasikutsumise korral vaadatakse vasakpoolset alamloendit enne vastavat paremat alamloendit. Iga alamloendi jaoks tuleb hankida uus pöördpunkt.

Alamloendi jaoks:

P O E I

P, O ja I telg (mediaan) on määratud. Pöördpunkt oleks O. Selle alamloendi ja täieliku loendi osas on uus arr [madal] arr [0] ja uus arr [kõrge] on viimane arr [i-1] = arr [ 4-1] = arr [3], kus i on eelmise sektsiooni viimane pöördeindeks. Pärast funktsiooni pivot () kutsumist kuvatakse uus pöördväärtus, pivot = O. Ärge ajage pöörlemisfunktsiooni ja pöördväärtust segamini. Pöördfunktsioon võib teha väikese sorteerimise ja paigutada pöörde alamloendi paremasse serva. Sellest alamloendist saab,

I P E O

Selle skeemi korral lõpeb pöördliik alati pärast funktsioonikutset alamloendi või loendi paremas otsas. Skaneerimine mõlemast otsast algab asukohast arr [0] ja arr [3], kuni i ja j kohtuvad või ristuvad. Võrdlus toimub pivot = O. Esimesed peatused on punktides P ja E. Need on vahetatud ja uueks alamloendiks saab:

I E P O

Mõlemast otsast skaneerimine jätkub ja uued peatused on P -i ja J -i juures. Nüüd olen mina ja j kohtunud või ristunud. Seega jääb alamloend samaks:

I E P O

Alamnimekirja või -loendi jagamine lõpeb, kui pöördliik on oma lõplikule positsioonile seatud. Niisiis, arr [i] ja arr [high] uued väärtused vahetatakse. See tähendab, et P ja O vahetatakse. Uus alamloend muutub:

I E O P.

O on nüüd kogu nimekirja lõplikul positsioonil. Selle roll pöördena on lõppenud. Alamloend on praegu jagatud veel kolmeks loendiks, mis on järgmised:

I E O P.

Siinkohal tuleb kutsuda esimese parema alamloendi Quick Sort. Seda siiski ei kutsuta. Selle asemel märgitakse see ja reserveeritakse, et hiljem helistada. Partitsioonifunktsiooni avalduste täitmise ajal tuleb funktsiooni ülaosast nüüd (pärast pivot () kutsumist kutsuda vasakpoolse alamloendi kiire sortimine). Seda kutsutakse nimekirja:

Ma E

See algab I ja E mediaani otsimisega. Siin, arr [low] = I, arr [mid] = I ja arr [high] = E. Seega tuleks mediaan, pivot, määrata kindlaks pöördalgoritmi abil , I. Kuid ülaltoodud pivot -pseudokood määrab pöörde kui E. See viga ilmneb siin, kuna ülaltoodud pseudokood on mõeldud kolmele elemendile, mitte kahele. Allpool toodud rakenduses on koodi veidi kohandatud. Alamloendist saab,

E I

Pivot lõpeb alati alamloendi või loendi paremas otsas pärast selle funktsioonikutset. Mõlemast otsast skannimine algab piirkonnast arr [0] ja arr [1] kuni i ja j kohtumiseni või ristumiseni. Võrdlus toimub pivot = I. Esimesed ja ainsad peatused on punktides I ja E: I juures i ja punktis E j. Nüüd olen mina ja j kohtunud või ületanud. Seega jääb alamloend samaks:

E I

Alamnimekirja või -loendi jagamine lõpeb, kui pöördliik on oma lõplikule positsioonile seatud. Niisiis, arr [i] ja arr [high] uued väärtused vahetatakse. Siin juhtub, et arr [i] = I ja arr [high] = I. Seega vahetatakse sama väärtus endaga. Uus alamloend muutub:

E I

Olen nüüd kogu nimekirja lõplikul positsioonil. Selle roll pöördena on lõppenud. Alamloend on nüüd jagatud veel kaheks loendiks, mis on

E I

Nüüd on pöördepunktid olnud Q, O ja I. Pivots lõpeb oma viimasel positsioonil. Üksiku elemendi alamloend, näiteks ülaltoodud P, lõpeb samuti oma lõpppositsiooniga.

Siinkohal on esimene vasakpoolne alamloend täielikult sorteeritud. Ja sortimisprotseduur on nüüd järgmine:

E I O P Q Y U R W T

Esimene parem alamloend:

Y U R W T

tuleb veel sorteerida.

Esimese parema alamnimekirja vallutamine
Pidage meeles, et esimese parema alamloendi kiire sorteerimise üleskutse märgiti ja reserveeriti selle asemel, et seda täita. Sel hetkel see täidetakse. Ja nii, uus arr [madal] = arr [5] = arr [QPivotIndex+1] ja uus arr [kõrge] jääb arr [9]. Sarnane tegevuste kogum, mis juhtus esimese vasakpoolse alamloendi puhul, toimub ka siin. Ja see esimene parem alamloend on sorteeritud järgmiselt:

R T U W Y

Ja sorteerimata esialgne loend on sorteeritud järgmiselt:

E I O P Q R T U W Y

Java kodeerimine

Algoritmi Java -sse paigutamine on lihtsalt kõigi ülaltoodud pseudokoodi segmentide paigutamine Java -meetoditesse ühte klassi. Ärge unustage, et klassis peab olema peamine () meetod, mis kutsub sortimata massiiviga üles funktsiooni quicksort ().

Pivot () meetod

Java pivot () meetod, mis tagastab väärtuse pivot, peaks olema järgmine:

Vahetusmeetod ()

Vahetusmeetod () peaks olema järgmine:

Kiirvaliku () meetod

Quicksort () meetod peaks olema järgmine:

Partitsioon () meetod

Partition () meetod peaks olema järgmine:

Peamine () meetod

Peamine () meetod võib olla:

Kõik ülaltoodud meetodid saab koondada ühte klassi.

Järeldus

Quick Sort on sortimisalgoritm, mis kasutab jaga-ja-valluta paradigmat. See algab sortimata loendi jagamisega kaheks või kolmeks alamloendiks. Selles õpetuses on Quick Sort jaganud loendi kolmeks alamloendiks: vasakpoolne alamloend, üksiku elemendi keskmine loend ja parem alamloend. Kiire sortimise vallutamine on loendi või alamloendi jagamine selle sortimise ajal pöördväärtuse abil. Selles õpetuses on selgitatud ühte Quick Sorti rakendust Java arvutikeeles.

Autori kohta

Chrysanthus Forcha

Matemaatika integreerimise avastaja esimestest põhimõtetest ja nendega seotud seeriatest. Tehnikahariduse magistrikraad, mis on spetsialiseerunud elektroonikale ja arvutitarkvarale. BSc elektroonika. Mul on ka teadmised ja kogemused magistriõppes arvutite ja telekommunikatsiooni alal. 20 000 kirjaniku hulgast olin devarticles.com 37. parim kirjanik. Olen nendes valdkondades töötanud üle 10 aasta.

SEOTUD LINUX VIHJEPOSTITUSED

• Stringide võrdlus Java -s
• HashMapi kasutamine Java -s
• Kiire sortimine Java keeles - seletatud
• Binaarpuu ettetellimise läbisõit Java -s
• Ühenda Sorteeri Java seletusega
• Kuidas kasutada skannerit Java -s
• Java kirjutab faili