Nopea lajittelu Java -selityksellä

Sopimus puolittamisesta

Kun luettelon elementtien määrä on parillinen, puolittaminen luettelossa tarkoittaa, että luettelon ensimmäinen puolisko on ensimmäinen puolisko ja kirjaimellinen toinen puoli on toinen puoli. Koko luettelon keskimmäinen (keskimmäinen) elementti on ensimmäisen luettelon viimeinen elementti. Tämä tarkoittaa, että keskimmäinen indeksi on pituus / 2 - 1, koska indeksin laskenta alkaa nollasta. Pituus on luettelon elementtien määrä. Jos esimerkiksi elementtien määrä on 8, luettelon ensimmäisellä puoliskolla on 4 elementtiä ja luettelon toisella puoliskolla on myös 4 elementtiä. Sopii hyvin. Koska indeksin laskenta alkaa nollasta, keskimmäinen indeksi on 3 = 8 / 2-1.

Entä silloin, kun luettelon tai alaluettelon elementtien määrä on pariton? Alussa pituus jaetaan edelleen kahdella. Tämän jaon ensimmäisellä puoliskolla alkioiden määrä on sopimuksen mukaan pituus / 2 + 1/2. Indeksin laskenta alkaa nollasta. Keskimmäinen indeksi annetaan pituudella / 2 - 1/2. Tätä pidetään sopimuksen mukaan keskiterminä. Jos esimerkiksi luettelon elementtien määrä on 5, keskimmäinen indeksi on 2 = 5/2 - 1/2. Ja luettelon ensimmäisellä puoliskolla on kolme ja toisella puoliskolla kaksi elementtiä. Koko luettelon keskielementti on indeksin kolmas elementti 2, joka on keskimmäinen indeksi, koska indeksin laskenta alkaa nollasta.

Jakaminen tällä tavalla on esimerkki kokonaislukuaritmeettisesta laskennasta.

Kolmen arvon mediaani

Kysymys: Mikä on sekvenssin mediaani:

C B A

Ratkaisu:
Järjestä lista nousevaan järjestykseen:

A B C

Keskitermi B on mediaani. Se on suuruus, joka on kahden muun suuruuden välissä.

Mediaanin etsiminen luettelosta ei ole sellaista. Esimerkiksi 19 lajittelemattoman elementin luettelossa ensimmäisen elementin, keskielementin ja viimeisen elementin mediaani voidaan vaatia. Nämä kolme arvoa eivät välttämättä ole nousevassa järjestyksessä; ja siksi niiden indeksit on otettava huomioon.

Pikalajittelussa koko luettelon ja alaluetteloiden mediaani vaaditaan. Pseudokoodi etsiä luettelosta (taulukosta) erotettujen kolmen arvon mediaani on:

Termi arr tarkoittaa matriisia. Tämä koodisegmentti etsii mediaania ja myös lajittelee. Tämä koodisegmentti näyttää yksinkertaiselta, mutta se voi olla melko hämmentävä. Kiinnitä siis huomiota seuraavaan selitykseen:

Tämän opetusohjelman lajittelu tuottaa luettelon, jossa ensimmäinen arvo on pienin ja viimeinen arvo on suurin. Aakkosilla A on pienempi kuin Z.

Tässä pivot on tuloksena oleva mediaani. Matala on luettelon tai alaluettelon alin indeksi (ei välttämättä alin arvo); korkea on luettelon tai alaluettelon korkein indeksi (ei välttämättä korkeimmalle arvolle) ja keskimmäinen on perinteinen keskimmäinen indeksi (ei välttämättä koko luettelon keskiarvo).

Joten saavutettava mediaani on alimman indeksin arvon, keskimmäisen indeksin arvon ja korkeimman indeksin arvon välillä.

Koodissa saadaan ensin perinteinen keskimmäinen indeksi. Tässä vaiheessa luettelo on lajittelematon. Kolmen arvon vertailu ja jonkinlainen uudelleenjärjestely nousevassa järjestyksessä tapahtuu samanaikaisesti. Ensimmäinen if-lause vertaa alimman ja keskimmäisen indeksin arvoa. Jos keskimmäisen indeksin arvo on pienempi kuin alimman indeksin, nämä kaksi arvoa vaihtavat sijainteja. Tämä aloittaa lajittelun ja muuttaa arvojen järjestystä luettelossa tai alaluettelossa. Toisessa if-lauseessa verrataan korkeimman indeksin ja alimman indeksin arvoa. Jos korkeimman indeksin indeksi on pienempi kuin alimman indeksin, molemmat arvot vaihtavat sijainteja. Tämä suorittaa jonkinlaista luettelon tai alaluettelon arvojärjestyksen lajittelua ja muuttamista. Kolmas if-lause vertaa keskimmäisen indeksin ja korkeimman indeksin arvoa. Jos korkeimman indeksin arvo on pienempi kuin keskimmäinen indeksi, molemmat arvot vaihtavat sijainteja. Myös lajittelua tai uudelleenjärjestelyä voi tapahtua täällä. Tämä kolmas if-ehto ei ole kahden edellisen kaltainen.

