Sorting Algorithms (ဒေတာကို အစဉ်လိုက် စီတဲ့ အယ်လ်ဂိုရီသမ်များ)

B2.4.3: Construct and trace algorithms to implement bubble sort and selection sort, evaluating their time and space complexities.
မြန်မာလို: bubble sort (ဘေးချင်းကပ် တန်ဖိုးတွေကို လဲပြီး စီခြင်း) နဲ့ selection sort (အငယ်ဆုံးကို ရှာပြီး နေရာချ စီခြင်း) ကို လုပ်ဆောင်တဲ့ algorithm (အယ်လ်ဂိုရီသမ်၊ ပြဿနာကို အဆင့်ဆင့် ဖြေရှင်းတဲ့ နည်းလမ်း) တွေကို construct (ကိုယ်တိုင် ရေးဖွဲ့တည်ဆောက်) လုပ်နိုင်ရမယ်၊ trace (algorithm လုပ်ဆောင်ပုံကို တစ်ဆင့်ချင်း လိုက်ပြီး မှတ်) လုပ်နိုင်ရမယ်။ ပြီးတော့ အဲဒီ algorithm တွေရဲ့ time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) နဲ့ space complexity (input ကြီးလာရင် memory လိုအပ်ချက် တိုးပုံ) ကို evaluate (အားသာချက်နဲ့ အားနည်းချက်တွေကို ချိန်ဆပြီး အကဲဖြတ်) လုပ်နိုင်ရမယ်။

  • Bubble sort: အစဉ်မှားနေတဲ့ ဘေးချင်းကပ် တန်ဖိုးတွေကို swap (တန်ဖိုးနှစ်ခု နေရာချင်း လဲတာ) လုပ်သွားလို့ pass (ဒေတာကို တစ်ခေါက် ဖြတ်ကြည့်တာ) တစ်ခါစီမှာ မစီရသေးတဲ့ တန်ဖိုးတွေထဲက အကြီးဆုံးက အဆုံးကို ရောက်သွားပါတယ်။
  • Optimised bubble sort: swap တစ်ခုမှ မရှိတဲ့ pass တစ်ခါ ပြီးတာနဲ့ swapped flag (တစ်ခုခု ဖြစ်ခဲ့လား true/false နဲ့ မှတ်ထားတဲ့ အမှတ်အသား) က sort ကို ရပ်ပေးပါတယ်။
  • Selection sort: pass တစ်ခါစီမှာ မစီရသေးတဲ့ element (အစုထဲက အချက်) တွေထဲက အငယ်ဆုံးကို သူ့နေရာမှန်ဆီ swap လုပ်ထည့်ပါတယ်။ Swap နည်းပေမယ့် early exit (စောစော ရပ်တာ) မရှိပါဘူး။
  • Bubble sort နဲ့ selection sort နှိုင်းယှဉ်ချက်: စီလုနီးပါး ဖြစ်နေတဲ့ ဒေတာအတွက် bubble sort က သင့်တော်ပြီး swap လုပ်ရတာ ကုန်ကျမှု များတဲ့အခါ selection sort က သင့်တော်ပါတယ်။ ဒေတာ အများကြီးအတွက်တော့ ဘယ်တစ်ခုမှ မသင့်တော်ပါဘူး။

အဓိက အယူအဆများ

ကိုယ်တိုင် စမ်းကြည့်ပါ: အဆင့်ဆင့် ပြပေးတဲ့ visualizer (algorithm အလုပ်လုပ်ပုံကို ပုံနဲ့ ပြပေးတဲ့ tool) က ဒီ algorithm တွေကို comparison (တန်ဖိုးနှစ်ခု နှိုင်းယှဉ်တာ) တစ်ခုချင်းစီ လိုက်ပြပေးပါတယ်။ နောက်တစ်ဆင့်မှာ ဘာဖြစ်မလဲ ကြိုခန့်မှန်းရတဲ့ mode လည်း ပါပြီး အဲဒါက IB စာမေးပွဲမှာ ပါတဲ့ trace table (variable တန်ဖိုးတွေကို အဆင့်ဆင့် မှတ်တဲ့ ဇယား) တွေနဲ့ ပုံစံတူပါတယ်။

Sorting algorithm (ဒေတာကို အစဉ်လိုက် စီပေးတဲ့ algorithm) က array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) ထဲက element တွေကို ascending (ငယ်စဉ်ကြီးလိုက်) ဒါမှမဟုတ် descending (ကြီးစဉ်ငယ်လိုက်) လို သတ်မှတ်ထားတဲ့ အစဉ်တစ်ခုအတိုင်း ပြန်စီပေးပါတယ်။ IB Computer Science (နိုင်ငံတကာ ကျောင်းတွေမှာ သင်တဲ့ ကွန်ပျူတာသိပ္ပံ သင်ရိုး) မှာ သိရမယ့် sorting algorithm နှစ်ခုကတော့ ဒီနှစ်ခုပါ:

  Bubble Sort Selection Sort
နည်းဗျူဟာ အစဉ်မှားနေတဲ့ ဘေးချင်းကပ် element တွေကို ထပ်ခါထပ်ခါ swap လုပ်တယ် အငယ်ဆုံး element ကို ရှာပြီး မှန်ကန်တဲ့ နေရာကို ရွှေ့တယ်
Pass အရေအတွက် Array ပေါ်မှာ pass အများဆုံး n-1 ခါ Pass n-1 ခါ အတိအကျ
စောစော ရပ်နိုင်လား ရပါတယ်၊ optimisation flag (ပိုမြန်အောင် ထည့်ထားတဲ့ flag) သုံးရင် မရပါဘူး၊ pass အားလုံးကို အမြဲ လုပ်တယ်
Time complexity worst case (အဆိုးဆုံး အခြေအနေ) နဲ့ average case (ပျမ်းမျှ အခြေအနေ) မှာ O(n²)၊ best case (အကောင်းဆုံး အခြေအနေ) မှာ O(n) (optimise လုပ်ထားရင်) Case အားလုံးမှာ O(n²)
Space complexity O(1): in place (မူလ array ထဲမှာပဲ) စီတယ် O(1): in place စီတယ်

Algorithm နှစ်ခုလုံးက in place စီပါတယ်။ ဆိုလိုတာက array အသစ် မဆောက်ဘဲ မူလ array ကိုပဲ နေရာပြန်စီတာပါ။ ဒါကြောင့် space complexity က O(1) ဖြစ်ပါတယ်: array ဘယ်လောက်ကြီးကြီး variable (တန်ဖိုး သိမ်းထားတဲ့ နာမည်ပေးထားတဲ့ နေရာ) အနည်းငယ်ပဲ ထပ်လိုပါတယ်။

