Pagkakaiba sa pagitan ng Mabilis na Pagsunud-sunod at Pagsamahin

May -Akda: Laura McKinney
Petsa Ng Paglikha: 1 Abril 2021
I -Update Ang Petsa: 10 Mayo 2024
Anonim
Trangkaso: Mabilis na Paggaling - ni Doc Willie Ong #179
Video.: Trangkaso: Mabilis na Paggaling - ni Doc Willie Ong #179

Nilalaman


Ang mabilis na pag-uuri at pagsamahin ang mga algorithm ay batay sa hatiin at lupigin ang algorithm na gumagana sa katulad na paraan. Ang naunang pagkakaiba sa pagitan ng mabilis at pagsamahin ay na sa mabilis na pagsunud-sunod ang sangkap na pangpang ay ginagamit para sa pag-uuri. Sa kabilang banda, ang pagsasanib ng uri ay hindi gumagamit ng sangkap na pang-pivot para sa pagsasagawa ng pag-uuri.

Ang parehong mga diskarte sa pag-uuri, mabilis na pag-uuri at pagsamahin ay binuo sa paraan ng paghati at lupigin kung saan ang hanay ng mga elemento ay nahati at pagkatapos ay pinagsama pagkatapos ng pag-aayos. Ang mabilis na pag-uuri ay karaniwang nangangailangan ng mas maraming paghahambing kaysa pagsamahin ang pag-uuri ng isang malaking hanay ng mga elemento.

    1. Tsart ng paghahambing
    2. Kahulugan
    3. Pangunahing Pagkakaiba
    4. Konklusyon

Tsart ng paghahambing

Batayan para sa paghahambingMabilis na uriSumanib-uuri
Paghihiwalay ng mga elemento sa hanayAng paghahati ng isang listahan ng mga elemento ay hindi kinakailangang nahahati sa kalahati.Ang Array ay palaging nahahati sa kalahati (n / 2).
Pinakamasalimuot na pagiging kumplikado ng kasoO (n2)O (n log n)
Gumagana nang maayos saMas maliit na hanayNagpapatakbo ng pagmultahin sa anumang uri ng array.
BilisMas mabilis kaysa sa iba pang mga pag-uuri ng mga algorithm para sa maliit na set ng data.Patuloy na bilis sa lahat ng uri ng mga set ng data.
Karagdagang kinakailangan sa espasyo sa imbakanMas kauntiMarami pa
KahusayanHindi mahusay para sa mas malaking pag-iral. Mas mahusay.
Paraan ng pagsunud-sunodPanloobPanlabas


Kahulugan ng Mabilis na Pagsunud-sunod

Mabilis na uri ay malawakang ginagamit na pag-uuri ng algorithm dahil ito ay mabilis para sa mga maikling pag-antay. Ang hanay ng mga elemento ay nahahati sa mga bahagi nang paulit-ulit hanggang sa hindi posible na hatiin pa ito. Ang mabilis na pag-uuri ay kilala rin bilang pagbubukod ng pagkahati. Gumagamit ito ng isang pangunahing elemento (kilala bilang pivot) para sa paghati sa mga elemento. Ang isang pagkahati ay naglalaman ng mga elemento na mas maliit kaysa sa pangunahing elemento. Ang isa pang pagkahati ay naglalaman ng mga elemento na mas malaki kaysa sa pangunahing elemento. Ang mga elemento ay pinagsunod-sunod na maingat.

Ipagpalagay na ang A ay isang hanay A, A, A, …… .., A ng n number na kailangang pinagsunod-sunod. Ang mabilis na uri ng algorithm na binubuo ng mga sumusunod na hakbang.

  1. Ang unang elemento o anumang random na elemento na napili bilang susi, ipalagay ang key = A (1).
  2. Ang "mababang" pointer ay inilalagay sa pangalawa at "up" pointer ay nakaposisyon sa huling elemento ng array, i.e. mababa = 2 at pataas = n;
  3. Patuloy, dagdagan ang "mababang" pointer sa pamamagitan ng isang posisyon hanggang sa (A> key).
  4. Patuloy, pagbubura ng "up" pointer ng isang posisyon hanggang sa (A <= key).
  5. Kung pataas ay mas malaki kaysa sa mababang pagpapalitan ng A kasama ang A.
  6. Ulitin ang hakbang na 3,4, at 5 hanggang sa ang kondisyon sa hakbang 5 ay nabigo (i.e. up <= mababa) pagkatapos ay ibahin ang anyo ng A kasama ang susi.
  7. Kung ang mga elemento na naiwan ng susi ay mas maliit kaysa sa susi at ang mga elemento sa kanan ng susi ay mas malaki kaysa sa susi pagkatapos ang array ay nahati sa dalawang mga sub-arrays.
  8. Ang pamamaraan sa itaas ay paulit-ulit na inilalapat sa mga subarrays hanggang ang buong hanay ay pinagsunod-sunod.


Mga Pakinabang at Kakulangan

