Ipinaliwanag ang Mabilis na Pag-uri-uriin sa Java

Halving Convention

Kapag pantay ang bilang ng mga elemento sa isang listahan, ang paghati sa listahan ay nangangahulugang ang literal na unang kalahati ng listahan ay ang unang kalahati, at ang literal na pangalawang kalahati ng listahan ay ang ikalawang kalahati. Ang kalagitnaan (gitna) na elemento ng buong listahan, ay ang huling elemento ng unang listahan. Nangangahulugan ito na ang gitnang indeks ay haba / 2 - 1, dahil ang pagbibilang ng indeks ay nagsisimula mula sa zero. Ang haba ay ang bilang ng mga elemento sa listahan. Halimbawa, kung ang bilang ng mga elemento ay 8, kung gayon ang unang kalahati ng listahan ay may 4 na elemento at ang pangalawang kalahati ng listahan ay mayroon ding 4 na elemento. Ayos lang yan Dahil ang pagbibilang ng indeks ay nagsisimula mula sa 0, ang gitnang indeks ay 3 = 8/2 - 1.

Paano ang tungkol sa kaso, kung ang bilang ng mga elemento sa listahan o sub-list ay kakaiba? Sa simula, ang haba ay nahahati pa rin sa 2. Sa pamamagitan ng kombensyon, ang bilang ng mga elemento sa unang kalahati ng dibisyon na ito ay haba / 2 + 1/2. Nagsisimula ang pagbibilang ng index mula sa zero. Ang gitnang indeks ay ibinibigay ng haba / 2 - 1/2. Ito ay isinasaalang-alang bilang gitnang termino, sa pamamagitan ng kombensyon. Halimbawa, kung ang bilang ng mga elemento sa isang listahan ay 5, kung gayon ang gitnang indeks ay 2 = 5/2 - 1/2. At, mayroong tatlong mga elemento sa unang kalahati ng listahan at dalawang elemento sa ikalawang kalahati. Ang gitnang elemento ng buong listahan ay ang pangatlong elemento sa index, 2, na kung saan ay ang gitnang indeks dahil ang pagbibilang ng indeks ay nagsisimula mula sa 0.

Ang paghati sa ganitong paraan ay isang halimbawa ng integer arithmetic.

Median ng Tatlong Halaga

Tanong: Ano ang median ng pagkakasunud-sunod:

C B A

Solusyon:
Ayusin ang listahan sa pataas na pagkakasunud-sunod:

A B C

Ang gitnang termino, B, ay ang panggitna. Ito ang magnitude na namamalagi sa pagitan ng iba pang dalawang lakas.

Ang paghahanap para sa median sa isang listahan ay hindi ganoong uri. Halimbawa, sa isang listahan ng 19 na elemento na hindi pinag-ayos, ang median para sa unang elemento, gitnang elemento, at huling elemento ay maaaring kailanganin. Ang tatlong halagang ito ay maaaring wala sa pataas na pagkakasunud-sunod; at sa gayon, dapat isaalang-alang ang kanilang mga indeks.

Sa Mabilis na Pagbukud-bukurin, kinakailangan ang panggitna para sa buong listahan at mga sub-list. Ang pseudocode upang maghanap para sa median ng tatlong mga halagang na spaced sa isang listahan (array) ay:

Ang term arr ay nangangahulugang array. Ang segment ng code na ito ay naghahanap para sa panggitna at gumagawa din ng pag-uuri. Ang segment ng code na ito ay mukhang simple, ngunit maaaring ito ay lubos na nakalilito. Kaya, bigyang pansin ang sumusunod na paliwanag:

Ang pag-uuri sa tutorial na ito ay makakagawa ng isang listahan kung saan ang unang halaga ay ang pinakamaliit na halaga, at ang huling halaga ay ang pinakamalaking halaga. Gamit ang alpabeto, ang A ay mas mababa sa Z.

Dito, ang pivot ay ang nagresultang panggitna. Mababa ang pinakamababang index ng listahan o sub-list (hindi kinakailangan para sa pinakamababang halaga); mataas ang pinakamataas na index ng listahan o sub-list (hindi kinakailangan para sa pinakamataas na halaga), at gitna ay ang maginoo na gitnang indeks (hindi kinakailangan para sa gitnang halaga ng buong listahan).

