Insertion Sort

Insertion sort က ဘာနဲ့ တူသလဲဆို ကျွန်တော်တို့ စာကြည့်တိုက်တွေမှာ စာအုပ်တွေစီတာနဲ့ သွားတူပါတယ်။ စာအုပ်စင်တခုမှာ စာအုပ်တွေကို alphabetical စီတာနဲ့ တွဲပြီး မြင်ကြည့်မယ်ဆို လွယ်ကူပါတယ်။ စာအုပ်တစ်အုပ်ကို သူ့နေရာတကျ စီချင်တဲ့အခါ စာအုပ်ရဲ့ alphabet ကို ကျွန်တော်တို့ ကြည့်ပြီး ထုတ်ထားလိုက်မယ်။ ပြီးသွားရင်တော့ အနီးဆုံး ကပ်ရပ်က စာအုပ်ရဲ့ alphabet ကို ကြည့်ပြီး ကျွန်တော်တို့ စီချင်တဲ့ စာအုပ်က သူ့ရှေ့မှာ လာသင့်သလား နောက်မှာ လာသင့်သလား ဆုံးဖြတ်ပါတယ်။ တကယ်လို့ နောက်မှာ လာသင့်တယ်ဆိုရင်တော့ လက်ရှိနေရာမှာ ထည့်ထားလိုက်မယ်။ ရှေ့မှာ လာသင့်တယ်ဆိုရင်တော့ ရှေ့ကပ်ရပ်မှာ ရှိနေတဲ့ စာအုပ်ကို ထပ်ပြီး ကြည့်သွားပါမယ်။ ဒီလိုနဲ့ ကပ်ရပ်မှာရှိတဲ့ စာအုပ်ကို ကြည့်သွားရင်း အခု စာအုပ် ရှိသင့်တဲ့ နေရာကို ရောက်တဲ့အထိ ယှဥ်ကြည့်သွားပါမယ်။ ရောက်ပြီဆိုရင်တော့ အဲ့နေရာမှာ ထည့် (insert) လုပ်လိုက်ပါမယ်။

Value တခုကို သူ့နေရာတကျ စီချင်တဲ့အခါ တခြား value တွေနဲ့ လိုက်ပြီး ယှဥ်ကြည့်ပြီး နေရာ ရွှေ့နေရတာဖြစ်လို့ အရမ်းကြီး performance ကောင်းတဲ့ sorting algorithm တော့ ဟုတ်မနေပါဘူး။ value အနည်းငယ်ကို စီချင်ရင်တော့ သုံးလို့ အဆင်ပြေပါတယ်။ Value တွေများရင်တော့ ဒီ့ထက် ပိုကောင်းတဲ့ algorithm တွေကို ရွေးသင့်ပါတယ်။

ဒီတော့ algorithm ရေးသားတာကို ကြည့်ကြည့်ရအောင်ပါ။

const insertionSort = (arr) => {
  let i, j, key;
  
  for (i = 1; i < arr.length; i++) {
    // Step 1: Take out current value
    key = arr[i];
    // Step 2: Get the index of previous value
    j = i - 1;

    // Step 3: Compare and move one place
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    // Step 4: Put the value taken out in correct place
    arr[j + 1] = key;
  }
  
  return arr;
};

let arr = [15, 13, 42, 43, 8, 22, 3, 10, 11, 6];
console.log(insertionSort(arr));

[3, 6, 8, 10, 11, 13, 15, 22, 42, 43]

ကျွန်တော်တို့ input value တွေကို loop သွားမှာ ဖြစ်တဲ့အတွက် for loop တခု တည်ဆောက်လိုက်ပါမယ်။ ဒီနေရာမှာ value ၂ ခုစီကို ယှဥ်ယှဥ်ပြီး စစ်သွားမှာ ဖြစ်တဲ့အတွက် index 1 ကနေ စပါတယ်။