String အကြောင်း အမြန် သတိပေးချက်: ဒီစာမျက်နှာက ဥပမာတွေမှာ int array တွေကို < နဲ့ > သုံးပြီး စီထားပါတယ်။ String (စာသား) array တွေကို စီတဲ့အခါမှာတော့ အဲဒီအစား .compareTo() ကို သုံးပါ။ ပထမ string က ဒုတိယ string ထက် အက္ခရာစဉ်အရ ရှေ့မှာ လာရင် အနုတ်ကိန်း၊ တူရင် သုည၊ နောက်မှာ လာရင် အပေါင်းကိန်းကို ပြန်ပေးပါတယ်။ အောက်က Sorting Strings အပိုင်းကို ကြည့်ပါ၊ ဒါမှမဟုတ် အပြည့်အစုံကို Strings မှာ ကြည့်ပါ။

Bubble Sort (ဘေးချင်းကပ် တန်ဖိုးတွေကို လဲပြီး စီခြင်း)

အလုပ်လုပ်ပုံ

Bubble sort က adjacent element (ဘေးချင်းကပ် element) နှစ်ခုကို နှိုင်းယှဉ်ပြီး အစဉ်မှားနေရင် swap လုပ်ပါတယ်။ Array တစ်ခုလုံးကို pass တစ်ခါ ဖြတ်ပြီးတိုင်း မစီရသေးတဲ့ element တွေထဲက အကြီးဆုံးက ရေပူဖောင်းလို “bubble up” ဖြစ်ပြီး အဆုံးက သူ့နေရာမှန်ကို ရောက်သွားပါတယ်။

Array arr ရဲ့ index 0 ကနေ 4 အထိမှာ 5, 3, 8, 1, 2 ရှိပါတယ်။ Pass 1 က ဘယ်ဘက်ကနေ စပြီး ဘေးချင်းကပ် အတွဲတိုင်းကို နှိုင်းယှဉ်ပါတယ်။ Before pass 1 Compare neighbours, left to right. 0 1 2 3 4 5 3 8 1 2 j က 0 ဖြစ်လို့ arr[0] နဲ့ arr[1] ကို နှိုင်းယှဉ်ပါတယ်။ 5 က 3 ထက် ကြီးလို့ swap လုပ်ပါတယ်: အခု index 0 မှာ 3၊ index 1 မှာ 5 ရှိပါတယ်။ Array က အခု 3, 5, 8, 1, 2 ဖြစ်ပါတယ်။ 1 5 > 3, so swap j = 0: compare arr[0] and arr[1] 0 1 2 3 4 3 5 8 1 2 j j + 1 j က 1 ဖြစ်လို့ arr[1] နဲ့ arr[2] ကို နှိုင်းယှဉ်ပါတယ်။ 5 က 8 ထက် မကြီးလို့ ဘာမှ မရွှေ့ပါဘူး။ Array က အခု 3, 5, 8, 1, 2 ဖြစ်ပါတယ်။ 2 5 > 8? No, so no swap j = 1: compare arr[1] and arr[2] 0 1 2 3 4 3 5 8 1 2 j j + 1 j က 2 ဖြစ်လို့ arr[2] နဲ့ arr[3] ကို နှိုင်းယှဉ်ပါတယ်။ 8 က 1 ထက် ကြီးလို့ swap လုပ်ပါတယ်: အခု index 2 မှာ 1၊ index 3 မှာ 8 ရှိပါတယ်။ Array က အခု 3, 5, 1, 8, 2 ဖြစ်ပါတယ်။ 3 8 > 1, so swap j = 2: compare arr[2] and arr[3] 0 1 2 3 4 3 5 1 8 2 j j + 1 j က 3 ဖြစ်လို့ arr[3] နဲ့ arr[4] ကို နှိုင်းယှဉ်ပါတယ်။ 8 က 2 ထက် ကြီးလို့ swap လုပ်ပါတယ်: အခု index 3 မှာ 2၊ index 4 မှာ 8 ရှိပါတယ်။ Array က အခု 3, 5, 1, 2, 8 ဖြစ်ပါတယ်။ 8 က အဆုံးမှာ သူ့ရဲ့ နောက်ဆုံး နေရာကို ရောက်ပါပြီ။ 4 8 > 2, so swap j = 3: compare arr[3] and arr[4] 0 1 2 3 4 3 5 1 2 8 j j + 1 final place

j နဲ့ j + 1 က နှိုင်းယှဉ်နေတဲ့ အတွဲကို ညွှန်ပြပါတယ်။

အရိပ်ပါတဲ့ အကွက်က swap ကြောင့် တန်ဖိုးအသစ် ရလာတဲ့ အကွက်ပါ။

ကွင်းခတ်ထားတဲ့ မျဉ်းက နောက်ဆုံး နေရာ ရောက်ပြီးသား တန်ဖိုးတွေကို ပြပါတယ်။

[5, 3, 8, 1, 2] ပေါ်မှာ လုပ်တဲ့ pass 1 ဖြစ်ပြီး အောက်က trace table ရဲ့ ပထမ အတန်းနဲ့ တူပါတယ်။ Comparison လေးခု ပြီးတဲ့အခါ အကြီးဆုံး တန်ဖိုး 8 က အဆုံးကို ရောက်သွားပါတယ်။

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “Before pass 1” က pass 1 မစခင်၊ “Compare neighbours, left to right” က ဘယ်ကနေ ညာကို ဘေးချင်းကပ် တန်ဖိုးတွေကို နှိုင်းယှဉ်ပါ၊ “compare arr[0] and arr[1]” က arr[0] နဲ့ arr[1] ကို နှိုင်းယှဉ်ပါ၊ “so swap” က ဒါကြောင့် swap လုပ်တယ်၊ “No, so no swap” က မကြီးလို့ swap မလုပ်ဘူး၊ “final place” က နောက်ဆုံး နေရာကို ရောက်ပြီလို့ အဓိပ္ပာယ်ရပါတယ်။

Pass တစ်ခါစီက element တစ်ခုကို သူ့ရဲ့ နောက်ဆုံး နေရာမှာ ထပ်ထားပေးတာမို့ နောက် pass တစ်ခါစီမှာ စစ်ရမယ့် element တစ်ခုစီ လျော့သွားပါတယ်။

သတိပြုရမယ့် အချက်များ:

  • Pass 1 ပြီးရင် အကြီးဆုံး element က အဆုံးမှာ ရှိနေပါတယ်
  • Pass 2 ပြီးရင် အကြီးဆုံး element နှစ်ခုက သူတို့နေရာ ရောက်နေပါပြီ
  • Pass k ပြီးရင် အကြီးဆုံး element k ခုက သူတို့နေရာ ရောက်နေပါပြီ
  • Element n ခုအတွက် pass အများဆုံး n-1 ခါ လိုပါတယ်

main ထဲမှာ တိုက်ရိုက် ရေးထားတဲ့ Java code 

int[] arr = {53, 18, 71, 26, 40, 15, 84};
int n = arr.length;

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

// Print sorted array
for (int i = 0; i < n; i++) {
    System.out.print(arr[i] + " ");
}

arr = [53, 18, 71, 26, 40, 15, 84]
n = len(arr)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if arr[j] > arr[j + 1]:
            temp = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = temp