Kaya, ang panggitna na makukuha ay nasa pagitan ng halaga ng pinakamababang index, ang halaga ng gitnang indeks, at ang halaga ng pinakamataas na index.

Sa code, ang maginoo na gitnang indeks ay nakuha muna. Sa pagsisimula na ito, hindi nabago ang listahan. Ang paghahambing at ilang pagsasaayos sa pataas na pagkakasunud-sunod ng tatlong mga halaga ay magaganap nang sabay. Inihambing ng unang if-statement ang halaga para sa pinakamababang index at ng gitna ng index. Kung ang nasa gitnang indeks ay mas mababa kaysa sa pinakamababang index, kung gayon ang dalawang halaga ay nagpapalit ng mga posisyon. Nagsisimula itong pag-uuri at binabago ang pag-aayos ng mga halaga sa listahan o sub-list. Kinukumpara ng pangalawang if-statement ang halaga para sa pinakamataas na index at ng pinakamababang index. Kung ang pinakamataas na index ay mas mababa kaysa sa pinakamababang index, ang dalawang halaga ay nagpapalit ng posisyon. Nagdadala ito ng ilang pag-uuri at pagbabago ng pag-aayos ng mga halaga sa listahan o sub-list. Pinaghahambing ng pangatlong if-statement ang halaga para sa gitnang indeks at ng pinakamataas na index. Kung ang pinakamataas na index ay mas mababa kaysa sa gitnang indeks, ang dalawang halaga ng mga posisyon ng pagpapalit. Ang ilang pag-uuri o muling pagsasaayos ay maaari ding maganap dito. Ang pangatlong kung-kondisyon na ito ay hindi tulad ng nakaraang dalawa.

Sa pagtatapos ng tatlong swap na ito, ang gitnang halaga ng tatlong pinag-uusapang halaga ay A [mataas], na ang orihinal na nilalaman ay maaaring mabago sa segment ng code. Halimbawa, isaalang-alang ang hindi nakasunod na pagkakasunud-sunod:

C B A

Alam na natin na ang panggitna ay B. Gayunpaman, dapat itong patunayan. Ang layunin dito ay upang makuha ang panggitna ng tatlong mga halagang ito gamit ang segment ng code sa itaas. Ang unang if-statement ay naghahambing sa B at C. Kung ang B ay mas mababa sa C, kung gayon ang mga posisyon ng B at C ay dapat ipagpalit. Ang B ay mas mababa sa C, kaya ang bagong pag-aayos ay naging:

B C A

Pansinin, ang mga halaga para sa pinakamababang index at ang gitnang indeks ay nagbago. Ang ikalawang if-statement ay naghahambing sa A at B. Kung ang A ay mas mababa sa B, kung gayon ang mga posisyon ng A at B ay kailangang palitan. Ang A ay mas mababa sa B, kaya ang bagong pag-aayos ay nagiging:

A C B

Pansinin, ang mga halaga para sa pinakamataas na index at ang pinakamababang index ay nagbago. Ang ikatlong if-statement ay naghahambing sa C at B. Kung ang C ay mas mababa sa B, kung gayon ang mga posisyon ng C at B ay kailangang palitan. Ang C ay hindi mas mababa sa B, kaya't walang pagpapalit na nagaganap. Ang bagong pag-aayos ay nananatili bilang nakaraang, iyon ay:

A C B

Ang B ay ang panggitna, kung saan ay, A [mataas], at ito ang pivot. Kaya, ang pivot ay ipinanganak sa matinding dulo ng listahan o sub-list.

Ang Pag-andar ng Pagpalit

Ang isa pang tampok na kinakailangan ng Quick Sort ay ang pagpapalit ng pagpapaandar. Ang pagpapaandar ng pagpapalit, nagpapalitan ng mga halaga ng dalawang variable. Ang pseudocode para sa pagpapalit ng pagpapaandar ay:

Dito, x at y sumangguni sa aktwal na mga halaga at hindi sa mga kopya.

Ang pag-uuri sa artikulong ito ay gagawa ng isang listahan kung saan ang unang halaga ay ang pinakamaliit na halaga, at ang huling halaga ay ang pinakamalaking halaga.

Nilalaman ng Artikulo

