Ātrā kārtošana Java skaidrojumā

Konvencija uz pusi

Ja saraksta elementu skaits ir vienāds, saraksta samazināšana uz pusi nozīmē, ka saraksta burtiskā pirmā puse ir pirmā puse, bet burtiskā saraksta otrā puse - otrā puse. Visa saraksta vidus (vidējais) elements ir pirmā saraksta pēdējais elements. Tas nozīmē, ka vidējais indekss ir garums / 2 - 1, jo indeksa skaitīšana sākas no nulles. Garums ir elementu skaits sarakstā. Piemēram, ja elementu skaits ir 8, tad saraksta pirmajā pusē ir 4 elementi, bet saraksta otrajā pusē ir arī 4 elementi. Tas ir labi. Tā kā indeksa skaitīšana sākas no 0, vidējais indekss ir 3 = 8 /2 - 1.

Kā būtu ar gadījumu, kad elementu skaits sarakstā vai apakšsarakstā ir nepāra? Sākumā garums joprojām tiek dalīts ar 2. Pēc vienošanās elementu skaits šī sadalījuma pirmajā pusē ir garums / 2 + 1/2. Indeksa skaitīšana sākas no nulles. Vidējo indeksu norāda garums / 2 - 1/2. Pēc vienošanās to uzskata par vidējo terminu. Piemēram, ja elementu skaits sarakstā ir 5, tad vidējais indekss ir 2 = 5/2 - 1/2. Un saraksta pirmajā pusē ir trīs elementi, bet otrajā pusē - divi elementi. Visa saraksta vidējais elements ir trešais indeksa elements 2, kas ir vidējais indekss, jo indeksu skaitīšana sākas no 0.

Šāds dalījums ir veselu skaitļu aritmētikas piemērs.

Trīs vērtību mediāna

Jautājums: Kāda ir secības mediāna:

C B A

Risinājums:
Sakārtojiet sarakstu augošā secībā:

A B C

Vidējais termins B ir mediāna. Tas ir lielums, kas atrodas starp pārējiem diviem lielumiem.

Mediānas meklēšana sarakstā nav tāda. Piemēram, 19 nešķirotu elementu sarakstā var būt nepieciešama pirmā elementa, vidējā un pēdējā elementa mediāna. Šīs trīs vērtības var nebūt augošā secībā; un tāpēc ir jāņem vērā to indeksi.

Izmantojot ātro kārtošanu, ir nepieciešama visa saraksta un apakšsarakstu mediāna. Pseidokods, lai meklētu trīs vērtību mediānu, kas izvietotas sarakstā (masīvā), ir šāda:

Termins arr nozīmē masīvs. Šis koda segments meklē mediānu un arī kārto. Šis koda segments izskatās vienkāršs, taču tas var būt diezgan mulsinošs. Tāpēc pievērsiet uzmanību šādam skaidrojumam:

Šķirošana šajā apmācībā radīs sarakstu, kurā pirmā vērtība ir mazākā vērtība, bet pēdējā vērtība ir lielākā vērtība. Izmantojot alfabētu, A ir mazāks par Z.

Šeit šarnīrsavienojums ir iegūtā mediāna. Zems ir zemākais saraksta vai apakšsaraksta indekss (ne vienmēr zemākajai vērtībai); augsts ir saraksta vai apakšsaraksta augstākais indekss (ne vienmēr augstākajai vērtībai), bet vidējais ir parastais vidējais indekss (ne vienmēr visa saraksta vidējai vērtībai).

Tātad, iegūstamā mediāna ir starp zemākā indeksa vērtību, vidējā indeksa vērtību un augstākā indeksa vērtību.

Kodā vispirms tiek iegūts parastais vidējais indekss. Šajā sākumā saraksts nav sakārtots. Trīs vērtību salīdzināšanai un zināmai pārkārtošanai augošā secībā ir jānotiek vienlaicīgi. Pirmajā if-paziņojumā tiek salīdzināta zemākā indeksa un vidējā indeksa vērtība. Ja vidējā indeksa rādītājs ir mazāks par zemākā indeksa rādītāju, tad abas vērtības apmainās ar pozīcijām. Tas sāk šķirošanu un maina vērtību izkārtojumu sarakstā vai apakšsarakstā. Otrais if-apgalvojums salīdzina augstākā indeksa un zemākā indeksa vērtību. Ja augstākā indeksa rādītājs ir mazāks nekā zemākā indeksa rādītājs, abas vērtības apmainās ar pozīcijām. Tas veic zināmu saraksta vai apakšsaraksta vērtību izkārtojuma kārtošanu un maiņu. Trešais if-paziņojums salīdzina vidējā indeksa un augstākā indeksa vērtību. Ja augstākā indeksa rādītājs ir mazāks par vidējo indeksu, abas vērtības apmainās ar pozīcijām. Šeit var rasties arī kāda šķirošana vai pārkārtošana. Šis trešais if-nosacījums nav tāds kā iepriekšējie divi.

