Greitas rūšiavimas „Java“ paaiškinta

Perpus suvažiavimas

Kai sąrašo elementų skaičius yra lygus, perpus sumažėjus sąrašui, pažodinė pirmoji sąrašo pusė yra pirmoji pusė, o pažodinė sąrašo pusė - antroji. Vidutinis (vidurinis) viso sąrašo elementas yra paskutinis pirmojo sąrašo elementas. Tai reiškia, kad vidurinis indeksas yra ilgis / 2 - 1, nes indeksas pradedamas skaičiuoti nuo nulio. Ilgis yra elementų skaičius sąraše. Pavyzdžiui, jei elementų skaičius yra 8, tada pirmoje sąrašo pusėje yra 4 elementai, o antroje sąrašo pusėje taip pat yra 4 elementai. Tai yra gerai. Kadangi indeksų skaičiavimas prasideda nuo 0, vidurinis indeksas yra 3 = 8 /2 - 1.

Ką daryti, kai sąrašo ar antrinio sąrašo elementų skaičius yra nelyginis? Pradžioje ilgis vis dar dalijamas iš 2. Pagal susitarimą elementų skaičius pirmoje šio padalijimo pusėje yra ilgis / 2 + 1/2. Indekso skaičiavimas prasideda nuo nulio. Vidurinis indeksas nurodomas pagal ilgį / 2 - 1/2. Pagal susitarimą tai laikoma vidurine sąvoka. Pavyzdžiui, jei sąrašo elementų skaičius yra 5, tada vidurinis indeksas yra 2 = 5/2 - 1/2. Ir pirmoje sąrašo pusėje yra trys elementai, o antroje - du elementai. Vidutinis viso sąrašo elementas yra trečiasis rodyklės elementas, 2, kuris yra vidurinis indeksas, nes indeksų skaičiavimas prasideda nuo 0.

Tokiu būdu padalijimas yra sveikųjų skaičių aritmetikos pavyzdys.

Trijų vertybių mediana

Klausimas: kokia yra sekos mediana:

C B A

Sprendimas:
Išdėstykite sąrašą didėjančia tvarka:

A B C

Vidurinis terminas B yra mediana. Tai dydis, kuris yra tarp kitų dviejų dydžių.

Medianos paieška sąraše nėra tokia. Pavyzdžiui, 19 nerūšiuotų elementų sąraše gali būti reikalaujama pirmojo, viduriniojo ir paskutinio elemento mediana. Šios trys vertės gali būti ne didėjančia tvarka; todėl reikia atsižvelgti į jų indeksus.

Naudojant greitą rūšiavimą, būtina viso sąrašo ir antrinių sąrašų mediana. Pseudokodas, skirtas ieškoti trijų sąraše (masyve) išdėstytų verčių mediana:

Sąvoka arr reiškia masyvą. Šis kodo segmentas ieško medianos ir taip pat atlieka tam tikrą rūšiavimą. Šis kodo segmentas atrodo paprastas, tačiau gali būti gana painus. Taigi, atkreipkite dėmesį į šį paaiškinimą:

Rūšiuojant šioje pamokoje bus sudarytas sąrašas, kuriame pirmoji vertė yra mažiausia, o paskutinė - didžiausia. Naudojant abėcėlę, A yra mažesnis nei Z.

Čia ašis yra gauta mediana. Žemas yra žemiausias sąrašo ar antrinio sąrašo indeksas (nebūtinai mažiausia vertė); aukštas yra aukščiausias sąrašo ar antrinio sąrašo indeksas (nebūtinai pagal didžiausią vertę), o viduryje yra įprastas vidurinis indeksas (nebūtinai vidutinė viso sąrašo vertė).

Taigi, mediana, kurią reikia gauti, yra tarp žemiausio indekso vertės, vidurinio indekso vertės ir aukščiausio indekso vertės.

Kode pirmiausia gaunamas įprastas vidurinis indeksas. Pradžioje sąrašas nerūšiuotas. Trijų verčių palyginimas ir tam tikras pertvarkymas didėjančia tvarka turi būti atliekamas vienu metu. Pirmajame teiginyje lyginama žemiausio ir vidutinio indekso vertė. Jei vidurinio indekso rodiklis yra mažesnis nei žemiausio indekso, tada abi vertės keičiasi pozicijomis. Taip pradedamas rūšiavimas ir keičiama sąrašo ar antrinio sąrašo reikšmių tvarka. Antrajame teiginyje lyginama aukščiausio ir žemiausio indekso vertė. Jei aukščiausio indekso rodiklis yra mažesnis nei žemiausio indekso, abi vertės keičiasi pozicijomis. Tai šiek tiek surūšiuoja ir keičia vertybių išdėstymą sąraše ar papildomame sąraše. Trečiasis teiginys palygina vidutinio ir aukščiausio indekso vertę. Jei aukščiausio indekso rodiklis yra mažesnis už vidurinį indeksą, abi vertės keičiasi pozicijomis. Čia taip pat gali atsirasti tam tikras rūšiavimas ar pertvarkymas. Ši trečioji sąlyga nėra panaši į dvi ankstesnes.