• Mabilis na Pag-uuri ng Algorithm
• Isang Partition Pseudocode
• Paglalarawan ng Mabilis na Pagsunud-sunurin
• Java Coding
• Konklusyon

Mabilis na Pag-uuri ng Algorithm

Ang normal na paraan upang pag-uri-uriin ang isang hindi nasortortang listahan ay upang isaalang-alang ang unang dalawang halaga. Kung hindi sila ayos, ayusin ang mga ito. Susunod, isaalang-alang ang unang tatlong mga halaga. I-scan ang unang dalawa upang makita kung saan umaangkop ang pangatlong halaga at akma itong naaangkop. Pagkatapos, isaalang-alang ang unang apat na halaga. I-scan ang unang tatlong mga halaga upang makita kung saan umaangkop ang ika-apat na halaga at naaangkop ito nang naaangkop. Magpatuloy sa pamamaraang ito hanggang sa maayos ang buong listahan.

Ang pamamaraang ito, na kilala rin bilang uri ng malupit na puwersa, sa pagsasalita ng computer programming, ay masyadong mabagal. Ang Quick Sort algorithm ay mayroong isang mas mabilis na pamamaraan.

Ang mga hakbang para sa quicksort algorithm ay ang mga sumusunod:

1. Siguraduhing mayroong hindi bababa sa 2 mga numero upang mai-uri-uriin ang hindi naka-unsort na listahan.
2. Kumuha ng isang tinantyang gitnang halaga para sa listahan, na tinatawag na pivot. Ang panggitna, tulad ng inilarawan sa itaas, ay isang paraan ng pagkuha ng pivot. Iba't ibang mga paraan dumating sa kanilang mga kalamangan at kawalan. - Tingnan mamaya.
3. Paghiwalayin ang listahan. Nangangahulugan ito, ilagay ang pivot sa listahan. Sa ganitong paraan, ang lahat ng mga elemento sa kaliwa ay mas mababa kaysa sa halaga ng pivot, at lahat ng mga elemento sa kanan ay mas malaki kaysa o katumbas ng halaga ng pivot. Mayroong iba't ibang mga paraan ng paghati. Ang bawat paraan ng pagkahati ay may mga kalamangan at kawalan. Ang paghati ay nahahati sa paradahan ng paghati-hati.
4. Ulitin ang mga hakbang 1, 2, at 3 nang paulit-ulit para sa mga bagong pares ng sub-list na lumilitaw hanggang sa maayos ang buong listahan. Ito ay pananakop sa paghihiwalay-at-mananakop na paradaym.

Ang Quick Sort pseudocode ay:

Isang Partition Pseudocode

Ang partisyon na pseudocode na ginamit sa tutorial na ito ay:

Sa ilustrasyon ng Mabilis na Pagbukud-bukurin sa ibaba, ginagamit ang code na ito:

Paglalarawan ng Mabilis na Pagsunud-sunurin

Isaalang-alang ang sumusunod na hindi nakasusunod na listahan (array) ng mga titik na alpabetiko:

Q W E R T Y U I O P

Sa pamamagitan ng inspeksyon, ang listahan ng pinagsunod-sunod ay:

E I O P Q R T U W Y

Patunayan na ngayon ang listahan ng pinagsunod-sunod, gamit ang nasa itaas na mga segment ng algorithm at pseudocode, mula sa hindi na-sort na listahan:

Q W E R T Y U I O P

Ang unang pivot ay natutukoy mula sa arr [0] = Q, arr [4] = T, at arr [9] = P, at kinilala bilang Q at inilagay sa matinding kanang bahagi ng listahan. Kaya, ang listahan na may anumang pag-uuri ng pag-andar ng pivot ay nagiging:

P W E R T Y U I O Q

Ang kasalukuyang pivot ay Q. Ang pamamaraan ng pivot ay gumawa ng ilang maliit na pag-uuri at inilagay ang P sa unang posisyon. Ang nagresultang listahan ay kailangang muling ayusin (pagkahati), tulad ng, ang lahat ng mga elemento sa kaliwa ay mas maliit sa halaga, pagkatapos ang pivot at lahat ng mga elemento sa kanan ng pivot, ay katumbas o mas malaki kaysa sa pivot. Ang computer ay hindi maaaring gumawa ng pagkahati sa pamamagitan ng inspeksyon. Kaya, ginagawa nito sa pamamagitan ng paggamit ng mga index at sa itaas na pagkahati algorithm.