Šo trīs mijmaiņas darījumu beigās trīs attiecīgo vērtību vidējā vērtība būtu A [augsta], kuras sākotnējais saturs varētu būt mainīts kodu segmentā. Piemēram, ņemiet vērā nešķiroto secību:

C B A

Mēs jau zinām, ka mediāna ir B. Tomēr tas ir jāpierāda. Mērķis šeit ir iegūt šo trīs vērtību mediānu, izmantojot iepriekš minēto koda segmentu. Pirmais if-apgalvojums salīdzina B un C. Ja B ir mazāks par C, tad B un C pozīcijas ir jāmaina. B ir mazāks par C, tāpēc jaunais izkārtojums kļūst par:

B C A

Ievērojiet, ka ir mainījušās zemākā un vidējā indeksa vērtības. Otrais if-apgalvojums salīdzina A un B. Ja A ir mazāks par B, tad A un B pozīcijas ir jāmaina. A ir mazāks par B, tāpēc jaunais izkārtojums kļūst par:

A C B

Ievērojiet, ka ir mainījušās augstākā un zemākā indeksa vērtības. Trešais if-apgalvojums salīdzina C un B. Ja C ir mazāks par B, tad C un B pozīcijas ir jāmaina. C nav mazāks par B, tāpēc mijmaiņa nenotiek. Jaunā kārtība paliek tāda pati kā iepriekšējā, tas ir:

A C B

B ir mediāna, tas ir, A [augsts], un tas ir pagrieziena punkts. Tātad šarnīrsavienojums ir izveidots saraksta vai apakšsaraksta galējā galā.

Mijmaiņas funkcija

Vēl viena funkcija, kas nepieciešama ātrai kārtošanai, ir maiņas funkcija. Mijmaiņas funkcija apmaina divu mainīgo vērtības. Pārslēgšanas funkcijas pseidokods ir šāds:

Šeit x un y attiecas uz faktiskajām vērtībām, nevis uz kopijām.

Šķirojot šajā rakstā, tiks izveidots saraksts, kurā pirmā vērtība ir mazākā vērtība, bet pēdējā vērtība ir lielākā vērtība.

Raksta saturs

• Ātrās kārtošanas algoritms
• Sadalīšanās pseidokods
• Ātrās kārtošanas ilustrācija
• Java kodēšana
• Secinājums

Ātrās kārtošanas algoritms

Parasts veids, kā kārtot nešķirotu sarakstu, ir apsvērt pirmās divas vērtības. Ja tie nav kārtībā, sakārtojiet tos. Tālāk apsveriet pirmās trīs vērtības. Skenējiet pirmos divus, lai redzētu, kur trešā vērtība ir piemērota, un ievietojiet to atbilstoši. Pēc tam apsveriet pirmās četras vērtības. Skenējiet pirmās trīs vērtības, lai redzētu, kur ir piemērota ceturtā vērtība, un ievietojiet to atbilstoši. Turpiniet šo procedūru, līdz viss saraksts ir sakārtots.

Šī procedūra, ko datorprogrammēšanas valodā sauc arī par brutālu spēku, ir pārāk lēna. Ātrās kārtošanas algoritmam ir daudz ātrāka procedūra.

Ātrās šķirošanas algoritma darbības ir šādas:

1. Pārliecinieties, ka nešķirotajā sarakstā ir vismaz 2 kārtojami numuri.
2. Iegūstiet saraksta aptuveno centrālo vērtību, ko sauc par šarnīru. Mediāna, kā aprakstīts iepriekš, ir viens no veidiem, kā iegūt pagrieziena punktu. Dažādiem veidiem ir savas priekšrocības un trūkumi. - Redzēsimies vēlāk.
3. Sadaliet sarakstu. Tas nozīmē, ka sarakstā ievietojiet pagrieziena punktu. Tādā veidā visi elementi kreisajā pusē ir mazāki par pagrieziena vērtību, un visi elementi labajā pusē ir lielāki vai vienādi ar pagrieziena vērtību. Ir dažādi sadalīšanas veidi. Katrai nodalīšanas metodei ir savas priekšrocības un trūkumi. Sadalīšana ir šķelšanās sadalīt un iekarot paradigmā.
4. Rekursīvi atkārtojiet 1., 2. un 3. darbību jaunajiem apakšsaraksta pāriem, līdz parādās viss saraksts. Tas ir iekarošanas sadalīšanas un iekarošanas paradigmā.