Nagtataglay ito ng isang mabuting average na pag-uugali sa kaso. Ang pagiging kumplikado ng oras ng pagiging kumplikado ng mabilis na uri ay mabuti na ito ay mas mabilis kaysa sa mga algorithm tulad ng bubble sort, insertion sort at pagpili sort. Gayunpaman, ito ay kumplikado at napaka-recursive, iyon ang dahilan na hindi ito angkop para sa mga malalaking arrays.

Kahulugan ng Pagsamahin na Pagsunud-sunod

Sumanib-uuri ay isang panlabas na algorithm na batay din sa paghati at pagsakop sa diskarte. Ang mga elemento ay nahati sa mga sub-arrays (n / 2) nang paulit-ulit hanggang sa isang elemento lamang ang natitira, na makabuluhang bumabawas sa pag-uuri ng oras. Gumagamit ito ng karagdagang imbakan para sa pag-iimbak ng pandiwang pantulong. Ang uri ng pagsamahin ay gumagamit ng tatlong mga arrays kung saan ang dalawa ay ginagamit para sa pag-iimbak ng bawat kalahati, at ang pangatlo ay ginagamit upang maiimbak ang pangwakas na listahan ng pinagsunod-sunod. Ang bawat hanay ay pagkatapos ay pinagsunod-sunod na maingat. Sa wakas, ang mga subarrays ay pinagsama upang gawin itong laki ng elemento ng array. Ang listahan ay palaging nahahati sa kalahati (n / 2) na hindi kanais-nais sa mabilis na pag-uuri.

Hayaan ang A maging ang hanay ng n bilang ng mga elemento na maiayos A, A, ………, A. Ang pagsasama-sama ay sumusunod sa mga ibinigay na hakbang.

  1. Hatiin ang array A sa tinatayang n / 2 na pinagsunod-sunod na sub-array sa pamamagitan ng 2, na nangangahulugang ang mga elemento sa (A, A), (A, A), (A, A), (A, A) sub-arrays ay dapat maging sa pinagsunod-sunod na pagkakasunud-sunod.
  2. Pagsamahin ang bawat pares ng mga pares upang makuha ang listahan ng pinagsunod-sunod na mga subarrays na sukat 4; ang mga elemento sa subarrays ay nasa uri din na pagkakasunud-sunod, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
  3. Ang hakbang 2 ay paulit-ulit na isinasagawa hanggang sa mayroon lamang isang pinagsunod-sunod na hanay ng laki n.

Mga Pakinabang at Kakulangan

Ang pagsasama-sama ng algorithm ay gumaganap sa eksaktong pareho at tumpak na paraan anuman ang bilang ng mga elemento na kasangkot sa pag-uuri. Gumagana ito ng maayos kahit na sa malaking set ng data. Gayunpaman, kumonsumo ng mas malaking bahagi ng memorya.

  1. Sa pinagsamang pinagsama, ang array ay dapat na hatiin sa dalawang halves lamang (i.e. n / 2). Tulad ng laban, sa mabilis na pagkakasunud-sunod, walang pagpilit sa paghati sa listahan sa pantay na mga elemento.
  2. Ang pinakamasamang kaso ng pagiging kumplikado ng mabilis na pag-uuri ay O (n2) habang nangangailangan ng mas maraming paghahambing sa pinakamasamang kalagayan. Sa kaibahan, ang pinagsama-samang uri ay may parehong pinakamasamang kaso at average na pagiging kumplikado ng kaso, iyon ang O (n log n).
  3. Ang uri ng pagsamahin ay maaaring gumana nang maayos sa anumang uri ng data set kung ito ay malaki o maliit. Sa kabaligtaran, ang mabilis na pag-uuri ay hindi maaaring gumana nang maayos sa malalaking mga database.
  4. Mabilis na uri ay mas mabilis kaysa sa pagsamahin ang uri sa ilang mga kaso tulad ng para sa maliit na set ng data.
  5. Ang pag-uuri ng pagsasama ay nangangailangan ng karagdagang puwang ng memorya upang maiimbak ang mga pandiwang pantulong. Sa kabilang banda, ang mabilis na uri ay hindi nangangailangan ng maraming espasyo para sa labis na imbakan.
  6. Pagsunud-sunod ng pagsamahin ay mas mahusay kaysa sa mabilis na pag-uuri.
  7. Ang mabilis na pag-uuri ay panloob na paraan ng pag-uuri kung saan ang data na maiayos ay nababagay sa isang oras sa pangunahing memorya. Sa kabaligtaran, ang uri ng pagsasanib ay panlabas na paraan ng pag-uuri kung saan ang data na maiayos ay hindi maaaring mapunan ng memorya sa parehong oras at ang ilan ay dapat na panatilihin sa pandiwang pantulong.

Konklusyon

Ang mabilis na uri ay mas mabilis na mga kaso ngunit hindi epektibo sa ilang mga sitwasyon at gumaganap din ng maraming paghahambing kumpara sa pagsamahin. Kahit na ang pagsasama-sama ay nangangailangan ng mas kaunting paghahambing, kailangan nito ng karagdagang puwang ng memorya ng 0 (n) para sa pag-iimbak ng dagdag na hanay habang ang mabilis na pag-uuri ay nangangailangan ng puwang ng O (log n).