Pasibaigus šiems trims apsikeitimo sandoriams, trijų nagrinėjamų verčių vidurkis būtų A [didelis], kurio pradinis turinys galėjo būti pakeistas kodo segmente. Pavyzdžiui, apsvarstykite nerūšiuotą seką:

C B A

Mes jau žinome, kad mediana yra B. Tačiau tai turėtų būti įrodyta. Tikslas yra gauti šių trijų verčių mediana naudojant aukščiau pateiktą kodo segmentą. Pirmasis if-teiginys lygina B ir C. Jei B yra mažesnis nei C, tada B ir C pozicijos turi būti pakeistos. B yra mažesnis nei C, todėl naujas išdėstymas tampa toks:

B C A

Atkreipkite dėmesį, kad pasikeitė žemiausio ir vidurinio indekso vertės. Antrasis if-teiginys lygina A ir B. Jei A yra mažesnis už B, tada A ir B pozicijas reikia sukeisti. A yra mažesnis nei B, todėl naujas išdėstymas tampa toks:

A C B

Atkreipkite dėmesį, kad pasikeitė aukščiausio ir žemiausio indekso vertės. Trečiasis teiginys palygina C ir B. Jei C yra mažesnis nei B, tada C ir B pozicijos turi būti pakeistos. C yra ne mažesnis kaip B, todėl apsikeitimas nevyksta. Nauja tvarka išlieka tokia pati kaip ir ankstesnė, tai yra:

A C B

B yra mediana, tai yra A [aukštas], ir tai yra ašis. Taigi, ašis yra pačiame sąrašo ar antrinio sąrašo gale.

Sukeitimo funkcija

Kita greito rūšiavimo funkcija yra keitimo funkcija. Apsikeitimo funkcija keičia dviejų kintamųjų reikšmes. Keitimo funkcijos pseudokodas yra:

Čia x ir y nurodo faktines vertes, o ne kopijas.

Rūšiavimas šiame straipsnyje sudarys sąrašą, kuriame pirmoji vertė yra mažiausia, o paskutinė - didžiausia.

Straipsnio turinys

• Greito rūšiavimo algoritmas
• Skaidinio pseudokodas
• Greito rūšiavimo iliustracija
• „Java“ kodavimas
• Išvada

Greito rūšiavimo algoritmas

Įprastas nerūšiuoto sąrašo rūšiavimo būdas yra atsižvelgti į dvi pirmąsias vertes. Jei jie nėra tvarkingi, sutvarkykite juos. Toliau apsvarstykite pirmąsias tris vertybes. Nuskaitykite pirmąsias dvi, kad pamatytumėte, kur tinka trečioji vertė, ir tinkamai ją pritaikykite. Tada apsvarstykite keturias pirmąsias vertybes. Nuskaitykite pirmąsias tris vertes, kad pamatytumėte, kur tinka ketvirta vertė, ir tinkamai ją pritaikykite. Tęskite šią procedūrą, kol visas sąrašas bus surūšiuotas.

Ši procedūra, dar vadinama brutalia jėga, kompiuterių programavimo kalba yra per lėta. Greito rūšiavimo algoritmas pateikiamas daug greičiau.

Greitojo algoritmo veiksmai yra šie:

1. Įsitikinkite, kad nerūšiuotame sąraše yra bent 2 numeriai, kuriuos reikia rūšiuoti.
2. Gaukite apskaičiuotą pagrindinę sąrašo vertę, vadinamą pagrindine. Medianas, kaip aprašyta aukščiau, yra vienas iš būdų pasukti. Skirtingi būdai turi savo privalumų ir trūkumų. - Žiūrėk vėliau.
3. Skirstykite sąrašą. Tai reiškia, kad įterpkite ašį į sąrašą. Tokiu būdu visi kairėje esantys elementai yra mažesni už sukamąją vertę, o visi dešinėje esantys elementai yra didesni arba lygūs sukimosi vertei. Yra skirtingi skaidymo būdai. Kiekvienas skaidymo metodas turi savo privalumų ir trūkumų. Skirstymas yra skaldymas skaldyk ir valdyk paradigmoje.
4. Kartokite 1, 2 ir 3 veiksmus rekursyviai naujoms porūšių poroms, kurios atsiranda, kol visas sąrašas bus surūšiuotas. Tai užkariauja skaldymo ir užkariavimo paradigmą.

