Bubble Sort vs Insertion 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 insertion sort ay isa ring sorting algorithm, na nagpapatakbo sa pamamagitan ng paglalagay ng elemento sa listahan ng input sa tamang posisyon sa isang listahan na nakaayos na. Paulit-ulit na inilalapat ang prosesong ito hanggang sa maiayos ang listahan.
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 pinapalitan 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 napaka-simpleng 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 Insertion Sort?
Ang Insertion sort ay isa pang algorithm sa pag-uuri, na gumagana sa pamamagitan ng paglalagay ng elemento sa listahan ng input sa tamang posisyon sa isang listahan (na pinagsunod-sunod na). Ang prosesong ito ay inilapat nang paulit-ulit hanggang ang listahan ay pinagbukud-bukod. Sa insertion sort, ang pag-uuri ay isinasagawa sa lugar. Samakatuwid pagkatapos ng pag-ulit ng algorithm, ang unang i+1 na mga entry sa listahan ay pagbubukud-bukod at ang natitirang bahagi ng listahan ay aalisin sa pagkakasunud-sunod. Sa bawat pag-ulit, ang unang elemento sa unsorted na bahagi ng listahan ay kukunin at ilalagay sa tamang lugar sa pinagsunod-sunod na seksyon ng listahan. Ang insertion sort ay may average na case time complexity na O(n2). Dahil dito, hindi rin angkop ang insertion sort para sa pag-uuri ng malalaking listahan.
Ano ang pagkakaiba ng Bubble Sort at Insertion Sort?
Kahit na ang bubble sort at insertion sort algorithm ay may average na case time complex na O(n2), ang bubble sort ay halos lahat ng oras ay nahihigitan ng insertion 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. Mayroon ding variant ng insertion sort na tinatawag na shell sort, na may time complexity na O(n3/2), na magpapahintulot na magamit ito nang praktikal. Higit pa rito, ang insertion sort ay napakahusay para sa pag-uuri ng mga listahang “halos napag-uri-uriin,” kung ihahambing sa bubble sort.