Ang mababa at mataas na index ngayon ay 0 at 9. Kaya, magsisimula ang computer sa pamamagitan ng pag-scan mula sa index 0 hanggang sa maabot nito ang isang index, na ang halaga ay katumbas o mas malaki kaysa sa pivot at pansamantalang huminto doon. Mag-scan din ito mula sa mataas (kanan) na dulo, index 9, pababa, hanggang sa maabot ang isang index na ang halaga ay mas mababa sa o katumbas ng pivot at pansamantalang huminto doon. Nangangahulugan ito ng dalawang posisyon ng paghinto. Kung ako, ang variable ng incremental index, mula sa mababa ay hindi pa katumbas o mas malaki kaysa sa pagbawas ng variable ng index, j mula sa mataas, pagkatapos ang dalawang halagang ito ay napalitan. Sa kasalukuyang sitwasyon, ang pag-scan mula sa magkabilang dulo ay tumigil sa W at O. Kaya't ang listahan ay:

P O E R T Y U I W Q

Ang pivot ay pa rin Q. Ang pag-scan sa kabaligtaran ng mga direksyon ay nagpapatuloy at humihinto nang naaayon. Kung hindi pa ako katumbas o mas malaki kaysa sa j, pagkatapos ang dalawang halaga kung saan huminto ang pag-scan mula sa magkabilang dulo ay napalitan. Sa oras na ito, ang pag-scan mula sa magkabilang dulo ay tumigil sa R ​​at I. Kaya, ang pag-aayos ng listahan ay magiging:

P O E I T Y U R W Q

Ang pivot ay pa rin Q. Ang pag-scan sa kabaligtaran ng mga direksyon ay nagpapatuloy at humihinto nang naaayon. Kung hindi pa ako katumbas o mas malaki kaysa sa j, kung gayon ang dalawang halaga kung saan tumigil ang pag-scan, ay napalitan. Sa oras na ito, ang pag-scan mula sa magkabilang dulo ay tumigil sa T para sa i at ako para sa j. nagkita na kami ni j or nagcross. Kaya, maaaring walang pagpapalit. Ang listahan ay mananatiling pareho sa:

P O E I T Y U R W Q

Sa puntong ito, ang pivot, Q, ay dapat ilagay sa huling posisyon nito sa pag-uuri. Ginagawa ito sa pamamagitan ng pagpapalit ng arr [i] ng arr [mataas], pagpapalit ng T at Q. Ang listahan ay nagiging:

P O E I Q Y U R W T

Sa puntong ito, ang pagkahati para sa buong listahan ay natapos na. Ang pivot = Q ang gampanan nito. Mayroon na ngayong tatlong mga sub-list, na kung saan ay:

P O E I Q Y U R W T

Ang paghati ay paghati at pananakop (pag-uuri) sa tularan. Ang Q ay nasa tamang posisyon ng pag-uuri. Ang bawat elemento sa kaliwa ng Q ay mas maliit kaysa sa Q, at ang bawat elemento sa kanan ng Q ay mas malaki kaysa sa Q. Gayunpaman, ang kaliwang listahan ay hindi pa rin pinagsunod-sunod; at ang tamang listahan ay hindi pa rin pinagsunod-sunod. Ang buong pag-andar ng Quick Sort ay kailangang tawaging recursively upang maisaayos ang kaliwang sub-list at ang tamang sub-list. Ang pagpapabalik sa Quick Sort na ito ay dapat na magpatuloy; ang mga bagong sub-list ay bubuo hanggang sa ang buong orihinal na listahan ay ganap na naayos. Para sa bawat pagpapaalala ng pagpapaandar ng Mabilis na Pagsunud-sunurin, ang kaliwang sub-list ay dinaluhan muna bago ang kaukulang kanang sub-list ay dinaluhan. Ang isang bagong pivot ay kailangang makuha para sa bawat sub-list.

Para sa sub-list:

P O E I