Näiden kolmen vaihtosopimuksen lopussa kyseisten kolmen arvon keskiarvo olisi A [korkea], jonka alkuperäinen sisältö on saatettu muuttaa koodisegmentissä. Harkitse esimerkiksi lajittelematonta järjestystä:

C B A

Tiedämme jo, että mediaani on B. Tämä on kuitenkin todistettava. Tavoitteena on saada näiden kolmen arvon mediaani käyttämällä yllä olevaa koodisegmenttiä. Ensimmäinen if-lause vertaa B: tä ja C. Jos B on pienempi kuin C, B: n ja C: n asemat on vaihdettava. B on pienempi kuin C, joten uudesta järjestelystä tulee:

B C A

Huomaa, että alimman ja keskimmäisen indeksin arvot ovat muuttuneet. Toinen if-lause vertaa A: ta ja B: tä. Jos A on pienempi kuin B, A: n ja B: n paikat on vaihdettava. A on pienempi kuin B, joten uudesta järjestelystä tulee:

A C B

Huomaa, että korkeimman ja alimman indeksin arvot ovat muuttuneet. Kolmas if-lause vertaa C: tä ja B: tä. Jos C on pienempi kuin B, C: n ja B: n asemat on vaihdettava. C on vähintään B, joten vaihtoa ei tapahdu. Uusi järjestely pysyy entisenä, eli:

A C B

B on mediaani, joka on A [korkea], ja se on nivel. Pivot syntyy siis luettelon tai alaluettelon ääripäähän.

Vaihtotoiminto

Toinen Quick Sortin tarvitsema ominaisuus on vaihtotoiminto. Vaihtotoiminto vaihtaa kahden muuttujan arvot. Vaihtotoiminnon pseudokoodi on:

Tässä x ja y tarkoittavat todellisia arvoja eivätkä kopioita.

Tämän artikkelin lajittelu tuottaa luettelon, jossa ensimmäinen arvo on pienin ja viimeinen arvo suurin.

Artikkelin sisältö

• Nopean lajittelun algoritmi
• Osion pseudokoodi
• Kuva pikalajittelusta
• Java -koodaus
• Johtopäätös

Nopean lajittelun algoritmi

Normaali tapa lajitella lajittelematon luettelo on ottaa huomioon kaksi ensimmäistä arvoa. Jos ne eivät ole kunnossa, laita ne järjestykseen. Harkitse seuraavaksi kolmea ensimmäistä arvoa. Skannaa kaksi ensimmäistä nähdäksesi, missä kolmas arvo sopii, ja sovita se asianmukaisesti. Harkitse sitten ensimmäisiä neljää arvoa. Skannaa kolme ensimmäistä arvoa nähdäksesi, missä neljäs arvo sopii ja sovi se asianmukaisesti. Jatka tätä menettelyä, kunnes koko luettelo on lajiteltu.

Tämä menettely, joka tunnetaan myös raa'an voiman lajitteluna, tietokoneohjelmoinnin kielellä, on liian hidas. Quick Sort -algoritmin mukana tulee paljon nopeampi toimenpide.

Pikavalinta -algoritmin vaiheet ovat seuraavat:

1. Varmista, että lajittelemattomassa luettelossa on vähintään kaksi lajiteltavaa numeroa.
2. Hanki luettelon arvioitu keskiarvo, jota kutsutaan pivotiksi. Mediaani, kuten edellä on kuvattu, on yksi tapa saada kääntöpiste. Eri tavoilla on etunsa ja haittansa. - Nähdä myöhemmin.
3. Osioi luettelo. Tämä tarkoittaa, että laita nivel luetteloon. Tällä tavalla kaikki vasemmalla olevat elementit ovat pienempiä kuin kääntöarvo ja kaikki oikealla olevat elementit ovat suurempia tai yhtä suuria kuin kääntöarvo. Osiointia on erilaisia. Jokaisessa osiointimenetelmässä on etunsa ja haittansa. Osiointi on jakamista jaa ja valloita -mallissa.
4. Toista vaiheita 1, 2 ja 3 rekursiivisesti uusien alaluetteloparien kohdalla, kunnes koko lista on lajiteltu. Tämä on valloittavaa jakaa ja valloita -mallissa.

