Selection Sort

Selection sort ဆိုတာကတော့ ပေးလိုက်တဲ့ input array ရဲ့ အငယ်ဆုံး (သို့) အကြီးဆုံး value ကို မှတ်သားပြီး ရွှေ့သွားတဲ့ sorting algorithm တခုပဲ ဖြစ်ပါတယ်။ ပေးလိုက်တဲ့ input array ကို နေရာတခုချင်းစီအလိုက် loop ပတ်ပြီးတော့ သူ့နေရာမှာ ရှိသင့်တဲ့ အငယ်ဆုံး value ကို ရှာသွားတဲ့ သဘောပဲ ဖြစ်ပါတယ်။ သူ့နေရာမှာ ရှိသင့်တဲ့ အငယ်ဆုံး value ကို ရပြီဆိုရင်တော့ နေရာရွှေ့ပြီး sort လုပ်ပြီးတဲ့ အစိတ်အပိုင်းအဖြစ် သတ်မှတ်ပါတယ်။ insertion sort နဲ့ အနည်းငယ် ဆင်သယောင် ရှိပေမယ့် insertion sort က အငယ်ဆုံး/အကြီးဆုံး အဲ့လိုမျိုးတွေကို ရှာတာမဟုတ်ဘဲ လက်ရှိ value ရဲ့ ရှိသင့်တဲ့နေရာကို ရှာသွားတာမျိုး ဖြစ်ပါတယ်။ insertion sort အကြောင်းကို ဒီ article ထဲမှာ လေ့လာလို့ရပါတယ်။

Insertion Sort

Insertion sort က ဘာနဲ့ တူသလဲဆို ကျွန်တော်တို့ စာကြည့်တိုက်တွေမှာ စာအုပ်တွေစီတာနဲ့ သွားတူပါတယ်။ စာအုပ်စင်တခုမှာ စာအုပ်တွေကို alphabetical စီတာနဲ့ တွဲပြီး မြင်ကြ

Arkar's BlogArkar Min Tun

အရင်ဆုံး input array ကို အခုလိုမျိုး ပေးလိုက်တယ်ဆိုပါစို့။

စစချင်း ဝင်လာတဲ့ array ဖြစ်တဲ့အတွက် array တခုလုံးမှာ စီထားပြီးသား မရှိဘူးလို့ သတ်မှတ်ပါမယ်။ ပထမဆုံး index 0 (zero) နေရမှာ ရှိသင့်တဲ့ အငယ်ဆုံး value ကို ရှာပါမယ်။ ဒီနေရာမှာ ငယ်ရာကနေ ကြီးရာကို သွားချင်တာမျိုး ဖြစ်တာကြောင့် အငယ်ဆုံးကို ရှာတာပဲ ဖြစ်ပါတယ်။ တကယ်လို့ ကြီးရာကနေ ငယ်ရာကို သွားချင်တယ်ဆိုရင်တော့ အကြီးဆုံး value ကို ရှာရမှာပဲ ဖြစ်ပါတယ်။

ပေးထားတဲ့ input array မှာ အငယ်ဆုံး value ဖြစ်တဲ့ 2 ကို တွေ့ပြီဆို လက်ရှိ စီဖို့ ကြိုးစားနေတဲ့ index ဖြစ်တဲ့ index 0 (zero) နဲ့ နေရာချင်း ပြောင်းလိုက်ပါမယ်။ ပြောင်းပြီးသွားရင်တော့ index 0 (zero) အတွက် sort လုပ်ပြီးသား ဖြစ်ပါပြီ။

ရှေ့ဆက်ပြီး index 1 နေရာအတွက် သူ့မှာ ရှိရမယ့် အငယ်ဆုံး value ကို ရှာပါမယ်။

ခုနကတင် ရွှေ့လိုက်တဲ့ 6 က index 1 နေရာမှာ ရှိသင့်တဲ့ value ဖြစ်နေတဲ့အတွက် သူ့ကို index 1 နေရာမှာ ရှိတဲ့ 12 နဲ့ နေရာရွှေ့လိုက်ပါမယ်။

ဒီတူညီတဲ့ logic နဲ့ပဲ တနေရာပြီး တနေရာ ရွှေ့သွားပြီး စီသွားပါမယ်။

ဒီလိုမျိုး အဆင့်လိုက် လုပ်သွားပြီးရင်တော့ စီထားပြီးသား (sorted) array ကို ရရှိမှာပဲ ဖြစ်ပါတယ်။

Code အနေနဲ့ ဘယ်လို ရေးမလဲ ကြည့်ကြည့်ရအောင်ပါ။

const selectionSort = (input) => {
  const n = input.length;
  let i, j, minIndex, temp;
  for (i = 0; i < n - 1; i++) {
    // Find the minimum value index
    minIndex = i;
    for (j = i + 1; j < n; j++) {
      if (input[j] < input[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the min value with the current i value
    temp = input[minIndex];
    input[minIndex] = input[i];
    input[i] = temp;
  }

  return input;
};

let items = [6, 12, 904, 8, 123, 45, 34, 2, 51];
console.log(selectionSort(items));

[2, 6, 8, 12, 34, 45, 51, 123, 904]

Time Complexity

ဘယ်လိုအခြေအနေမျိုးပဲ ဖြစ်နေပါစေ input array ကို ၂ခါစီ traverse လုပ်ရတဲ့ algorithm မျိုးပဲ ဖြစ်ပါတယ်။ လက်ရှိ နေရာကို မှတ်ပြီးတာနဲ့ array ကို ပတ်ပြီးတော့ အငယ်ဆုံး ဘယ်သူရှိလဲ လိုက်ရှာရတာမျိုး ဖြစ်တဲ့အတွက် ပုံမှန် ပတ်တာနဲ့ အငယ်ဆုံး ရှာဖို့ ပတ်တာနဲ့ ၂ခု လုပ်ဆောင်ရပါတယ်။ နေရာတနေရာစီတိုင်းအတွက် array ကို ပတ်ပြီး ရှာသွားရတာ ဖြစ်တဲ့အတွက် time complexity အနေနဲ့ O(n²) ကို ရရှိမှာပဲ ဖြစ်ပါတယ်။

Space Complexity

Space complexity အနေနဲ့ကတော့ ဝင်လာတဲ့ input array ကိုပဲ နေရာ swap တာတွေ လုပ်သွားတာဖြစ်တဲ့ အတွက် ထပ်ပြီးတော့ array ဆောက်တာမျိုး မရှိပါဘူး။ တခြား variable ဖြစ်တဲ့ i, j, minIndex, temp တွေကလဲ constant space တွေဖြစ်တဲ့အတွက် space complexity အနေနဲ့ O(1) ကို ရရှိမှာပဲ ဖြစ်ပါတယ်။