# Print sorted array
for i in range(n):
    print(arr[i], end=" ")

Output (program က ထုတ်ပေးတဲ့ ရလဒ်):

15 18 26 40 53 71 84

Inner loop (အတွင်းဘက် loop) က n - 1 အထိ မဟုတ်ဘဲ n - 1 - i အထိပဲ သွားပါတယ်။ Pass တစ်ခါပြီးတိုင်း နောက်ဆုံးက element i ခုက စီပြီးသား ဖြစ်နေလို့ အဲဒါတွေကို ထပ်နှိုင်းယှဉ်စရာ မလိုပါဘူး။ ဒါဟာ ကျောင်းသားတွေ မကြာခဏ လွတ်သွားတတ်တဲ့ အရေးကြီးတဲ့ optimisation တစ်ခုပါ။

Optimised Bubble Sort: early exit (စီပြီးတာနဲ့ စောစော ရပ်နိုင်အောင် ပြင်ထားတဲ့ bubble sort)

Pass တစ်ခါမှာ swap တစ်ခုမှ မဖြစ်ရင် array က စီပြီးသား ဖြစ်နေလို့ စောစော ရပ်လို့ ရပါတယ်။ ဒါကို boolean (true ဒါမှမဟုတ် false တန်ဖိုးပဲ ယူတဲ့) flag တစ်ခုနဲ့ လုပ်ပါတယ်:

int[] arr = {53, 18, 71, 26, 40, 15, 84};
int n = arr.length;
boolean swapped = true;

for (int i = 0; i < n - 1 && swapped; i++) {
    swapped = false;

    for (int j = 0; j < n - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            swapped = true;
        }
    }
}

arr = [53, 18, 71, 26, 40, 15, 84]
n = len(arr)
swapped = True

# Python's for loop cannot carry the "and swapped" condition,
# so the outer counted loop becomes a while loop with a counter.
i = 0
while i < n - 1 and swapped == True:
    swapped = False

    for j in range(n - 1 - i):
        if arr[j] > arr[j + 1]:
            temp = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = temp
            swapped = True

    i = i + 1

Loop က ပထမအကြိမ် အလုပ်လုပ်အောင် swapped flag ကို အစမှာ true လို့ ထားပါတယ်။ Pass တစ်ခါစတိုင်း အဲဒါကို false ပြန်ထားပြီး swap တစ်ခု ဖြစ်မှသာ true ပြန်ပြောင်းပါတယ်။ Pass တစ်ခါလုံး swap မရှိဘဲ ပြီးသွားရင် swapped က false အတိုင်း ကျန်နေပြီး loop condition (loop ဆက်လုပ်မလား စစ်တဲ့ အခြေအနေ) i < n - 1 && swapped က loop ကို သဘာဝကျကျ ရပ်ပေးပါတယ်။ ဒါကြောင့် best case က O(n) ဖြစ်ပါတယ်: array က စီပြီးသား ဆိုရင် pass တစ်ခါပဲ လိုပါတယ်။ Flag မပါရင်တော့ bubble sort က စီပြီးသား ဒေတာပေါ်မှာတောင် pass n-1 ခါ အမြဲ လုပ်ပါတယ်။

Bubble Sort ကို {5, 3, 8, 1, 2} ပေါ်မှာ trace လုပ်ခြင်း

Pass Comparison များ Swap များ Pass ပြီးနောက် array
1 (5,3) (5,8) (8,1) (8,2) 5↔3, 8↔1, 8↔2 [3, 5, 1, 2, 8]
2 (3,5) (5,1) (5,2) 5↔1, 5↔2 [3, 1, 2, 5, 8]
3 (3,1) (3,2) 3↔1, 3↔2 [1, 2, 3, 5, 8]
4 (1,2) မရှိ [1, 2, 3, 5, 8] ✓

Comparison စုစုပေါင်း: 4 + 3 + 2 + 1 = 10။ Swap စုစုပေါင်း: 7။

Complexity ကို ခွဲခြမ်းစိတ်ဖြာခြင်း

Case Time ဖြစ်တဲ့ အခြေအနေ
Best O(n) Array က စီပြီးသား ဖြစ်နေရင် (swapped flag နဲ့ဆိုရင် pass တစ်ခါ၊ swap မရှိ)
Average O(n²) ကျပန်း အစဉ်
Worst O(n²) ပြောင်းပြန် စီထားရင်: အတွဲတိုင်းကို swap လုပ်ရတယ်
Space O(1) temp၊ i၊ j၊ swapped ကိုပဲ သုံးတယ်: ထပ်လိုတဲ့ memory (မှတ်ဉာဏ်) က constant (array အရွယ် ဘယ်လောက်ပဲ ဖြစ်ဖြစ် မပြောင်းဘူး)

Worst case မှာ comparison အရေအတွက်က n(n-1)/2 ဖြစ်ပါတယ်။ ဥပမာ element 5 ခုဆိုရင် 4 + 3 + 2 + 1 = 10 comparison ဖြစ်ပါတယ်။ ဘာလို့လဲဆိုတော့ outer loop (အပြင်ဘက် loop) က n-1 ကြိမ် ပတ်ပြီး pass တစ်ခါစီမှာ inner loop က n-1-i ကြိမ် ပတ်လို့ပါ။ ပေါင်းလဒ် 1 + 2 + … + (n-1) = n(n-1)/2 ဖြစ်ပြီး အဲဒါကို ရိုးရှင်းအောင် ချုံ့လိုက်ရင် O(n²) ရပါတယ်။

Bubble Sort Algorithm Explained
Bubble Sort Algorithm Explained

Watch on YouTube

Bubble Sort Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. Bubble sort က အဆင့်တိုင်းမှာ ဘာကို နှိုင်းယှဉ်သလဲ။

Q2. {7, 2, 5, 1, 9, 3} ပေါ်မှာ bubble sort ရဲ့ ပထမ pass ပြီးတဲ့အခါ ဘယ် element က သူ့နေရာမှန်မှာ ရှိနေတာ သေချာသလဲ။

Q3. Optimised bubble sort မှာ swapped flag ကို ဘာအတွက် သုံးသလဲ။

Q4. Bubble sort ရဲ့ space complexity က ဘာလဲ။

Bubble Sort Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)

{6, 3, 8, 2} ပေါ်မှာ bubble sort ကို trace လုပ်ပါ။ Pass တစ်ခါပြီးတိုင်း array ရဲ့ အခြေအနေကို ဖြည့်ပါ။

Passနေရာ 0နေရာ 1နေရာ 2နေရာ 3Swap အရေအတွက်
အစ 6 3 8 2 -
1
2 8
3 6 8

Bubble Sort Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)

Array ကို ascending order နဲ့ စီပေးတဲ့ bubble sort code ကို ကွက်လပ်တွေ ဖြည့်ပြီး ပြည့်စုံအောင် လုပ်ပါ။