Greito rūšiavimo pseudokodas yra:

Skaidinio pseudokodas

Šiame vadove naudojamas skaidinio pseudokodas:

Žemiau esančioje greito rūšiavimo iliustracijoje naudojamas šis kodas:

Greito rūšiavimo iliustracija

Apsvarstykite šį nerūšiuotą abėcėlės raidžių sąrašą (masyvą):

Q W E R T Y U I O P

Patikrinus, surūšiuotas sąrašas yra toks:

E I O P Q R T U W Y

Rūšiuotas sąrašas dabar bus įrodytas naudojant aukščiau pateiktą algoritmą ir pseudokodo segmentus iš nerūšiuoto sąrašo:

Q W E R T Y U I O P

Pirmasis posūkis nustatomas iš arr [0] = Q, arr [4] = T ir arr [9] = P, jis identifikuojamas kaip Q ir pateikiamas kraštutiniame sąrašo dešiniajame kampe. Taigi sąrašas su bet kokiomis šarnyro funkcijų rūšiavimo funkcijomis tampa toks:

P W E R T Y U I O Q

Dabartinis posūkis yra Q. Pasukimo procedūra atliko nedidelį rūšiavimą ir padėjo P į pirmą vietą. Gautas sąrašas turi būti pertvarkytas (padalytas) taip, kad visi kairėje esantys elementai būtų mažesnės vertės, tada sukamoji dalis ir visi elementai, esantys dešinėje pusėje, yra lygūs arba didesni už sukamąjį. Kompiuteris negali atlikti skaidymo tikrinant. Taigi tai daroma naudojant indeksus ir aukščiau pateiktą skaidinio algoritmą.

Žemas ir aukštas indeksai dabar yra 0 ir 9. Taigi kompiuteris pradės nuskaitymą nuo indekso 0, kol pasieks indeksą, kurio vertė yra lygi arba didesnė už sukamąją, ir laikinai sustoja. Jis taip pat nuskaitys nuo aukščiausio (dešiniojo) galo, 9 indekso, nusileisdamas žemyn, kol pasieks indeksą, kurio vertė yra mažesnė arba lygi posūkiui, ir laikinai sustos. Tai reiškia dvi sustojimo pozicijas. Jei i, didėjančio indekso kintamasis nuo mažo, dar nėra lygus mažesniam indekso kintamajam arba didesnis už jį, j nuo aukšto, tada šios dvi vertės keičiamos. Esant dabartinei situacijai, nuskaitymas iš abiejų galų sustojo ties W ir O. Taigi sąrašas tampa toks:

P O E R T Y U I W Q

Pasukimas vis dar yra K. Skenavimas priešingomis kryptimis tęsiamas ir atitinkamai sustabdomas. Jei i dar nėra lygus ar didesnis nei j, tada dvi vertės, kuriomis nustojo nuskaityti iš abiejų galų, yra pakeistos. Šį kartą nuskaitymas iš abiejų galų sustojo ties R ir I. Taigi sąrašo išdėstymas tampa toks:

P O E I T Y U R W Q

Pasukimas vis dar yra K. Skenavimas priešingomis kryptimis tęsiamas ir atitinkamai sustabdomas. Jei i dar nėra lygus ar didesnis nei j, tada dvi vertės, kuriomis nuskaitymas buvo sustabdytas, keičiamos. Šį kartą nuskaitymas iš abiejų galų sustojo ties T, o aš - j. i ir j susitiko arba kirto. Taigi, apsikeitimo negali būti. Sąrašas išlieka toks pat kaip:

P O E I T Y U R W Q

Šiuo metu ašis Q turi būti sudėta į galutinę rūšiavimo vietą. Tai atliekama keičiant arr [i] į arr [high], keičiant T ir Q. Sąrašas tampa toks:

P O E I Q Y U R W T

Šiuo metu viso sąrašo skaidymas baigėsi. Pivot = Q atliko savo vaidmenį. Dabar yra trys papildomi sąrašai:

P O E I Q Y U R W T