Pikalajittelun pseudokoodi on:

Osion pseudokoodi

Tässä opetusohjelmassa käytetty osion pseudokoodi on:

Alla olevassa Quick Sort -kuvassa käytetään tätä koodia:

Kuva pikalajittelusta

Harkitse seuraavaa lajittelematonta aakkosjärjestysluetteloa (taulukkoa):

Q W E R T Y U I O P

Tarkastuksen mukaan lajiteltu luettelo on:

E I O P Q R T U W Y

Lajiteltu luettelo todistetaan nyt käyttämällä yllä olevaa algoritmia ja pseudokoodisegmenttejä lajittelemattomasta luettelosta:

Q W E R T Y U I O P

Ensimmäinen nivel määritetään arvosta arr [0] = Q, arr [4] = T ja arr [9] = P, ja se tunnistetaan Q: ksi ja sijoitetaan luettelon äärimmäiseen oikealle puolelle. Joten luettelosta, jossa on kaikki pivot -funktion lajittelut, tulee:

P W E R T Y U I O Q

Nykyinen nivel on Q. Kääntömenettely teki pienen lajittelun ja sijoitti P ensimmäiseen paikkaan. Tuloksena oleva luettelo on järjestettävä uudelleen (osioitu) siten, että kaikki vasemmalla olevat elementit ovat arvoltaan pienempiä, jolloin pivot ja kaikki pivotin oikealla puolella olevat elementit ovat yhtä suuria tai suurempia kuin nivel. Tietokone ei voi osioida tarkastusta. Joten se tekee indeksejä ja yllä olevaa osioalgoritmia.

Alin ja ylin indeksi ovat nyt 0 ja 9. Joten tietokone aloittaa skannauksen indeksistä 0, kunnes se saavuttaa indeksin, jonka arvo on yhtä suuri tai suurempi kuin pivot ja pysähtyy siihen väliaikaisesti. Se skannaa myös yläreunasta (indeksi 9) alaspäin, kunnes se saavuttaa indeksin, jonka arvo on pienempi tai yhtä suuri kuin kääntö, ja pysähtyy siellä väliaikaisesti. Tämä tarkoittaa kahta pysäytysasentoa. Jos i, inkrementaalinen indeksimuuttuja alhaisesta, ei ole vielä yhtä suuri tai pienempi kuin pienenevä indeksimuuttuja, j korkeasta, nämä kaksi arvoa vaihdetaan. Nykyisessä tilanteessa skannaus molemmista päistä pysähtyi kohdissa W ja O. Joten luettelosta tulee:

P O E R T Y U I W Q

Kääntö on edelleen Q. Skannaus vastakkaisiin suuntiin jatkuu ja pysähtyy vastaavasti. Jos i ei ole vielä yhtä suuri tai suurempi kuin j, kaksi arvoa, joilla skannaus molemmista päistä lopetettiin, vaihdetaan. Tällä kertaa skannaus molemmista päistä pysähtyi kohtaan R ja I. Joten luettelon järjestelystä tulee seuraava:

P O E I T Y U R W Q

Kääntö on edelleen Q. Skannaus vastakkaisiin suuntiin jatkuu ja pysähtyy vastaavasti. Jos i ei ole vielä yhtä suuri tai suurempi kuin j, skannauksen lopettaneet kaksi arvoa vaihdetaan. Tällä kertaa skannaus molemmista päistä pysähtyi kohtaan T for i ja I varten j. i ja j ovat tavanneet tai ylittäneet. Vaihtoa ei siis voi tapahtua. Lista pysyy samana kuin:

P O E I T Y U R W Q

Tässä vaiheessa nivel Q on asetettava lajittelussa lopulliseen asentoonsa. Tämä tapahtuu vaihtamalla arr [i] arvoon [high], vaihtamalla T ja Q. Lista muuttuu:

P O E I Q Y U R W T

Tässä vaiheessa koko luettelon osiointi on päättynyt. Pivot = Q on tehnyt tehtävänsä. Nyt on kolme alaluetteloa, jotka ovat:

P O E I Q Y U R W T