ဒီ algorithm က array ကို pass အကြိမ်ကြိမ် ဖြတ်ပြီး အစဉ်မှားနေတဲ့ ဘေးချင်းကပ် element တွေကို swap လုပ်ပါတယ်။ အကြီးဆုံး element တွေက အဆုံးမှာ စုလာလို့ pass တစ်ခါစီမှာ inner loop က တိုတိုလာပါတယ်။

int[] arr = {42, 15, 8, 23, 4};
int n = arr.length;

for (int i = 0; i < ; i++) {
    for (int j = 0; j < ; j++) {
        if (arr[j] > ) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            ;
        }
    }
}

Bubble Sort Spot the Error (အမှား ရှာခြင်း)

ဒီ bubble sort က run လို့ ရပေမယ့် ထိရောက်မှု မရှိပါဘူး: စီပြီးသား element တွေကို ထပ်စစ်နေပါတယ်။ Bug (code ထဲက အမှား) ရှိတဲ့ line ကို ရွေးပါ၊ ပြီးရင် ပြင်နည်းကို ရွေးပါ။

1int[] arr = {30, 10, 50, 20, 40}; 2int n = arr.length; 3for (int i = 0; i < n - 1; i++) { 4 for (int j = 0; j < n - 1; j++) { 5 if (arr[j] > arr[j + 1]) { 6 int temp = arr[j]; 7 arr[j] = arr[j + 1]; 8 arr[j + 1] = temp; 9 } 10 } 11}

Line 4 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Bubble Sort Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

ဒီ optimised bubble sort က pass ဘယ်နှစ်ခါ လုပ်ရသလဲ ရေတွက်ပါတယ်။ Output အတိအကျ က ဘာလဲ။

int[] arr = {4, 1, 3, 2};
int n = arr.length;
int passes = 0;
boolean swapped = true;
for (int i = 0; i < n - 1 && swapped; i++) {
    swapped = false;
    for (int j = 0; j < n - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            swapped = true;
        }
    }
    passes++;
}
System.out.println("Passes: " + passes);

သင့်အဖြေကို ရိုက်ထည့်ပါ:

Bubble Sort လေ့ကျင့်ခန်းများ

  1. စာရွက်ပေါ်မှာ trace လုပ်ခြင်း။ {9, 5, 1, 4, 3} ပေါ်မှာ bubble sort ကို Trace လုပ်ပါ။ Pass တစ်ခါစီအတွက် array ရဲ့ အခြေအနေကို ရေးပြီး swap အရေအတွက်ကို ရေတွက်ပါ။ စုစုပေါင်း pass ဘယ်နှစ်ခါ လိုသလဲ။

  2. စီပြီးသား array။ (swapped flag ပါတဲ့) optimised bubble sort ကို {1, 2, 3, 4, 5} ပေါ်မှာ run ပါ။ Pass ဘယ်နှစ်ခါ လုပ်သလဲ။ Comparison ဘယ်နှစ်ခု လုပ်သလဲ။ ဒါဟာ ဘာကြောင့် best case ဖြစ်သလဲဆိုတာ Explain (ရှင်းပြပါ)။

  3. ပြောင်းပြန် စီထားတဲ့ array။ {5, 4, 3, 2, 1} ပေါ်မှာ bubble sort ကို Trace လုပ်ပါ။ Comparison နဲ့ swap စုစုပေါင်း အရေအတွက်ကို ရေတွက်ပါ။ ဒါက worst case ဖြစ်ပါတယ်၊ ဘာကြောင့်လဲ Explain လုပ်ပါ။

  4. ကြီးစဉ်ငယ်လိုက် စီခြင်း။ Bubble sort code ကို descending order (အကြီးဆုံးကနေ အငယ်ဆုံး) နဲ့ စီအောင် ပြင်ပါ။ Character (စာလုံး ဒါမှမဟုတ် သင်္ကေတ) တစ်လုံးပဲ ပြောင်းဖို့ လိုပါတယ်။

Selection Sort (အငယ်ဆုံးကို ရှာပြီး နေရာချ စီခြင်း)

အလုပ်လုပ်ပုံ

Selection sort က array ကို ဘယ်ဘက်က sorted part (စီပြီးသား အပိုင်း) နဲ့ ညာဘက်က unsorted part (မစီရသေးတဲ့ အပိုင်း) ဆိုပြီး နှစ်ပိုင်း ခွဲပါတယ်။ Pass တစ်ခါစီမှာ unsorted part ထဲက အငယ်ဆုံး element ကို ရှာပြီး unsorted part ရဲ့ ပထမ element နဲ့ swap လုပ်ပါတယ်။

Array arr ရဲ့ index 0 ကနေ 4 အထိမှာ 5, 3, 8, 1, 2 ရှိပါတယ်။ ဘာမှ မစီရသေးပါဘူး။ Before pass 1 The whole array is unsorted. 0 1 2 3 4 5 3 8 1 2 Pass 1: i က 0 ဖြစ်ပြီး minIndex က 3 ပါ။ Index 3 မှာရှိတဲ့ 1 က index 0 ကနေ 4 အထိထဲမှာ အငယ်ဆုံး ဖြစ်လို့ arr[0] နဲ့ arr[3] ကို swap လုပ်ပါတယ်။ Array က အခု 1, 3, 8, 5, 2 ဖြစ်ပါတယ်။ Index 0 က သူ့ရဲ့ နောက်ဆုံး နေရာကို ရောက်ပါပြီ။ 1 smallest is 1, at index 3 swap arr[0] and arr[3] 0 1 2 3 4 1 3 8 5 2 i minIndex min_index final place Pass 2: i က 1 ဖြစ်ပြီး minIndex က 4 ပါ။ Index 4 မှာရှိတဲ့ 2 က index 1 ကနေ 4 အထိထဲမှာ အငယ်ဆုံး ဖြစ်လို့ arr[1] နဲ့ arr[4] ကို swap လုပ်ပါတယ်။ Array က အခု 1, 2, 8, 5, 3 ဖြစ်ပါတယ်။ Index 0 ကနေ 1 အထိ နောက်ဆုံး နေရာတွေကို ရောက်ပါပြီ။ 2 smallest is 2, at index 4 swap arr[1] and arr[4] 0 1 2 3 4 1 2 8 5 3 i minIndex min_index final place Pass 3: i က 2 ဖြစ်ပြီး minIndex က 4 ပါ။ Index 4 မှာရှိတဲ့ 3 က index 2 ကနေ 4 အထိထဲမှာ အငယ်ဆုံး ဖြစ်လို့ arr[2] နဲ့ arr[4] ကို swap လုပ်ပါတယ်။ Array က အခု 1, 2, 3, 5, 8 ဖြစ်ပါတယ်။ Index 0 ကနေ 2 အထိ နောက်ဆုံး နေရာတွေကို ရောက်ပါပြီ။ 3 smallest is 3, at index 4 swap arr[2] and arr[4] 0 1 2 3 4 1 2 3 5 8 i minIndex min_index final place Pass 4: i က 3 ဖြစ်ပြီး minIndex ကလည်း 3 ပါ။ Index 3 မှာရှိတဲ့ 5 က index 3 ကနေ 4 အထိထဲမှာ အငယ်ဆုံး ဖြစ်လို့ နေရာမှာပဲ ဆက်ရှိပါတယ်။ Array က အခု 1, 2, 3, 5, 8 ဖြစ်ပါတယ်။ တန်ဖိုး ငါးခုလုံး နောက်ဆုံး နေရာတွေကို ရောက်ပါပြီ။ 4 smallest is 5, at index 3 arr[3] is already in place: no move 0 1 2 3 4 1 2 3 5 8 i minIndex min_index all in final place