Ang pivot (panggitna) para sa P, O, at natutukoy ako. Ang pivot ay magiging O. Para sa sub-list na ito, at nauugnay sa kumpletong listahan, ang bagong arr [low] ay arr [0], at ang bagong arr [high] ay ang huling arr [i-1] = arr [ 4-1] = arr [3], kung saan ako ang pangwakas na index ng pivot mula sa nakaraang pagkahati. Matapos ang function ng pivot () ay tinawag, ang bagong halaga ng pivot, pivot = O. Huwag malito sa pagitan ng pagpapaandar ng pivot at ng halaga ng pivot. Ang pagpapaandar ng pivot ay maaaring gumawa ng ilang maliit na pag-uuri at ilagay ang pivot sa matinding kanan ng sub-list. Ang sub-list na ito ay nagiging,

I P E O

Sa ganitong pamamaraan, ang pivot ay laging nagtatapos sa kanang dulo ng sub-list o listahan pagkatapos ng tawag sa pagpapaandar nito. Ang pag-scan mula sa magkabilang dulo ay nagsisimula sa arr [0] at arr [3] hanggang sa magkita o magkrus ang j at ko. Ang paghahambing ay tapos na sa pivot = O. Ang mga unang hintuan ay nasa P at E. Napalitan sila, at ang bagong sub-list ay nagiging:

I E P O

Nagpapatuloy ang pag-scan mula sa magkabilang dulo, at ang mga bagong hintuan ay nasa P para sa i at sa E para sa j. Ngayon ako at si j ay nagkakilala o tumatawid na. Kaya't ang sub-list ay nananatiling pareho sa:

I E P O

Ang pagkahati ng isang sub-list o listahan ay nagtatapos kapag ang pivot ay inilagay sa huling posisyon nito. Kaya, ang mga bagong halaga para sa arr [i] at arr [mataas] ay napalitan. Iyon ay, Ipinalitan ang P at O. Ang bagong sub-list ay nagiging:

I E O P

Ang O ay nasa huling posisyon na nito para sa buong listahan. Ang papel nito bilang isang pivot ay natapos na. Ang sub-list ay kasalukuyang nahahati sa tatlong iba pang mga listahan, na kung saan ay:

I E O P

Sa puntong ito, ang Quick Sort ng unang kanang sub-list ay dapat tawagan. Gayunpaman, hindi ito tatawagin. Sa halip, ito ay mapapansin at nakalaan, na tatawag sa paglaon. Tulad ng mga pahayag ng pag-andar ng pagkahati ay naisakatuparan, mula sa tuktok ng pagpapaandar, ito ang Mabilis na Pagbukud-bukurin para sa kaliwang sub-list na dapat tawaging ngayon (pagkatapos na tawagan ang pivot ()). Tatawagan ito para sa listahan:

Ako E

Magsisimula ito sa pamamagitan ng paghahanap ng median ng I at E. Dito, arr [mababa] = I, arr [mid] = I at arr [high] = E. Kaya't ang median, pivot, ay dapat na matukoy ng pivot algorithm bilang , I. Gayunpaman, matutukoy ng pivot pseudocode sa itaas ang pivot bilang E. Ang error na ito ay nangyayari dito dahil ang nabanggit na pseudocode ay inilaan para sa tatlong elemento at hindi dalawa. Sa pagpapatupad sa ibaba, mayroong ilang pagsasaayos sa code. Ang sub-list ay nagiging,

E ako

Ang pivot ay laging nagtatapos sa kanang dulo ng sub-list o listahan pagkatapos ng tawag sa pagpapaandar nito. Ang pag-scan mula sa magkabilang dulo ay nagsisimula sa arr [0] at arr [1] na eksklusibo hanggang sa magkita o magkrus ang j at ko. Ang paghahambing ay tapos na sa pivot = I. Ang una at tanging paghinto ay sa I at E: sa I para sa i at sa E para sa j. Ngayon ako at si j ay nagkakilala o tumawid na. Kaya, ang sub-list ay mananatiling pareho sa:

E ako

Ang pagkahati ng isang sub-list o listahan ay nagtatapos kapag ang pivot ay inilagay sa huling posisyon nito. Kaya, ang mga bagong halaga para sa arr [i] at arr [mataas] ay napalitan. Ito ay nangyayari dito na arr [i] = I at arr [mataas] = I. Kaya, ang parehong halaga ay ipinagpapalit sa sarili nito. Ang bagong sub-list ay nagiging:

E ako

