Bubble Sort

Bubble sort ဆိုတာကတော့ sorting algorithms တွေထဲက တခုဖြစ်ပြီးတော့ sort လုပ်တဲ့နေရာမှာ အအေးခွက်ထဲက bubble လေးတွေလို အပေါ်ကို တက်တက်သွားတဲ့ သဘောတရားကို အခြေခံထားတာပဲ ဖြစ်ပါတယ်။ အအေးခွက်ထဲက bubble လေးတွေလိုမျိုး အကြီးဆုံး value တွေလဲ တခုပြီးတခု အပေါ်ကိုတက် (အနောက်ကိုပို့) သွားတာမျိုးပဲ ဖြစ်ပါတယ်။

သဘောတရားအားဖြင့် အရမ်းကြီး မရှုပ်ထွေးတော့ ဥပမာလေးနဲ့ ကြည့်ကြည့်ရအောင်ပါ။

ဒီမှာကြည့်မယ်ဆို စစချင်း (6, 12) မှာ အကြီးဆုံး 12 က နောက်မှာ ရှိနေတဲ့အတွက် နေရာပြောင်းတာ မလုပ်ပါဘူး။ ဒါပေမယ့် (904, 8) ကို ရောက်တဲ့အချိန်မှာ နေရာမှန်မှာ ရှိမနေတဲ့အတွက် စပြီးတော့ ရွှေ့ရပါပြီ။ 904 က array ထဲမှာ အကြီးဆုံး ဖြစ်နေတဲ့အတွက် နောက်ဆုံးရောက်တဲ့အထိ ရွှေ့သွားရပါမယ်။ ဘေးချင်းကပ်မှာရှိတဲ့ value ၂ခုချင်းစီကို ယှဥ်ပြီးတော့ ရွှေ့သွားတာကို တွေ့နိုင်ပါတယ်။ ဒီ loop အဆုံးမှာတော့ အကြီးဆုံးဖြစ်တဲ့ 904 က နေရာမှန်ကို ရောက်သွားပါပြီ။ ဆက်ပြီးတော့ နောက်ထပ် အကြီးဆုံး value ကို ရှာပြီး စီပါမယ်။

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

Theory ပိုင်းပြောပြီးပြီဆိုတော့ code အနေနဲ့ ဘယ်လိုရေးမလဲ ကြည့်ကြည့်ရအောင်ပါ။

const bubbleSort = (input) => {
  const n = input.length;
  let i, j, temp;
  for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - i - 1; j++) {
      if (input[j] > input[j + 1]) {
        temp = input[j];
        input[j] = input[j + 1];
        input[j + 1] = temp;
      }
    }
  }
  return input;
};

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

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

Time Complexity

တကယ်လို့ input array က စီပြီးသား ဖြစ်နေခဲ့ရင် value တွေကို swap လုပ်ဖို့ လိုနေတော့မှာ မဟုတ်ပါဘူး။ ဒီလို best case အခြေအနေမှာဆိုရင်တော့ time complexity O(n) ကို ရရှိမှာ ဖြစ်ပါတယ်။ best case မဟုတ်တဲ့ အခြေအနေတွေမှာဆိုရင်တော့ နေရာရွှေ့ (swap) တာတွေ လုပ်ရပြီဖြစ်တဲ့အတွက် O(n²) ဖြစ်သွားမှာပဲ ဖြစ်ပါတယ်။

Space Complexity

Bubble sort မှာ array အသစ်အနေနဲ့ create လုပ်သွားတာမျိုး မရှိဘဲ input array ကိုပဲ နေရာရွှေ့တာတွေ လုပ်သွားတာ ဖြစ်တဲ့အတွက် နေရာအသစ် ယူသွားတာမျိုး မရှိပါဘူး။ အခြား value တွေဖြစ်တဲ့ n, i, j, temp တွေကလဲ constant space တွေ ဖြစ်တဲ့အတွက် space complexity O(1) ကို ရရှိမှာပဲ ဖြစ်ပါတယ်။