Loop ထဲမှာ ပထမဆုံး အဆင့်အနေနဲ့ လက်ရှိရောက်နေတဲ့ index ရဲ့ value ကို key ဆိုတဲ့ variable ကို ထည့်ထားလိုက်ပါမယ်။ တကယ်လို့ ရွှေ့ဖို့လိုတဲ့အခါ ရောက်သင့်တဲ့နေရာမှာ ဒီ value ကို သွင်းလိုက်မှာပဲ ဖြစ်ပါတယ်။

ဒုတိယအဆင့်အနေနဲ့ လက်ရှိ index ရဲ့ ရှေ့က index ကို တွက်ယူပါမယ်။ စစချင်းမှာ index 1 ကစတာဖြစ်တဲ့အတွက် သူ့ရဲ့အရှေ့ကဆိုရင် index 0 ကို ရမှာပဲ ဖြစ်ပါတယ်။ ဒီမှာ index ကို variable နဲ့မှတ်တာက insertion sort မှာ ရှေ့ကို တိုးတိုးသွားမှာ ဖြစ်တဲ့အတွက် ရွှေ့နေတဲ့ index တွေကို သိမ်းထားဖို့ value သတ်မှတ်လိုက်တာပဲ ဖြစ်ပါတယ်။

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

ရွှေ့စရာတွေပြီးသွားပြီဆိုရင်တော့ လက်ရှိရောက်နေတဲ့ j index ရဲ့နေရာကို တခုတိုးပြီးတော့ ကျွန်တော်တို့ key ထဲမှာ သိမ်းထားတဲ့ value ကို ထည့်ပေးလိုက်ပါမယ်။ တခုတိုးပေးရတာက အပေါ်က while loop မှာ နောက်ဆုံးအဆင့်မှာ j = j - 1 ဆိုတော့ တခုလျော့ပြီး ထွက်လာမှာ ဖြစ်လို့ပါ။

Time Complexity

Best case - Input value တွေက စီပြီးသားအနေနဲ့ ဝင်လာတာဆိုရင်တော့ ကျွန်တော်တို့တွေ best case time complexity ကို ရရှိမှာပဲ ဖြစ်ပါတယ်။ value တွေကို ရွှေ့တာတွေ လုပ်စရာမလိုတော့ဘဲ value တွေကိုပဲ traverse လုပ်သွားမှာ ဖြစ်ပါတယ်။​ ဒီတော့ complexity အနေနဲ့ O(n) ကို ရရှိမှာပဲ ဖြစ်ပါတယ်။

Average Case - တကယ်လို့ input value တွေက random အစီအစဥ်မကျတကျ ဖြစ်နေတယ်ဆိုရင်တော့ average case time complexity ကို ရရှိမှာပဲ ဖြစ်ပါတယ်။ တချို့ value တွေကို ရွှေ့ဖို့လိုပြီး တချို့ကိုတော့ ရွှေ့ဖို့ မလိုတာ ဖြစ်နိုင်ပါတယ်။ ဒီအခြေအနေမှာတော့ complexity O(n²) ကို ရရှိမှာ ဖြစ်ပါတယ်။

Worst Case - ဒါကတော့ input value က လိုချင်တဲ့ sorting order နဲ့ ပြောင်းပြန်ဝင်လာခဲ့ရင် value တွေအကုန်လုံးကို sort လုပ်ဖို့ လိုတဲ့ အခြေအနေမျိုး ဖြစ်ပါတယ်။ အစကနေ အဆုံးအထိ value တွေကို နေရာတွေ ရွှေ့သွားရမှာပဲ ဖြစ်ပါတယ်။ ဒီလိုအခြေအနေမှာလဲ complexity က O(n²) ကို ရရှိမှာ ဖြစ်ပါတယ်။

Space Complexity

Input value အပြင် ကျွန်တော်တို့မှာ သိမ်းသွားတာက i, j, နဲ့ key ၃ ခုပဲ ရှိတဲ့အတွက် space complexity အနေနဲ့ O(1) ကို ရရှိမှာပဲ​ဖြစ်ပါတယ်။