i က မစီရသေးတဲ့ ပထမ နေရာ ဖြစ်ပြီး minIndexmin_index က အငယ်ဆုံး တန်ဖိုးကို တွေ့တဲ့ နေရာပါ။

အရိပ်ပါတဲ့ အကွက်က swap ကြောင့် တန်ဖိုးအသစ် ရလာတဲ့ အကွက်ပါ။

ကွင်းခတ်ထားတဲ့ မျဉ်းက နောက်ဆုံး နေရာ ရောက်ပြီးသား တန်ဖိုးတွေကို ပြပါတယ်။

Array [5, 3, 8, 1, 2] တစ်ခုတည်းကိုပဲ selection sort နဲ့ စီထားတာပါ: pass တစ်ခါမှာ swap တစ်ခုပဲ လုပ်ပြီး စီပြီးသား အပိုင်းက ဘယ်ဘက်ကနေ တဖြည်းဖြည်း ကြီးလာပါတယ်။

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “The whole array is unsorted” က array တစ်ခုလုံး မစီရသေးဘူး၊ “smallest is 1, at index 3” က အငယ်ဆုံးက 1 ဖြစ်ပြီး index 3 မှာ ရှိတယ်၊ “swap arr[0] and arr[3]” က arr[0] နဲ့ arr[3] ကို swap လုပ်ပါ၊ “arr[3] is already in place: no move” က arr[3] က နေရာမှန်မှာ ရှိပြီးသားမို့ မရွှေ့ဘူး၊ “all in final place” က အားလုံး နောက်ဆုံး နေရာ ရောက်ပြီလို့ အဓိပ္ပာယ်ရပါတယ်။ minIndex ကို Python version မှာ min_index လို့ ရေးပါတယ်။

သတိပြုရမယ့် အချက်များ:

  • Pass တစ်ခါစီမှာ swap တစ်ခု အတိအကျ လုပ်ပါတယ် (အငယ်ဆုံးက သူ့နေရာမှာ ရှိပြီးသားဆိုရင်တော့ swap မလုပ်ပါဘူး)
  • Pass k ခါ ပြီးရင် ရှေ့ဆုံး element k ခုက စီပြီးသား နောက်ဆုံး နေရာတွေမှာ ရှိနေပါပြီ
  • Pass n-1 ခါ အတိအကျ အမြဲ လိုပါတယ်၊ စောစော ရပ်လို့ မရပါဘူး

main ထဲမှာ တိုက်ရိုက် ရေးထားတဲ့ Java code 

int[] arr = {58, 47, 19, 33, 14};
int n = arr.length;

for (int i = 0; i < n - 1; i++) {
    int minIndex = i;

    for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }

    // Swap the found minimum with the first unsorted element
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

// Print sorted array
for (int i = 0; i < n; i++) {
    System.out.print(arr[i] + " ");
}

arr = [58, 47, 19, 33, 14]
n = len(arr)

for i in range(n - 1):
    min_index = i

    for j in range(i + 1, n):
        if arr[j] < arr[min_index]:
            min_index = j

    # Swap the found minimum with the first unsorted element
    temp = arr[min_index]
    arr[min_index] = arr[i]
    arr[i] = temp

# Print sorted array
for i in range(n):
    print(arr[i], end=" ")

Output:

14 19 33 47 58

Inner loop က 0 ကနေ မဟုတ်ဘဲ i + 1 ကနေ စပါတယ်။ Array ရဲ့ unsorted portion (မစီရသေးတဲ့ အပိုင်း) ထဲမှာပဲ ရှာပါတယ်၊ index (နေရာအမှတ်) i ရှေ့က အရာအားလုံးက စီပြီးသား ဖြစ်ပြီး သူတို့ရဲ့ နောက်ဆုံး နေရာမှာ ရှိနေပါပြီ။

Selection Sort ကို {58, 47, 19, 33, 14} ပေါ်မှာ trace လုပ်ခြင်း

Pass (i) Unsorted portion အငယ်ဆုံး တန်ဖိုး အငယ်ဆုံး index Swap ပြီးနောက် array
0 [58, 47, 19, 33, 14] 14 4 arr[0] ↔ arr[4] [14, 47, 19, 33, 58]
1 [47, 19, 33, 58] 19 2 arr[1] ↔ arr[2] [14, 19, 47, 33, 58]
2 [47, 33, 58] 33 3 arr[2] ↔ arr[3] [14, 19, 33, 47, 58]
3 [47, 58] 47 3 arr[3] ↔ arr[3] [14, 19, 33, 47, 58]

Comparison စုစုပေါင်း: 4 + 3 + 2 + 1 = 10။ Swap စုစုပေါင်း: 4 (pass တစ်ခါကို တစ်ခု)။

Complexity ကို ခွဲခြမ်းစိတ်ဖြာခြင်း

Case Time ဖြစ်တဲ့ အခြေအနေ
Best O(n²) အမြဲတမ်း: unsorted portion တစ်ခုလုံးကို ဆက်ပြီး ကြည့်ရတုန်းပဲ
Average O(n²) ကျပန်း အစဉ်
Worst O(n²) ပြောင်းပြန် စီထားရင် (comparison အရေအတွက် အတူတူပဲ)
Space O(1) minIndex၊ temp၊ i၊ j ကိုပဲ သုံးတယ်: ထပ်လိုတဲ့ memory က constant

Bubble sort နဲ့ မတူတာက selection sort မှာ best case မှာ ပိုမြန်လာတာ မရှိပါဘူး။ Array က စီပြီးသား ဖြစ်နေရင်တောင် အဲဒါကို စစ်ဖို့ comparison n(n-1)/2 ခု လုပ်ရတုန်းပါပဲ။ ဒါပေမဲ့ swap ကိုတော့ အများဆုံး n-1 ခု (pass တစ်ခါကို တစ်ခု) ပဲ လုပ်ပါတယ်၊ bubble sort ကတော့ swap O(n²) ခုအထိ လုပ်ရနိုင်ပါတယ်။ ဒါကြောင့် swap တစ်ခုစီ လုပ်ရတာ အချိန်နဲ့ အလုပ် များတဲ့အခါ selection sort က ပိုကောင်းပါတယ်၊ ဥပမာ record (အချက်အလက် အများကြီး စုထားတဲ့ ဒေတာ တစ်ခု) အကြီးကြီးတွေကို ရွှေ့ရတဲ့အခါမျိုးပါ။

Selection Sort Algorithm Explained
Selection Sort Algorithm Explained