Ātrās šķirošanas pseidokods ir šāds:

Sadalīšanās pseidokods

Šajā apmācībā izmantotais nodalījuma pseidokods ir šāds:

Tālāk redzamajā ātrās kārtošanas ilustrācijā tiek izmantots šis kods:

Ātrās kārtošanas ilustrācija

Apsveriet šādu nešķirotu alfabēta burtu sarakstu (masīvu):

Q W E R T Y U I O P

Pēc pārbaudes sakārtotais saraksts ir šāds:

E I O P Q R T U W Y

Tagad sakārtotais saraksts tiks pārbaudīts, izmantojot iepriekš minēto algoritmu un pseidokodu segmentus no nešķirotā saraksta:

Q W E R T Y U I O P

Pirmo pagriezienu nosaka no arr [0] = Q, arr [4] = T un arr [9] = P, un tas tiek identificēts kā Q un ievietots saraksta galējā labajā pusē. Tātad saraksts ar jebkuru pagrieziena funkciju kārtošanu kļūst par:

P W E R T Y U I O Q

Pašreizējais šarnīrsavienojums ir Q. Šarnīra procedūra veica nelielu šķirošanu un novietoja P pirmajā pozīcijā. Iegūtais saraksts ir jāpārkārto (jāsadala) tā, lai visi kreisajā pusē esošie elementi būtu mazākas vērtības, tad šarnīrsavienojums un visi elementi šarnīra labajā pusē ir vienādi vai lielāki par pagrieziena punktu. Dators nevar veikt sadalīšanu, veicot pārbaudi. Tātad, tas tiek darīts, izmantojot indeksus un iepriekš minēto nodalīšanas algoritmu.

Zemie un augstie indeksi tagad ir 0 un 9. Tātad dators sāks skenēt no indeksa 0, līdz tas sasniegs indeksu, kura vērtība ir vienāda vai lielāka par pagrieziena punktu, un uz laiku apstājas. Tas arī skenēs no augšējā (labā), indeksa 9, nokāpjot uz leju, līdz sasniegs indeksu, kura vērtība ir mazāka vai vienāda ar pagrieziena punktu, un uz laiku apstāsies. Tas nozīmē divas apstāšanās pozīcijas. Ja i, pieaugošā indeksa mainīgais, no zema vēl nav vienāds vai lielāks par samazinošo indeksa mainīgo, j no augsta, tad šīs divas vērtības tiek apmainītas. Pašreizējā situācijā skenēšana no abiem galiem apstājās pie W un O. Tātad saraksts kļūst šāds:

P O E R T Y U I W Q

Šarnīrs joprojām ir Q. Skenēšana pretējos virzienos turpinās un attiecīgi tiek pārtraukta. Ja i vēl nav vienāds ar vai lielāks par j, tad tiek mainītas divas vērtības, pie kurām skenēšana no abiem galiem tika pārtraukta. Šoreiz skenēšana no abiem galiem apstājās pie R un I. Tātad saraksta izkārtojums kļūst šāds:

P O E I T Y U R W Q

Šarnīrs joprojām ir Q. Skenēšana pretējos virzienos turpinās un attiecīgi tiek pārtraukta. Ja i vēl nav vienāds ar vai lielāks par j, tad tiek mainītas divas vērtības, pie kurām skenēšana tika pārtraukta. Šoreiz skenēšana no abiem galiem apstājās pie T par i un es par j. i un j ir tikušies vai šķērsojuši. Tātad mijmaiņas nevar būt. Saraksts paliek tāds pats kā:

P O E I T Y U R W Q

Šajā brīdī šarnīrs, Q, šķirošanā jānovieto galīgajā pozīcijā. To veic, apmainot arr [i] ar arr [high], samainot T un Q. Saraksts kļūst šāds:

P O E I Q Y U R W T

Šajā brīdī visa saraksta sadalīšana ir beigusies. Pivot = Q ir spēlējis savu lomu. Tagad ir trīs apakšsaraksti, kas ir:

P O E I Q Y U R W T

Sadalījums ir sadalīšana un iekarošana (šķirošana) paradigmā. Q atrodas pareizajā šķirošanas pozīcijā. Katrs elements pa kreisi no Q ir mazāks par Q, un katrs elements pa labi no Q ir lielāks par Q. Tomēr kreisais saraksts joprojām nav sakārtots; un pareizais saraksts joprojām nav sakārtots. Visa ātrās kārtošanas funkcija ir jāizsauc rekursīvi, lai sakārtotu kreiso un labo apakšsarakstu. Šī ātrās kārtošanas atsaukšana ir jāturpina; tiks izveidoti jauni apakšsaraksti, līdz viss sākotnējais saraksts būs pilnībā sakārtots. Katru reizi, kad tiek atsaukta funkcija Ātrā šķirošana, vispirms tiek apmeklēts kreisais apakšsaraksts, pirms tiek apmeklēts atbilstošais labais apakšsaraksts. Katram apakšsarakstam ir jāiegūst jauns šarnīrsavienojums.

Apakšsarakstam:

P O E I

Tiek noteikts P, O un I šarnīrs (mediāna). Šim apakšsarakstam un attiecībā uz pilnu sarakstu jaunais arr [zems] ir arr [0], un jaunais arr [augstais] ir pēdējais arr [i-1] = arr [ 4-1] = arr [3], kur i ir iepriekšējā nodalījuma pēdējais pagrieziena rādītājs. Pēc tam, kad ir izsaukta funkcija pivot (), jaunā šarnīra vērtība pivot = O. Nejauciet rakursfunkciju un šarnīra vērtību. Šarnīra funkcija var nedaudz sakārtot un pagriezt apakšsaraksta galējā labajā stūrī. Šis apakšsaraksts kļūst par

I P E O

Izmantojot šo shēmu, šarnīrs vienmēr beidzas apakšsaraksta vai saraksta labajā galā pēc funkcijas izsaukuma. Skenēšana no abiem galiem sākas no arr [0] un arr [3], līdz i un j satiekas vai šķērso. Salīdzinājums tiek veikts ar pivot = O. Pirmās pieturas atrodas pie P un E. Tās tiek apmainītas, un jaunais apakšsaraksts kļūst par:

Es E P O

Turpinās skenēšana no abiem galiem, un jaunās pieturas atrodas pie P attiecībā uz i un pie E uz j. Tagad es un j satikāmies vai šķērsojām. Tātad apakšsaraksts paliek tāds pats kā:

Es E P O

Apakšsaraksta vai saraksta sadalīšana beidzas, kad šarnīrsavienojums ir novietots galīgajā pozīcijā. Tātad tiek mainītas jaunās arr [i] un arr [high] vērtības. Tas ir, P un O tiek apmainīti. Jaunais apakšsaraksts kļūst par:

I E O P.

Tagad O ir visa saraksta galīgajā pozīcijā. Tā kā šarnīra loma ir beigusies. Apakšsaraksts pašlaik ir sadalīts vēl trīs sarakstos, kas ir:

I E O P.

Šajā brīdī ir jāizsauc pirmā saraksta apakšējā saraksta ātrā kārtošana. Tomēr tas netiks saukts. Tā vietā tas tiks atzīmēts un rezervēts, lai to izsauktu vēlāk. Sadalīšanas funkcijas paziņojumu izpildes laikā no funkcijas augšdaļas ir jāizsauc kreisā apakšsaraksta ātrā kārtošana (pēc tam, kad ir izsaukta pivot ()). Tas tiks saukts par sarakstu:

Es E.

Tas sāksies, meklējot I un E mediānu. Šeit, arr [low] = I, arr [mid] = I un arr [high] = E. Tātad mediāna, pivot, jānosaka ar šarnīra algoritmu kā , I. Tomēr iepriekš minētais šarnīra pseidokode noteiks pagrieziena punktu kā E. Šī kļūda rodas šeit, jo iepriekš minētais pseidokods ir domāts trim elementiem, nevis diviem. Tālāk norādītajā ieviešanā kodā ir veiktas dažas korekcijas. Apakšsaraksts kļūst par

E es

Šarnīrs vienmēr beidzas apakšsaraksta vai saraksta labajā galā pēc funkcijas izsaukuma. Skenēšana no abiem galiem sākas no arr [0] un arr [1] ekskluzīvi, līdz i un j satiekas vai šķērso. Salīdzinājums tiek veikts ar pivot = I. Pirmās un vienīgās pieturas ir pie I un E: pie I - i un pie E - j. Tagad i un j ir tikušies vai šķērsojuši. Tātad apakšsaraksts paliek tāds pats kā:

E es

Apakšsaraksta vai saraksta sadalīšana beidzas, kad šarnīrsavienojums ir novietots galīgajā pozīcijā. Tātad tiek mainītas jaunās arr [i] un arr [high] vērtības. Šeit gadās, ka arr [i] = I un arr [high] = I. Tātad tā pati vērtība tiek apmainīta ar sevi. Jaunais apakšsaraksts kļūst par:

E es

Tagad es esmu galīgajā pozīcijā attiecībā uz visu sarakstu. Tā kā šarnīra loma ir beigusies. Apakšsaraksts tagad ir sadalīts vēl divos sarakstos, kas ir

E es

Tagad pagrieziena punkti līdz šim ir bijuši Q, O un I. Pivots beidzas savās galīgajās pozīcijās. Viena elementa apakšsaraksts, piemēram, iepriekš minētais P, arī beidzas tā galīgajā vietā.

Šajā brīdī pirmais kreisais apakšsaraksts ir pilnībā sakārtots. Un šķirošanas procedūra tagad ir šāda:

E I O P Q Y U R W T

Pirmais labais apakšsaraksts:

Y U R W T

vēl jāsakārto.

Pirmā labā apakšsaraksta iekarošana
Atcerieties, ka ātrās kārtošanas zvans pirmajam labajam apakšsarakstam tika atzīmēts un rezervēts, nevis izpildīts. Šajā brīdī tas tiks izpildīts. Tātad jaunais arr [zems] = arr [5] = arr [QPivotIndex+1], un jaunais arr [augsts] paliek arr [9]. Līdzīgs darbību kopums, kas notika pirmajā kreisajā apakšsarakstā, notiks šeit. Un šis pirmais labais apakšsaraksts ir sakārtots šādi:

R T U W Y

Un sākotnējais nešķirotais saraksts ir sakārtots šādi:

E I O P Q R T U W Y

Java kodēšana

Algoritma ievietošana Java ir tikai visu iepriekš minēto pseidokodu segmentu ievietošana Java metodēs vienā klasē. Neaizmirstiet, ka klasē ir jābūt galvenajai () metodei, kas izsauks funkciju quicksort () ar nesortēto masīvu.

Pivot () metode

Java pivot () metodei, kas atgriež vērtību pivot, jābūt šādai:

Mijmaiņas () metode

Mijmaiņas () metodei jābūt šādai:

Ātrās šķirošanas () metode

Quicksort () metodei jābūt šādai:

Sadalīšanās () metode

Sadalīšanas () metodei jābūt šādai:

Galvenā () metode

Galvenā () metode var būt:

Visas iepriekš minētās metodes var apvienot vienā klasē.

Secinājums

Ātrā šķirošana ir šķirošanas algoritms, kas izmanto sadalīšanas un iekarošanas paradigmu. Tas sākas, sadalot nešķirotu sarakstu divos vai trīs apakšsarakstos. Šajā apmācībā Quick Sort ir sadalījis sarakstu trīs apakšsarakstos: kreisais apakšsaraksts, viena elementa vidējais saraksts un labais apakšsaraksts. Ātrās kārtošanas iekarošana ir saraksta vai apakšsaraksta sadalīšana, to kārtojot, izmantojot šarnīra vērtību. Šajā apmācībā ir izskaidrota viena ātrās kārtošanas ieviešana Java datora valodā.

Par autoru

Chrysanthus Forcha

Matemātikas integrācijas atklājējs no pirmajiem principiem un saistītās sērijas. Maģistra grāds tehniskajā izglītībā, kas specializējas elektronikā un datorprogrammatūrā. BSc elektronika. Man ir arī zināšanas un pieredze maģistrantūrā skaitļošanas un telekomunikāciju jomā. No 20 000 rakstnieku es biju 37. labākais rakstnieks vietnē devarticles.com. Šajās jomās strādāju vairāk nekā 10 gadus.

SAISTĪTĀS LINUX MĀJAS ZIŅAS

• Stīgu salīdzinājums Java
• Kā lietot HashMap Java
• Ātrā kārtošana Java skaidrojumā
• Bināro koku priekšpasūtīšanas pāreja Java
• Apvienot Kārtot Java izskaidrojumā
• Kā lietot skeneri Java
• Java rakstīt failā