Osio on jako ja valloitus (lajittelu) paradigmassa. Q on oikeassa lajittelukohdassaan. Jokainen elementti Q: n vasemmalla puolella on pienempi kuin Q ja jokainen Q: n oikealla puolella oleva elementti on suurempi kuin Q. Vasemmanpuoleista luetteloa ei kuitenkaan vieläkään lajitella; ja oikeaa luetteloa ei ole vielä lajiteltu. Koko pikalajittelutoiminto on kutsuttava rekursiivisesti vasemman ja oikean alaluettelon lajittelemiseksi. Pikalajittelun palauttamista on jatkettava; uusia alaluetteloita kehitetään, kunnes koko alkuperäinen luettelo on lajiteltu kokonaan. Jokaisen Quick Sort -toiminnon kutsumisen yhteydessä vasemmanpuoleinen alaluettelo tarkastellaan ensin ennen vastaavaa oikeaa alaluetteloa. Jokaiselle alaluettelolle on hankittava uusi pivot.

Alaluettelo:

P O E I

P-, O- ja I -pivot (mediaani) määritetään. Pivotti olisi O. Tässä alaluettelossa ja koko luettelon osalta uusi arr [low] on arr [0] ja new arr [high] on viimeinen arr [i-1] = arr [ 4-1] = arr [3], missä i on edellisen osion viimeinen pivot-indeksi. Kun pivot () -funktio on kutsuttu, uusi pivot -arvo pivot = O. Älä sekoita pivot -funktion ja pivot -arvon välillä. Pivot-toiminto voi tehdä pienen lajittelun ja sijoittaa saranan alaluettelon oikealle puolelle. Tästä alaluettelosta tulee,

I P E O

Tässä mallissa pivot päättyy aina aliluettelon tai -luettelon oikeaan päähän sen funktiokutsun jälkeen. Skannaus molemmista päistä alkaa kohdasta arr [0] ja arr [3], kunnes i ja j kohtaavat tai kohtaavat. Vertailu tehdään pivot = O.Ensimmäiset pysäkit ovat kohdissa P ja E. Ne vaihdetaan, ja uudesta alaluettelosta tulee:

I E P O

Skannaus molemmista päistä jatkuu, ja uudet pysäkit ovat kohdissa P ja i ja kohdassa E j. Nyt minä ja j tapasimme tai risteimme. Joten alaluettelo pysyy samana kuin:

I E P O

Alaluettelon tai luettelon osiointi päättyy, kun pivot on asetettu lopulliseen asentoonsa. Joten uudet arvot arr [i] ja arr [high] vaihdetaan. Eli P ja O vaihdetaan. Uudesta alaluettelosta tulee:

I E O P.

O on nyt lopullisessa asemassa koko luettelon osalta. Sen rooli kääntöpisteenä on päättynyt. Alaluettelo on tällä hetkellä jaettu kolmeen muuhun luetteloon, jotka ovat:

I E O P.

Tässä vaiheessa on kutsuttava ensimmäisen oikeanpuoleisen alaluettelon Quick Sort. Sitä ei kuitenkaan kutsuta. Sen sijaan se merkitään muistiin ja varataan myöhempään soittamiseen. Osiointitoiminnon lausuntoja suoritettaessa funktion ylhäältä vasemman alaluettelon pikavalinta on kutsuttava nyt (pivot () -kutsun jälkeen). Se kutsutaan luetteloon:

Minä E.

Se alkaa etsimällä I: n ja E: n mediaani. Täällä arr [low] = I, arr [mid] = I ja arr [high] = E. Joten mediaani, pivot, pitäisi määrittää pivot -algoritmilla Kuitenkin yllä oleva pivot -pseudokoodi määrittää pivotiksi E. Tämä virhe ilmenee tässä, koska yllä oleva pseudokoodi on tarkoitettu kolmelle elementille eikä kahdelle. Alla olevassa toteutuksessa koodiin on tehty joitakin muutoksia. Alaluettelosta tulee,

E I

Pivot päättyy aina alaluettelon tai -luettelon oikeaan päähän sen funktiokutsun jälkeen. Skannaus molemmista päistä alkaa arr [0] ja arr [1] yksinomaan, kunnes i ja j kohtaavat tai kohtaavat. Vertailu tehdään pivot = I. Ensimmäiset ja ainoat pysähdykset ovat I: ssä ja E: kohdassa I (i) ja kohdassa E (j). Nyt minä ja j tapasimme tai ylitimme. Joten alaluettelo pysyy samana kuin:

E I

Alaluettelon tai luettelon osiointi päättyy, kun pivot on asetettu lopulliseen asentoonsa. Joten uudet arvot arr [i] ja arr [high] vaihdetaan. Tässä tapahtuu, että arr [i] = I ja arr [high] = I. Joten sama arvo vaihdetaan itsensä kanssa. Uudesta alaluettelosta tulee:

E I

Olen nyt lopullisessa asemassa koko luettelon osalta. Sen rooli kääntöpisteenä on päättynyt. Alaluettelo on nyt jaettu kahteen muuhun luetteloon, jotka ovat

E I

Nyt pivot ovat olleet Q, O ja I. Pivots päättyy lopulliseen asentoonsa. Yksittäisen elementin alaluettelo, kuten edellä oleva P, päättyy myös lopulliseen paikkaansa.

Tässä vaiheessa ensimmäinen vasen alaluettelo on lajiteltu kokonaan. Ja lajittelumenettely on nyt osoitteessa:

E I O P Q Y U R W T

Ensimmäinen oikea alaluettelo:

Y U R W T

pitää vielä lajitella.

Ensimmäisen oikean alaluettelon valloittaminen
Muista, että ensimmäisen oikeanpuoleisen alaluettelon Quick Sort -puhelu on merkitty muistiin ja varattu sen suorittamisen sijasta. Tässä vaiheessa se toteutetaan. Ja niin, uusi arr [low] = arr [5] = arr [QPivotIndex+1], ja uusi arr [high] pysyy arr [9]. Samanlaisia ​​toimintoja, jotka tapahtuivat ensimmäisessä vasemmassa alaluettelossa, tapahtuu täällä. Ja tämä ensimmäinen oikea alaluettelo on lajiteltu seuraavasti:

R T U W Y

Ja alkuperäinen lajittelematon luettelo on lajiteltu seuraavasti:

E I O P Q R T U W Y

Java -koodaus

Algoritmin laittaminen Javaan tarkoittaa vain kaikkien edellä mainittujen pseudokoodisegmenttien yhdistämistä Java -menetelmiin yhdessä luokassa. Älä unohda, että luokassa on oltava main () -menetelmä, joka kutsuu quicksort () -funktiota lajittelemattoman taulukon kanssa.

Pivot () -menetelmä

Java pivot () -menetelmän, joka palauttaa arvon pivot, pitäisi olla:

Vaihto () -menetelmä

Vaihtomenetelmän () tulisi olla:

Quicksort () -menetelmä

Quicksort () -menetelmän tulisi olla:

Osio () -menetelmä

Partition () -menetelmän tulisi olla:

Päämenetelmä ()

Päämenetelmä () voi olla:

Kaikki edellä mainitut menetelmät voidaan yhdistää yhteen luokkaan.

Johtopäätös

Nopea lajittelu on lajittelualgoritmi, joka käyttää jaa ja valloita -mallia. Se alkaa jakamalla lajittelematon luettelo kahteen tai kolmeen alaluetteloon. Tässä opetusohjelmassa Quick Sort on jakanut luettelon kolmeen alaluetteloon: vasen alaluettelo, yksittäisen elementin keskilista ja oikea alaluettelo. Pikalajittelussa valloittaminen on luettelon tai alaluettelon jakaminen lajittelun aikana pivot-arvon avulla. Tämä opetusohjelma on selittänyt yhden Quick Sortin toteutuksen Java -tietokoneen kielellä.

Kirjailijasta

Chrysanthus Forcha

Matematiikan integroinnin löytäjä ensimmäisistä periaatteista ja niihin liittyvistä sarjoista. Tekniikan maisterin tutkinto, joka on erikoistunut elektroniikkaan ja tietokoneohjelmistoihin. BSc Elektroniikka. Minulla on myös tietoa ja kokemusta tietojenkäsittelyn ja tietoliikenteen maisteritasolla. Olin 20 000 kirjoittajan joukossa 37. paras kirjoittaja devarticles.com -sivustolla. Olen työskennellyt näillä aloilla yli 10 vuotta.

LIITTYVÄT LINUX -VINKKIPOSTIT

• Javan merkkijonojen vertailu
• HashMapin käyttäminen Javassa
• Nopea lajittelu Java -selityksellä
• Binaaripuun ennakkotilauksen läpikäynti Javassa
• Yhdistä lajittelu Java -selityksissä
• Skannerin käyttäminen Javassa
• Java kirjoittaa tiedostoon