Watch on YouTube

Selection Sort Quick Check

Q1. Selection sort က pass တစ်ခါစီမှာ ဘာလုပ်သလဲ။

Q2. Selection sort ရဲ့ best-case time complexity က ဘာလဲ။

Q3. Element 8 ခုပါတဲ့ array ပေါ်မှာ selection sort pass 3 ခါ လုပ်ပြီးရင် element ဘယ်နှစ်ခုက သူတို့ရဲ့ နောက်ဆုံး နေရာမှာ ရှိနေတာ သေချာသလဲ။

Q4. Field (object ထဲက အချက်အလက် အကွက်) အများကြီး ပါတဲ့ object (class တစ်ခုကနေ ဖန်တီးထားတဲ့ instance) တွေလို record အကြီးကြီးတွေကို စီတဲ့အခါ bubble sort ထက် selection sort ကို ဘာကြောင့် ပိုရွေးနိုင်သလဲ။

Selection Sort Trace Exercise

{7, 4, 10, 3} ပေါ်မှာ selection sort ကို trace လုပ်ပါ။ Pass တစ်ခါစီ ပြီးတိုင်း တွေ့တဲ့ အငယ်ဆုံး တန်ဖိုးနဲ့ array ရဲ့ အခြေအနေကို ဖြည့်ပါ။

Pass (i)အငယ်ဆုံး တန်ဖိုးအငယ်ဆုံး indexနေရာ 0နေရာ 1နေရာ 2နေရာ 3
အစ - - 7 4 10 3
0
1 3
2 3 4

Selection Sort Code Completion

Array ကို ascending order နဲ့ စီပေးတဲ့ selection sort code ကို ကွက်လပ်တွေ ဖြည့်ပြီး ပြည့်စုံအောင် လုပ်ပါ။

ဒီ algorithm က unsorted portion ထဲက အငယ်ဆုံး element ကို ရှာပြီး မှန်ကန်တဲ့ နေရာကို swap လုပ်ထည့်ပါတယ်။ Variable minIndex က မစီရသေးတဲ့ element တွေထဲက အငယ်ဆုံးကို ဘယ်နေရာမှာ တွေ့သလဲ မှတ်ထားပါတယ်။

int[] arr = {46, 19, 75, 8, 31};
int n = arr.length;

for (int i = 0; i < n - 1; i++) {
    int minIndex = ;

    for (int j = ; j < n; j++) {
        if (arr[j] < ) {
            minIndex = ;
        }
    }

    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

Selection Sort Spot the Error

ဒီ selection sort ရဲ့ ရှာတဲ့ အပိုင်းအခြားမှာ အမှားတစ်ခု ပါနေလို့ နောက်ဆုံးမှာ array က စီပြီးသား မဖြစ်ပါဘူး။ Bug ရှိတဲ့ line ကို ရွေးပါ၊ ပြီးရင် ပြင်နည်းကို ရွေးပါ။

1int[] arr = {20, 5, 15, 10}; 2int n = arr.length; 3for (int i = 0; i < n - 1; i++) { 4 int minIndex = i; 5 for (int j = 0; j < n; j++) { 6 if (arr[j] < arr[minIndex]) { 7 minIndex = j; 8 } 9 } 10 int temp = arr[minIndex]; 11 arr[minIndex] = arr[i]; 12 arr[i] = temp; 13}

Line 5 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Selection Sort Predict the Output

ဒီ code က တကယ် လုပ်ခဲ့တဲ့ swap (အငယ်ဆုံးက နေရာမှန်မှာ မရှိသေးလို့ လုပ်ရတဲ့ swap) အရေအတွက်ကို ရေတွက်ပါတယ်။ Output အတိအကျ က ဘာလဲ။

int[] arr = {8, 3, 6, 1};
int n = arr.length;
int swaps = 0;
for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    if (minIndex != i) {
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
        swaps++;
    }
}
System.out.println("Swaps: " + swaps);

သင့်အဖြေကို ရိုက်ထည့်ပါ:

Selection Sort လေ့ကျင့်ခန်းများ

  1. စာရွက်ပေါ်မှာ trace လုပ်ခြင်း။ {29, 10, 14, 37, 13} ပေါ်မှာ selection sort ကို Trace လုပ်ပါ။ Pass တစ်ခါစီအတွက် တွေ့တဲ့ အငယ်ဆုံး တန်ဖိုး၊ သူ့ရဲ့ index နဲ့ swap ပြီးနောက် array ရဲ့ အခြေအနေကို မှတ်ပါ။

  2. Comparison တွေကို ရေတွက်ခြင်း။ Selection sort code ထဲကို comparison ရေတွက်တဲ့ counter (အရေအတွက် မှတ်တဲ့ variable) တစ်ခု ထည့်ပြီး element 6 ခုပါတဲ့ array ပေါ်မှာ run ပါ။ စုစုပေါင်းက n(n-1)/2 = 15 comparison ဖြစ်ကြောင်း စစ်ကြည့်ပါ။

  3. Swap ရေတွက်ခြင်း။ Swap အရေအတွက်ကို ရေတွက်ပြီး print ထုတ်အောင် selection sort ကို ပြင်ပါ။ {1, 2, 3, 4, 5} (စီပြီးသား) နဲ့ {5, 4, 3, 2, 1} (ပြောင်းပြန် စီထားတာ) ပေါ်မှာ run ပါ။ Swap အရေအတွက်တွေ ဘယ်လို ကွာသလဲ။ ဘာကြောင့်လဲ။

  4. အငယ်ဆုံးအစား အကြီးဆုံးကို ရှာခြင်း။ Pass တစ်ခါစီမှာ အကြီးဆုံး element ကို ရှာပြီး unsorted portion ရဲ့ အဆုံး မှာ ထားအောင် selection sort ကို ပြင်ပါ (ဘယ်ကနေ ညာကို မဟုတ်ဘဲ ညာကနေ ဘယ်ကို စီတာပါ)။

String တွေကို .compareTo() နဲ့ စီခြင်း

Java မှာ String array တွေကို စီတဲ့အခါ < ဒါမှမဟုတ် > ကို သုံးလို့ မရပါဘူး: အဲဒါတွေက primitive type (Java ရဲ့ အခြေခံ ဒေတာ အမျိုးအစား) တွေမှာပဲ အလုပ်လုပ်ပါတယ်။ (Python မှာတော့ < နဲ့ > က string တွေမှာလည်း အလုပ်လုပ်ပြီး အက္ခရာစဉ်အတိုင်း နှိုင်းယှဉ်ပေးတာမို့ integer (ကိန်းပြည့်) အတွက် ရေးထားတဲ့ sort ကို string တွေအတွက် ဘာမှ မပြင်ဘဲ သုံးလို့ ရပါတယ်။) Java မှာတော့ အဲဒီအစား .compareTo() ကို သုံးပါ:

  • a.compareTo(b) > 0 ဆိုရင် အက္ခရာစဉ်အရ a က b ရဲ့ နောက်မှာ လာတယ်လို့ အဓိပ္ပာယ်ရပါတယ် (ဂဏန်းတွေအတွက် a > b နဲ့ တူပါတယ်)
  • a.compareTo(b) < 0 ဆိုရင် a က b ရဲ့ ရှေ့မှာ လာပါတယ်
  • a.compareTo(b) == 0 ဆိုရင် နှစ်ခု တူညီပါတယ်
