Bubble Sort vs Selection Sort
Ang Bubble sort ay isang algorithm ng pagbubukod-bukod na gumagana sa pamamagitan ng pagdaan sa listahan na paulit-ulit na pagbubukod-bukod habang naghahambing ng mga pares ng elemento na magkatabi. Kung ang isang pares ng mga elemento ay nasa maling pagkakasunud-sunod ang mga ito ay ipinagpapalit upang ilagay ang mga ito sa tamang pagkakasunud-sunod. Ang traversal na ito ay paulit-ulit hanggang sa wala nang karagdagang pagpapalit ay kinakailangan. Ang selection sort ay isa ring sorting algorithm, na nagsisimula sa paghahanap ng minimum na elemento sa listahan at pagpapalit nito sa unang elemento. Ang prosesong ito ay inuulit para sa natitirang bahagi ng listahan sa pamamagitan ng paglalagay ng mga pinagpalit na elemento sa pagkakasunud-sunod.
Ano ang Bubble Sort?
Ang Bubble sort ay isang algorithm ng pagbubukod-bukod na gumagana sa pamamagitan ng pagdaan sa listahan na paulit-ulit na pagbubukod-bukod habang naghahambing ng mga pares ng elemento na magkatabi. Kung ang isang pares ng mga elemento ay nasa maling pagkakasunud-sunod ang mga ito ay ipinagpapalit upang ilagay ang mga ito sa tamang pagkakasunud-sunod. Ang traversal na ito ay paulit-ulit hanggang sa wala nang karagdagang pagpapalit ay kinakailangan (na nangangahulugan na ang listahan ay pinagsunod-sunod). Dahil ang mas maliliit na elemento sa listahan ay napupunta sa itaas habang ang isang bubble ay lumalabas, ito ay binibigyan ng pangalang bubble sort. Ang bubble sort ay isang napakasimpleng algorithm ng pag-uuri ngunit mayroon itong average na pagiging kumplikado ng oras ng kaso ng O(n2) kapag nag-uuri ng isang listahan na may n elemento. Dahil dito, hindi angkop ang bubble sort para sa pag-uuri ng mga listahan na may malaking bilang ng mga elemento. Ngunit dahil sa pagiging simple nito, itinuturo ang bubble sort sa panahon ng pagpapakilala sa mga algorithm.
Ano ang Selection Sort?
Ang Selection sort ay isa ring sorting algorithm na nagsisimula sa paghahanap ng minimum na elemento sa listahan at pagpapalit nito sa unang elemento. Pagkatapos ay matatagpuan ang pinakamababang elemento mula sa natitira sa listahan (mula sa pangalawang elemento hanggang sa huling elemento sa listahan) at pinalitan ng pangalawang elemento. Ang prosesong ito ay paulit-ulit para sa natitira sa listahan sa pamamagitan ng paglalagay ng mga swapped na elemento sa pagkakasunud-sunod. Kaya sa pagpili ng pag-uuri, sa anumang hakbang ng algorithm, ang listahan ay nahahati sa dalawang bahagi kung saan ang isang bahagi ay naglalaman ng mga pinagsunod-sunod na elemento at ang isa pang bahagi ay naglalaman ng mga hindi pinagsunod-sunod na elemento. Habang nagpapatuloy ang algorithm, lumalaki ang pinagsunod-sunod na listahan mula kaliwa hanggang kanan. Ang pag-uuri ng pagpili ay mayroon ding average na pagiging kumplikado ng oras ng kaso na O(n2). Samakatuwid, hindi rin ito angkop para sa pag-uuri ng malalaking listahan.
Ano ang pagkakaiba ng Bubble Sort at Selection Sort?
Kahit na pareho ang bubble sort at selection sort algorithm ay may average na case time complexities na O(n2), ang bubble sort ay halos lahat ng oras ay nahihigitan ng selection sort. Ito ay dahil sa bilang ng mga swap na kailangan ng dalawang algorithm (ang mga bubble sort ay nangangailangan ng mas maraming swaps). Ngunit dahil sa pagiging simple ng bubble sort, ang laki ng code nito ay napakaliit. Ang katatagan ay isa pang pagkakaiba sa dalawang algorithm na ito. Ang isang matatag na algorithm ng pag-uuri, ay isang algorithm ng pag-uuri na nagpapanatili ng pagkakasunud-sunod ng mga talaan kung ang listahan ay naglalaman ng mga elemento na may pantay na halaga. Sa ganoong kahulugan, ang selection sort ay hindi isang stable na algorithm samantalang ang bubble sort ay isang stable na algorithm.