Nasa huling posisyon na ako ngayon para sa buong listahan. Ang papel nito bilang isang pivot ay natapos na. Ang sub-list ay nahahati ngayon sa dalawa pang listahan, na,

E ako

Ngayon, ang mga pivot sa ngayon ay Q, O, at I. Ang mga pivot ay nagtatapos sa kanilang huling posisyon. Ang isang sub-list ng isang solong elemento, tulad ng P sa itaas, ay nagtatapos din sa huling posisyon nito.

Sa puntong ito, ang unang kaliwang sub-list ay ganap na naayos. At ang pamamaraan ng pag-uuri ay nasa:

E I O P Q Y U R W T

Ang unang kanang sub-list:

Y U R W T

kailangan pa rin ayusin.

Pagsakop sa Unang Tamang Sub-Listahan
Tandaan na ang tawag sa Mabilis na Pagsunud-sunurin para sa unang kanang sub-list ay nabanggit at nakalaan sa halip na maipatupad. Sa puntong ito, papatayin ito. At sa gayon, ang bagong arr [low] = arr [5] = arr [QPivotIndex + 1], at ang bagong arr [mataas] ay mananatiling arr [9]. Ang isang katulad na hanay ng mga aktibidad na nangyari para sa unang kaliwang sub-list ay magaganap dito. At ang unang kanang sub-list na ito ay pinagsunod-sunod sa:

R T U W Y

At ang orihinal na hindi napag-isang listahan ay inayos sa:

E I O P Q R T U W Y

Java Coding

Ang paglalagay ng algorithm sa Java ay upang mailagay lamang ang lahat ng mga itaas na segment ng pseudocode sa mga pamamaraan ng Java sa isang klase. Huwag kalimutan na kailangang mayroong isang pangunahing () pamamaraan sa klase na tatawag sa pagpapaandar ng quicksort () na may unsortadong array.

Ang pivot () Paraan

Ang pamamaraan ng Java pivot () na nagbabalik ng halaga, pivot, ay dapat na:

Ang pagpapalit () Paraan

Ang paraan ng pagpapalit () ay dapat na:

Ang quicksort () na Paraan

Ang paraan ng quicksort () ay dapat na:

Ang paghati () Paraan

Ang pamamaraan ng pagkahati () ay dapat na:

Ang pangunahing () Paraan

Ang pangunahing () pamamaraan ay maaaring:

Ang lahat ng mga pamamaraan sa itaas ay maaaring ilagay sa isang klase.

Konklusyon

Ang Quick Sort ay isang pag-uuri ng algorithm na gumagamit ng subdivag ng paghati-hati. Nagsisimula ito sa pamamagitan ng paghahati ng isang hindi nasortortang listahan sa dalawa o tatlong mga sub-list. Sa tutorial na ito, hinati ng Quick Sort ang isang listahan sa tatlong mga sub-list: isang kaliwang sub-list, isang gitnang listahan ng isang solong elemento, at isang tamang sub-list. Ang pagsakop sa Mabilis na Pag-uri-uriin ay naghahati ng isang listahan o sub-list habang inaayos ito, gamit ang isang halaga ng pivot. Ipinaliwanag ng tutorial na ito ang isang pagpapatupad ng Quick Sort sa wikang computer ng Java.

Tungkol sa may-akda

Chrysanthus Forcha

Discoverer ng Pagsasama ng matematika mula sa Unang Mga Prinsipyo at mga kaugnay na serye. Master's Degree sa Edukasyong Teknikal, na nagdadalubhasa sa Electronics at Computer Software. BSc Electronics. Mayroon din akong kaalaman at karanasan sa antas ng Master sa Computing at Telecommunications. Sa 20,000 manunulat, ako ang ika-37 pinakamahusay na manunulat sa devarticles.com. Nagtatrabaho ako sa mga patlang na ito nang higit sa 10 taon.

KAUGNAY NA LINUX HINT POSTS

• Paghahambing ng Mga String sa Java
• Paano gamitin ang HashMap sa Java
• Ipinaliwanag ang Mabilis na Pag-uri-uriin sa Java
• Binary Tree Preorder Traversal sa Java
• Pagsamahin ang Pagsunud-sunurin sa Java Ipinaliwanag
• Paano gamitin ang Scanner sa Java
• Sumulat sa file ang Java