Skirstymas yra padalijimas ir užkariavimas (rūšiavimas) paradigmoje. Q yra teisingoje rūšiavimo padėtyje. Kiekvienas kairėje nuo Q esantis elementas yra mažesnis už Q, o kiekvienas elementas, esantis dešinėje nuo Q, yra didesnis už Q. Tačiau kairysis sąrašas vis dar nėra surūšiuotas; ir teisingas sąrašas vis dar nėra surūšiuotas. Visa greito rūšiavimo funkcija turi būti iškviesta rekursyviai, kad būtų galima surūšiuoti kairįjį ir dešinįjį sąrašus. Šis greito rūšiavimo atšaukimas turi būti tęsiamas; nauji daliniai sąrašai bus kuriami tol, kol visas pirminis sąrašas bus visiškai surūšiuotas. Kiekvieną kartą iškviečiant greito rūšiavimo funkciją, kairysis antrinis sąrašas yra apžiūrimas pirmiausia prieš atitinkamą dešinįjį sąrašą. Kiekvienam pogrupiui reikia gauti naują posūkį.

Dėl papildomo sąrašo:

P O E I

Nustatomas P, O ir I ašis (mediana). Šio poskyrio ir viso sąrašo atveju naujas arr [low] yra arr [0], o new arr [high] yra paskutinis arr [i-1] = arr [ 4-1] = arr [3], kur i yra paskutinis ankstesnio skaidinio posūkio rodiklis. Paskambinus „pivot“ () funkcijai, nauja sukimosi vertė, pivot = O. Negalima painioti tarp „pivot“ funkcijos ir „pivot“ vertės. Pasukimo funkcija gali šiek tiek rūšiuoti ir sukamąją vietą išdėstyti kraštinio dešiniojo sąrašo dešinėje. Šis sub-sąrašas tampa,

Aš P E O

Naudojant šią schemą, pasukimas visada baigiasi dešiniajame antrinio sąrašo arba sąrašo gale po jo iškvietimo. Skenavimas iš abiejų galų prasideda nuo arr [0] ir arr [3], kol i ir j susitinka arba susikerta. Palyginimas atliekamas su pivot = O. Pirmieji sustojimai yra prie P ir E. Jie yra sukeisti ir naujas sub-sąrašas tampa:

I E P O

Tęsiamas nuskaitymas iš abiejų galų, o naujos stotelės yra P ir i, o E - j. Dabar aš ir j susitiko arba kirto. Taigi papildomas sąrašas išlieka toks pat kaip:

I E P O

Dalinio sąrašo ar sąrašo skaidymas baigiasi, kai šarnyras yra galutinėje padėtyje. Taigi naujos arr [i] ir arr [high] vertės yra pakeistos. Tai yra, P ir O yra sukeisti. Naujas potinklis tampa toks:

Aš ir P.

O dabar yra galutinė viso sąrašo pozicija. Jos, kaip šarnyro, vaidmuo baigėsi. Šiuo metu papildomas sąrašas yra padalintas į dar tris sąrašus, kurie yra:

Aš ir P.

Šiuo metu turi būti iškviestas pirmojo dešiniojo sub-sąrašo greitas rūšiavimas. Tačiau jis nebus vadinamas. Vietoj to jis bus pažymėtas ir rezervuotas, kad paskambintų vėliau. Vykdant skaidymo funkcijos teiginius, funkcijos viršuje dabar turi būti iškviestas kairiojo antrinio sąrašo greitasis rūšiavimas (iškvietus „pivot ()“). Jis bus pakviestas į sąrašą:

T.Y

Jis prasidės ieškant I ir E mediana. Čia, arr [low] = I, arr [mid] = I ir arr [high] = E. Taigi mediana, pivot, turėtų būti nustatyta pagal pasukimo algoritmą kaip , I. Tačiau aukščiau pateiktas pasukamasis pseudokodas nustatys sukamąjį elementą kaip E. Ši klaida įvyksta čia, nes minėtas pseudokodas skirtas trims, o ne dviem elementams. Toliau diegiant kodą yra šiek tiek pakoreguota. Sub-sąrašas tampa,

E aš

Pasukimas visada pasibaigia dešiniajame antrinio sąrašo ar sąrašo gale. Skenavimas iš abiejų galų prasideda nuo arr [0] ir arr [1], kol i ir j susitinka arba susikerta. Palyginimas atliekamas su pivot = I. Pirmosios ir vienintelės stotelės yra ties I ir E: ties I - i ir E - j. Dabar aš ir j susitiko arba kirto. Taigi, papildomas sąrašas išlieka toks pat kaip:

E aš

Dalinio sąrašo ar sąrašo skaidymas baigiasi, kai šarnyras yra galutinėje padėtyje. Taigi naujos arr [i] ir arr [high] vertės yra pakeistos. Čia atsitinka, kad arr [i] = I ir arr [high] = I. Taigi ta pati vertė keičiama su savimi. Naujas potinklis tampa toks:

E aš

Dabar esu galutinėje viso sąrašo pozicijoje. Jos, kaip šarnyro, vaidmuo baigėsi. Dabar šis sąrašas yra padalintas į dar du sąrašus, kurie yra:

E aš

Dabar ašys buvo Q, O ir I. Pivots baigiasi savo galutinėmis pozicijomis. Vieno elemento, pvz., P aukščiau, sąrašas taip pat baigiasi galutine padėtimi.

Šiuo metu pirmasis kairysis sub-sąrašas buvo visiškai surūšiuotas. Ir rūšiavimo procedūra dabar yra tokia:

E I O P Q Y U R W T

Pirmasis dešinysis sub-sąrašas:

Y U R W T

dar reikia surikiuoti.

Pirmojo dešiniojo sub-sąrašo užkariavimas
Atminkite, kad greitojo rūšiavimo skambutis į pirmąjį dešinįjį sub-sąrašą buvo pažymėtas ir rezervuotas, o ne vykdomas. Šiuo metu jis bus įvykdytas. Taigi naujasis arr [žemas] = arr [5] = arr [QPivotIndex+1], o naujas arr [aukštas] lieka arr [9]. Panašus veiklos rinkinys, įvykęs pirmajame kairiajame sub-sąraše, įvyks čia. Ir šis pirmasis dešinysis sub-sąrašas surūšiuotas taip:

R T U W Y

O pradinis nerūšiuotas sąrašas buvo surūšiuotas taip:

E I O P Q R T U W Y

„Java“ kodavimas

Įdėjus algoritmą į „Java“, tereikia visus aukščiau pateiktus pseudokodo segmentus sudėti į „Java“ metodus vienoje klasėje. Nepamirškite, kad klasėje turi būti pagrindinis () metodas, kuris iškvies funkciją quicksort () su nerūšiuotu masyvu.

Pivot () metodas

„Java pivot ()“ metodas, kuris grąžina vertę „pivot“, turėtų būti:

Apsikeitimo () metodas

Apsikeitimo () metodas turėtų būti toks:

Greitojo () metodas

Quicksort () metodas turėtų būti toks:

Skirstymo () metodas

Skirstymo () metodas turėtų būti toks:

Pagrindinis () metodas

Pagrindinis () metodas gali būti:

Visi aukščiau išvardyti metodai gali būti priskiriami vienai klasei.

Išvada

Greitas rūšiavimas yra rūšiavimo algoritmas, kuris naudoja padalijimo ir užkariavimo paradigmą. Jis pradedamas dalijant nerūšiuotą sąrašą į du ar tris antrinius sąrašus. Šiame vadove „Quick Sort“ suskirstė sąrašą į tris antrinius sąrašus: kairįjį, vidutinį vieno elemento sąrašą ir dešinįjį papildomą sąrašą. Užkariavimas naudojant greitą rūšiavimą-tai sąrašo arba antrinio sąrašo padalijimas, rūšiuojant juos, naudojant pasukamąją vertę. Ši pamoka paaiškino vieną greito rūšiavimo diegimą „Java“ kompiuterio kalba.

Apie autorių

Chrysanthus Forcha

Matematikos integracijos iš pirmųjų principų ir susijusių serijų atradėjas. Techninio išsilavinimo magistro laipsnis, kurio specializacija yra elektronika ir kompiuterių programinė įranga. Bakalauro elektronika. Taip pat turiu žinių ir patirties kompiuterių ir telekomunikacijų magistrantūroje. Iš 20 000 rašytojų devarticles.com buvau 37 -as geriausias rašytojas. Šiose srityse dirbu daugiau nei 10 metų.

SUSIJĘ LINUX UŽMONĖS POSTAI

• Stygų palyginimas „Java“
• Kaip naudoti „HashMap“ „Java“
• Greitas rūšiavimas „Java“ paaiškinta
• Dvejetainių medžių išankstinio užsakymo peržiūra „Java“
• Sujungti Rūšiuoti „Java Explained“
• Kaip naudotis skaitytuvu „Java“
• Java rašyti į failą