String[] names = {"Charlie", "Alice", "Eve", "Bob", "Diana"};
int n = names.length;

// Bubble sort for Strings
for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
        if (names[j].compareTo(names[j + 1]) > 0) {
            String temp = names[j];
            names[j] = names[j + 1];
            names[j + 1] = temp;
        }
    }
}

for (int i = 0; i < n; i++) {
    System.out.print(names[i] + " ");
}

names = ["Charlie", "Alice", "Eve", "Bob", "Diana"]
n = len(names)

# Bubble sort for strings - in Python, > already compares
# strings alphabetically, so no .compareTo() is needed
for i in range(n - 1):
    for j in range(n - 1 - i):
        if names[j] > names[j + 1]:
            temp = names[j]
            names[j] = names[j + 1]
            names[j + 1] = temp

for i in range(n):
    print(names[i], end=" ")

Output:

Alice Bob Charlie Diana Eve

Integer တွေကို စီတာနဲ့ ကွာတာ တစ်ခုတည်းက arr[j] > arr[j + 1] နေရာမှာ names[j].compareTo(names[j + 1]) > 0 ကို အစားထိုးတာပါ။ Swap လုပ်တဲ့ logic ကတော့ လုံးဝ အတူတူပါပဲ။ ဒါက bubble sort ရော selection sort ပါ နှစ်ခုလုံးအတွက် မှန်ပါတယ်။

.compareTo() နဲ့ တခြား String method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) တွေရဲ့ အပြည့်အစုံကို Strings မှာ ကြည့်ပါ။

Bubble Sort နဲ့ selection sort နှိုင်းယှဉ်ချက်

လက္ခဏာ Bubble Sort Selection Sort
နည်းဗျူဟာ ဘေးချင်းကပ် အတွဲတွေကို swap လုပ်တယ် အငယ်ဆုံးကို ရှာပြီး နေရာချတယ်
Comparison (worst case) n(n-1)/2 n(n-1)/2
Swap (worst case) n(n-1)/2 n-1
Best-case time Flag နဲ့ဆိုရင် O(n) O(n²): ပိုမကောင်းလာဘူး
Worst-case time O(n²) O(n²)
Space O(1) O(1)
Adaptive (ဒေတာ အခြေအနေနဲ့ လိုက်ပြီး မြန်နှုန်း ပြောင်းတဲ့) ဖြစ်လား ဖြစ်ပါတယ်: စီလုနီးပါး ဒေတာမှာ ပိုမြန်တယ် မဖြစ်ပါဘူး: ဘယ်လို ဒေတာပဲ ဖြစ်ဖြစ် အလုပ် အတူတူပဲ
Stable (တူညီတဲ့ တန်ဖိုးတွေရဲ့ အစဉ် မပျက်တဲ့) ဖြစ်လား ဖြစ်ပါတယ်: တူညီတဲ့ element တွေက မူလ အစဉ်အတိုင်း ရှိနေတယ် မဖြစ်ပါဘူး: swap လုပ်တာကြောင့် တူညီတဲ့ element တွေရဲ့ အစဉ် ပြောင်းသွားနိုင်တယ်

Bubble sort ကို ဘယ်အချိန် ရွေးမလဲ:

  • ဒေတာက စီလုနီးပါး ဒါမှမဟုတ် စီပြီးသား ဖြစ်နေတဲ့အခါ (early exit ကြောင့် အကျိုးရှိတယ်)
  • Stability (တူညီတဲ့ element တွေရဲ့ အချင်းချင်း အစဉ်ကို ထိန်းထားတာ) အရေးကြီးတဲ့အခါ

Selection sort ကို ဘယ်အချိန် ရွေးမလဲ:

  • Swap လုပ်ရတာ အချိန်နဲ့ အလုပ် များတဲ့အခါ (ဥပမာ record အကြီးကြီးတွေ): swap အများဆုံး n-1 ခုပဲ လုပ်တယ်
  • Best case မှာ ပိုမြန်အောင် လုပ်ထားတာထက် အမြဲ တစ်သမတ်တည်း ဖြစ်တဲ့ မြန်နှုန်းကို ပိုလိုချင်တဲ့အခါ

Algorithm နှစ်ခုလုံးရဲ့ worst-case time က O(n²) ဖြစ်လို့ dataset (ဒေတာ အစုအဝေး) အကြီးကြီးတွေအတွက် လက်တွေ့မှာ အသုံးမဝင်ပါဘူး။ ဒေတာ များတဲ့အခါ quicksort (pivot နဲ့ ခွဲပြီး မြန်မြန် စီတဲ့ နည်း၊ ပျမ်းမျှ O(n log n)) လို algorithm တွေက အများကြီး ပိုထိရောက်ပါတယ်: HL (Higher Level: IB သင်တန်းမှာ ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အဆင့်) အပိုင်းက Quicksort မှာ လေ့လာရပါမယ်။

နှစ်မျိုးလုံး သုံးရတဲ့ လေ့ကျင့်ခန်းများ

ဒီလေ့ကျင့်ခန်းတွေမှာ sorting algorithm နှစ်ခုလုံးကို နှိုင်းယှဉ်ရ ဒါမှမဟုတ် သုံးရပါမယ်။

နှစ်မျိုးလုံးအတွက် Quick Check

Q1. စီပြီးသား array ပေါ်မှာ ဘယ် sorting algorithm က ပိုကောင်းကောင်း အလုပ်လုပ်သလဲ။

Q2. Program ရေးသူ တစ်ယောက်က record 1,000,000 ကို စီဖို့ လိုပါတယ်။ Bubble sort နဲ့ selection sort က ဘာကြောင့် မကောင်းတဲ့ ရွေးချယ်မှုတွေ ဖြစ်သလဲ။

Q3. ကျောင်းသား record object အကြီးကြီးတွေ (နာမည်၊ အမှတ်၊ လိပ်စာ စသဖြင့်) ပါတဲ့ array ကို စီမယ်ဆိုပါစို့။ ဘယ် algorithm က ပိုမြန်နိုင်သလဲ၊ ဘာကြောင့်လဲ။

နှစ်မျိုးလုံးအတွက် လေ့ကျင့်ခန်းများ

  1. စီပြီး နှိုင်းယှဉ်ခြင်း။ Array {50, 23, 9, 18, 61, 32} ကို ဖန်တီးတဲ့ program တစ်ခု ရေးပါ။ Copy တစ်ခုကို bubble sort နဲ့ စီပြီး နောက် copy တစ်ခုကို selection sort နဲ့ စီပါ။ တစ်ခုစီအတွက် comparison နဲ့ swap အရေအတွက်ကို ရေတွက်ပြီး print ထုတ်ပါ။ ဘယ် algorithm က swap ပိုများများ လုပ်ခဲ့သလဲ။

  2. စီလုနီးပါး ဒေတာနဲ့ ကျပန်း ဒေတာ။ Algorithm နှစ်ခုလုံးကို ဒီ array နှစ်ခုပေါ်မှာ စမ်းသပ်ပါ:
    • စီလုနီးပါး: {1, 2, 4, 3, 5, 6, 8, 7}
    • ကျပန်း: {45, 12, 78, 3, 56, 22, 91, 8} တစ်ခုစီအတွက် comparison နဲ့ swap တွေကို ရေတွက်ပါ။ စီလုနီးပါး ဒေတာကြောင့် ဘယ် algorithm က ပိုအကျိုးရှိသလဲ။

  3. String တွေကို စီခြင်း။ String[] fruits = {"Mango", "Apple", "Cherry", "Banana", "Date"} ကို ပေးထားပါတယ်။ .compareTo() နဲ့ selection sort ကို သုံးပြီး အက္ခရာစဉ်အတိုင်း စီပါ။ Code မရေးခင် ပထမ pass နှစ်ခါကို စာရွက်ပေါ်မှာ Trace လုပ်ပါ။

  4. Algorithm ရွေးချယ်ခြင်း။ အခြေအနေ တစ်ခုစီအတွက် bubble sort ဒါမှမဟုတ် selection sort ကို ရွေးပါ၊ ပြီးရင် Justify (ဘာကြောင့် ရွေးတာလဲ အကြောင်းပြချက်နဲ့ ပြပါ):
    • (a) စီလုနီးပါး ဖြစ်နေတဲ့ quiz အမှတ် 10 ခုကို စီခြင်း
    • (b) ကျောင်းသား record 100 ကို စီခြင်း (record တစ်ခုစီက object အကြီးကြီး တစ်ခုပါ)
    • (c) လုံးဝ ပြောင်းပြန် ဖြစ်နေတဲ့ array တစ်ခုကို စီခြင်း
    • (d) Element 5 ခုပဲ ပါတဲ့ array အသေးလေးကို စီခြင်း

  5. ဒေတာ ကြီးလာရင် ဘယ်လောက် ကွာသလဲ နှိုင်းယှဉ်ခြင်း။ ဒီဇယားကို ဖြည့်ပါ:

    Array အရွယ် (n) Worst-case comparison Bubble sort အတွက် အချိန် (O(n²)) Quicksort အတွက် အချိန် (O(n log n))
    10 ? ? ?
    100 ? ? ?
    1,000 ? ? ?
    1,000,000 ? ? ?

    Comparison တစ်ခုကို 1 microsecond (တစ်စက္ကန့်ရဲ့ တစ်သန်းပုံ တစ်ပုံ) ကြာတယ်လို့ ယူဆပါ။ အဖြေတွေကို သင့်တော်တဲ့ ယူနစ်နဲ့ ဖော်ပြပါ (microsecond၊ millisecond (တစ်စက္ကန့်ရဲ့ တစ်ထောင်ပုံ တစ်ပုံ)၊ စက္ကန့်၊ မိနစ်)။

GitHub Classroom (အလိုအလျောက် စစ်ဆေးတဲ့ test တွေပါတဲ့ programming assignment များ)

Sorting Algorithms
Practice implementing bubble sort and selection sort on arrays of integers and strings.

A class assignment on GitHub Classroom: use it when your teacher has set it. It needs a free GitHub account.

Core Accept the assignment on GitHub

Working in the Codespace

  1. Accept and open. Accept the assignment above, open the link in the email from GitHub, then press Open in Codespace. In Java, change the status bar from Lightweight to Standard mode.
  2. Write and check. Open src/BubbleDescending.java and complete each TODO. Press Run and compare the output with the comments, or run bash run-tests.sh in the Terminal.
  3. Submit. In Source Control, write a message, press Commit, then Sync Changes. Your teacher’s feedback arrives as a pull request called Feedback.

There are six exercise files in src/: start with BubbleDescending.java and work down the list in the README.

The full Codespace guide, with pictures

ဆက်စပ် ခေါင်းစဉ်များ

  • အရင် သိထားရမှာများ: 1D Arrays (တန်းတစ်တန်းတည်းမှာ စီထားတဲ့ ဒေတာအစု): ဒီသင်ခန်းစာမှာ စီရမယ့် data structure (ဒေတာ သိမ်းဆည်းပုံ) ပါ။ Iteration (ထပ်ခါထပ်ခါ လုပ်ခြင်း): algorithm နှစ်ခုလုံးက nested loop (loop ထဲမှာ ထပ်ပါတဲ့ loop) တွေနဲ့ အလုပ်လုပ်ပါတယ်။ Selection (condition ပေါ်မူတည်ပြီး လမ်းကြောင်း ရွေးခြင်း): comparison တွေအတွက် if statement တွေ သုံးပါတယ်။
  • ဆက်စပ်တာ: Searching Algorithms (ရှာဖွေရေး algorithm များ): binary search (တစ်ဝက်စီ ခွဲပြီး ရှာနည်း) အတွက် စီပြီးသား ဒေတာ လိုပါတယ်၊ ဒါကြောင့် sorting လုပ်ထားရင် ပိုမြန်မြန် ရှာနိုင်ပါတယ်။
  • နောက်ပိုင်း: Methods (IB သင်ရိုးရဲ့ B2.3.4) ကို လေ့လာပြီးတဲ့အခါ sort algorithm နှစ်ခုလုံးကို ပြန်သုံးလို့ရတဲ့ method တွေအဖြစ် ပြန်ရေးပါမယ်။
  • HL: Quicksort: ပျမ်းမျှ O(n log n) ဖြစ်တဲ့ algorithm ဖြစ်ပြီး ဒေတာ များတဲ့အခါ O(n²) sort တွေထက် အများကြီး ပိုထိရောက်ပါတယ်။
  • Big-O Notation (algorithm ရဲ့ ကြာချိန် တိုးနှုန်းကို ပြတဲ့ သင်္ကေတ) က ဒီမှာ မိတ်ဆက်ခဲ့တဲ့ complexity analysis ကို စနစ်တကျ ပုံသေနည်းနဲ့ ဖော်ပြပေးပါတယ်။

© EduCS.me. ကွန်ပျူတာသိပ္ပံ ပညာရေးအတွက် အရင်းအမြစ်တွေ စုထားတဲ့ နေရာပါ။ EduCS is an independent educational resource. It is not affiliated with, or endorsed by, the International Baccalaureate Organization. (EduCS ဟာ သီးခြား ပညာရေး အရင်းအမြစ်တစ်ခုပါ။ International Baccalaureate Organization နဲ့ ဆက်စပ်မှု မရှိသလို သူတို့ရဲ့ ထောက်ခံချက်လည်း မရှိပါဘူး။) ဆက်သွယ်ရန်

Built with Just the Docs.