Quicksort (pivot နဲ့ ခွဲပြီး မြန်မြန် စီတဲ့ နည်း)

B2.4.4 (HL): Explain the fundamental concept of recursion and its applications in programming. Quicksort is listed as a recursive algorithm application; O(n log n) average-case, O(n^2) worst case.
မြန်မာလို: recursion (method က သူ့ကိုယ်သူ ပြန်ခေါ်ခြင်း) ရဲ့ အခြေခံ သဘောတရားနဲ့ programming မှာ recursion ကို ဘယ်လို အသုံးချလဲဆိုတာကို explain (ရှင်းပြ) နိုင်ရပါမယ်။ IB သင်ရိုးမှာ quicksort ကို recursion သုံးတဲ့ algorithm (အယ်လ်ဂိုရီသမ်၊ ပြဿနာကို အဆင့်ဆင့် ဖြေရှင်းတဲ့ နည်းလမ်း) ဥပမာ တစ်ခုအဖြစ် ဖော်ပြထားပါတယ်: average case (ပျမ်းမျှ အခြေအနေ) မှာ O(n log n)၊ worst case (အဆိုးဆုံး အခြေအနေ) မှာ O(n^2) ဖြစ်ပါတယ်။

ဒီစာမျက်နှာက HL အတွက်သာ ဖြစ်ပါတယ်။ SL (Standard Level) နဲ့ HL (Higher Level) ဆိုတာ IB Computer Science သင်တန်းရဲ့ အဆင့်နှစ်ဆင့်ဖြစ်ပြီး HL အပိုင်းတွေက ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အပိုင်းတွေပါ။

  • Quicksort အလုပ်လုပ်ပုံ: pivot (တခြား တန်ဖိုးတွေကို ဘယ်ညာ ခွဲဖို့ ရွေးထားတဲ့ တန်ဖိုး) တစ်ခုကို အခြေခံပြီး တန်ဖိုးတွေကို partition (pivot ကို အခြေခံပြီး တန်ဖိုးတွေကို နှစ်ဘက် ခွဲခြင်း) လုပ်ပါတယ်: ငယ်တာ ဒါမှမဟုတ် ညီတာကို ဘယ်ဘက်မှာ၊ ကြီးတာကို ညာဘက်မှာ ထားပြီး ဘက်တစ်ဖက်စီကို ဆက်စီပါတယ်။
  • အဓိက သိရမယ့် အချက်: partition လုပ်ပြီးတဲ့အခါ pivot က သူ့ရဲ့ နောက်ဆုံး နေရာမှာ ရှိနေပြီ ဖြစ်လို့ နောက်ကနေ combine step (ခွဲထားတဲ့ အပိုင်းတွေကို ပြန်ပေါင်းတဲ့ အဆင့်) မလိုတော့ပါဘူး။
  • Complexity (input ကြီးလာရင် လုပ်ရတဲ့ အလုပ် တိုးလာပုံ): ညီညီမျှမျှ ခွဲမိရင် O(n log n) ရပြီး တစ်ဖက်တည်းကို အကုန် ရောက်အောင် ခွဲမိရင် O(n^2) ရပါတယ်။
  • Recursion tree က BST ဖြစ်တယ်: recursion tree (recursion ခေါ်မှုတွေကို သစ်ပင်ပုံ ဆွဲပြတဲ့ ပုံ) ထဲက pivot တွေက BST (binary search tree: ဘယ်ဘက် ငယ်၊ ညာဘက် ကြီးတဲ့ binary tree) ရဲ့ “ငယ်တာ ဘယ်ဘက်၊ ကြီးတာ ညာဘက်” စည်းမျဉ်းအတိုင်း ဖြစ်ပါတယ်။

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

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

Quicksort က array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) ကို pivot လို့ ခေါ်တဲ့ ရွေးထားတဲ့ element (အစုထဲက အချက်) တစ်ခုကို အခြေခံပြီး ထပ်ခါထပ်ခါ နှစ်ပိုင်း ခွဲခြင်းအားဖြင့် စီပါတယ်။ ခွဲတိုင်း pivot ကို သူ့ရဲ့ မှန်ကန်တဲ့ နောက်ဆုံး နေရာမှာ ထားပေးပြီး ပိုငယ်တဲ့ တန်ဖိုးတွေက သူ့ ဘယ်ဘက်မှာ၊ ပိုကြီးတဲ့ တန်ဖိုးတွေက သူ့ ညာဘက်မှာ ရှိနေပါတယ်။ ပြီးရင် ဘက်နှစ်ဖက်ကို အဲဒီ နည်းအတိုင်းပဲ ဆက်စီပါတယ်။ Sub-array (array ရဲ့ အပိုင်းလေး) တိုင်းမှာ element 0 ခု ဒါမှမဟုတ် 1 ခုပဲ ကျန်ပြီး စီပြီးသား ဖြစ်သွားတဲ့အထိ ဆက်လုပ်ပါတယ်။

အဆင့်တွေကို ရိုးရိုး စကားနဲ့ ပြောရရင်:

  1. Sub-array မှာ element 0 ခု ဒါမှမဟုတ် 1 ခုပဲ ရှိရင် ရပ်ပါ: စီပြီးသား ဖြစ်နေပါပြီ။ (ဒါက base case ပါ: recursion ကို ရပ်စေတဲ့ condition)
  2. Pivot element တစ်ခုကို ရွေးပါ (ဥပမာ sub-array ရဲ့ နောက်ဆုံး element)။
  3. Partition လုပ်ပါ: ကျန်တဲ့ element တွေကို တစ်ခုချင်း ကြည့်ပြီး pivot ထက် ငယ်တာ ဒါမှမဟုတ် ညီတာ တွေကို ဘယ်ဘက်ကို၊ pivot ထက် ကြီးတာ တွေကို ညာဘက်ကို ရွှေ့ပါ။
  4. Pivot ကို အုပ်စု နှစ်စုကြားမှာ ထားပါ။ အခု pivot က စီပြီးသား array ထဲက သူ့ရဲ့ နောက်ဆုံး နေရာမှာ ရှိနေပါပြီ။
  5. ဘယ်ဘက် sub-array နဲ့ ညာဘက် sub-array ပေါ်မှာ အဲဒီ လုပ်ငန်းစဉ်အတိုင်းပဲ ထပ်လုပ်ပါ။
  6. Recursive call (method က သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ ခေါ်မှု) တိုင်းက element 0 ခု ဒါမှမဟုတ် 1 ခုပဲ ပါတဲ့ sub-array ကို ရောက်သွားတဲ့အခါ array တစ်ခုလုံး စီပြီးသား ဖြစ်သွားပါပြီ။

အဓိက သိရမယ့် အချက်

Partition လုပ်ပြီးတိုင်း pivot က သူ့ရဲ့ နောက်ဆုံး နေရာမှာ ရှိနေပါပြီ: နောက်ထပ် ဘယ်တော့မှ မရွေ့တော့ပါဘူး။ ဒါကြောင့် quicksort မှာ combine step မရှိပါဘူး: စီတာက partition ပြီးမှ မဟုတ်ဘဲ partition လုပ်နေစဉ်မှာပဲ ဖြစ်ပါတယ်။ Recursive call တွေက ဘက်နှစ်ဖက်ကိုပဲ စီပေးဖို့ လိုပါတယ်: pivot ကတော့ သူ ရှိရမယ့် နေရာကို ရောက်နေပြီးသားပါ။

Complexity (input ကြီးလာရင် လုပ်ရတဲ့ အလုပ် တိုးလာပုံ)

Case Complexity ဘယ်လို အခြေအနေမှာ ဖြစ်လဲ
Best (အကောင်းဆုံး အခြေအနေ) O(n log n) Pivot က sub-array ကို အကြိမ်တိုင်း တစ်ဝက်နီးပါးစီ ခွဲပေးတယ်
Average (ပျမ်းမျှ အခြေအနေ) O(n log n) ကျပန်း input (program ထဲ ထည့်ပေးတဲ့ ဒေတာ): partition တွေက ညီလုနီးပါး ဖြစ်တယ်
Worst (အဆိုးဆုံး အခြေအနေ) O(n^2) Pivot က အမြဲ အငယ်ဆုံး ဒါမှမဟုတ် အကြီးဆုံး element ဖြစ်နေတယ် (ဥပမာ စီပြီးသား array မှာ နောက်ဆုံး element ကို pivot အဖြစ် ရွေးရင်)

Partition တစ်ခါစီမှာ element O(n) ခုကို ဖြတ်ကြည့်ရပါတယ်။ Pivot က ညီညီမျှမျှ ခွဲပေးရင် recursion က log n level (အဆင့်) နက်ပြီး O(n) x O(log n) = O(n log n) ရပါတယ်။ ခွဲတိုင်း တစ်ဖက်တည်းကို အကုန် ရောက်ရင်တော့ recursion က level n ခု နက်ပြီး O(n) x O(n) = O(n^2) ရပါတယ်။

Memory (မှတ်ဉာဏ်)

Quicksort က မူလ array ထဲမှာပဲ တန်ဖိုးတွေကို နေရာပြန်စီပါတယ်: input အရွယ်အစားနဲ့ တူတဲ့ array အပို တစ်ခု မလိုပါဘူး။ Memory ကို call stack (လက်ရှိ method ခေါ်မှုတွေကို သိမ်းတဲ့ stack) အတွက်ပဲ သုံးပြီး အဲဒီ call stack က recursion ရဲ့ နက်မှုနဲ့အမျှ ကြီးလာပါတယ် (ပျမ်းမျှ O(log n)၊ worst case မှာ O(n))။

တူညီတဲ့ တန်ဖိုးများ

ဒီစာမျက်နှာမှာ ပြထားတဲ့ partition နည်းမှာ pivot နဲ့ တန်ဖိုး ညီတဲ့ element တွေက ဘယ်ဘက်ကို ရောက်ပါတယ်။ တန်ဖိုး တူတဲ့ element တွေရဲ့ မူလ ဘယ်ကနေ ညာ အစဉ်ကို quicksort က ထိန်းထားပေးမယ်လို့ အာမ မခံပါဘူး: partition လုပ်နေစဉ် “5” နှစ်ခုက တစ်ခုကို တစ်ခု ကျော်ပြီး နေရာ ပြောင်းသွားနိုင်ပါတယ်။

ဒါတွေကို သိပြီးသားပါ

Quicksort က algorithm အသစ် ဖြစ်ပေမယ့် အရင်က လေ့လာခဲ့တဲ့ အယူအဆတွေကို ပေါင်းစပ်ထားတာပါ:

  • Bubble sort (ဘေးချင်းကပ် တန်ဖိုးတွေကို လဲပြီး စီခြင်း) နဲ့ selection sort (အငယ်ဆုံးကို ရှာပြီး နေရာချ စီခြင်း) (Sorting Algorithms) က နှိုင်းယှဉ်စရာ အခြေခံ O(n^2) sort နှစ်ခုကို ပေးခဲ့ပါတယ်။ Quicksort က သင် တွေ့ရတဲ့ sort တွေထဲမှာ ပျမ်းမျှအားဖြင့် အဲဒီ နှစ်ခုထက် ပိုမြန်တဲ့ ပထမဆုံး sort ပါ။
  • Big-O notation (algorithm ရဲ့ ကြာချိန် တိုးနှုန်းကို ပြတဲ့ သင်္ကေတ၊ Big-O) ကြောင့် O(n log n) နဲ့ O(n^2) ကို နှိုင်းယှဉ်နိုင်ပါတယ်။
  • Recursion (Recursion) က base case / recursive case (သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ အပိုင်း) ခွဲခြားပုံနဲ့ recursion က ဘာကြောင့် memory ကုန်လဲဆိုတာ ရှင်းပြပေးတဲ့ call stack ပုံကို ပေးခဲ့ပါတယ်။
  • BST ဖွဲ့စည်းပုံ (Binary Search Trees) က “ငယ်တာ ဘယ်ဘက် / ကြီးတာ ညာဘက်” စည်းမျဉ်းကို ပေးခဲ့ပါတယ်။ Partition အဆင့်က အဲဒီ စည်းမျဉ်းကိုပဲ tree အစား array ပေါ်မှာ သုံးပါတယ်။
  • Array index (နေရာအမှတ်) သုံးပုံနဲ့ swap (တန်ဖိုး နှစ်ခု နေရာချင်း လဲခြင်း) လုပ်ပုံ (1D Arrays၊ တန်းတစ်တန်းတည်းမှာ စီထားတဲ့ ဒေတာအစု) က partition ကို လက်တွေ့ လုပ်ဆောင်ပေးတဲ့ အပိုင်းတွေပါ။

IB CS သင်တန်း တက်နေသူတွေအတွက် မှတ်ချက် (B2.4 syllabus): IB syllabus (IB သင်ရိုး) မှာ quicksort က B2.4.4: Explain recursion and its applications (recursion နဲ့ သူ့ရဲ့ အသုံးချပုံတွေကို ရှင်းပြပါ) အောက်မှာ ပါပါတယ်။ အကဲဖြတ်မှုမှာ သုံးတဲ့ ကြိယာက explain (ရှင်းပြပါ) ဖြစ်ပါတယ်: quicksort ကို စကားနဲ့ ဖော်ပြရမယ်၊ partition အဆင့် တစ်ခုကို trace (တစ်ဆင့်ချင်း လိုက်ပြီး မှတ်) လုပ်ရမယ်၊ best / average / worst case တွေကို ရှင်းပြရမယ်၊ ပြီးတော့ syllabus ရဲ့ linking question (ခေါင်းစဉ်တွေကို ချိတ်ဆက်ပေးတဲ့ မေးခွန်း) ဖြစ်တဲ့ “Can a BST play a role in the quicksort algorithm?” (BST က quicksort algorithm မှာ အခန်းကဏ္ဍ ရှိနိုင်သလား) ကို ဖြေရပါမယ်။ Quicksort ကို ကိုယ်တိုင် ရေးတာ (construct) က စာမေးပွဲမှာ မပါပါဘူး: B2.4.3 က sort ရေးတာကို bubble sort နဲ့ selection sort အတွက်ပဲ ကန့်သတ်ထားပြီး B2.4.5 က recursion ရေးတာကို non-branching (ခေါ်မှု တစ်ခါမှာ သူ့ကိုယ်သူ တစ်ကြိမ်ပဲ ပြန်ခေါ်တဲ့) ရိုးရှင်းတဲ့ recursive algorithm တွေအတွက်ပဲ ကန့်သတ်ထားပါတယ်။ ဒီစာမျက်နှာပေါ်က Java code က algorithm ကို run ကြည့်ဖို့နဲ့ IA (Internal Assessment: IB သင်တန်းမှာ ကျောင်းသားတစ်ယောက်ချင်း ကိုယ်တိုင် တည်ဆောက်ရပြီး ကျောင်းက ဆရာက အမှတ်ပေးတဲ့ အပိုင်း) project အတွက် ပြင်သုံးဖို့ ကိုးကားစရာ သက်သက်ပါ၊ ကိုယ်တိုင် ရေးရမယ့် construct task မဟုတ်ပါဘူး။

အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ

ဥပမာ တစ်ခုစီက ဖတ်ပြီး နားလည်ဖို့ ပြထားတာပါ: အစကနေ အဆုံးထိ ဖတ်ပြီး အဆင့်တိုင်းကို နားလည်အောင် လုပ်ပါ။ ဒီခေါင်းစဉ်အတွက် code ကိုယ်တိုင် ရေးရတဲ့ လေ့ကျင့်ခန်းတွေက တခြား စာမျက်နှာတွေမှာ ရှိပါတယ် (bubble sort နဲ့ selection sort ကို ရေးခဲ့ပြီးပါပြီ)။ ဒီမှာတော့ ရည်ရွယ်ချက်က နားလည်ဖို့၊ trace လုပ်ဖို့နဲ့ ဖော်ပြနိုင်ဖို့ ပါ။

ဥပမာ 1: Partition အဆင့် တစ်ခု အပြည့်အစုံ

စစချင်း array: [7, 2, 1, 6, 8, 5, 3, 4]။ Pivot = 4 (နောက်ဆုံး element)။

Pointer (array ထဲက နေရာကို မှတ်ထားတဲ့ index variable) နှစ်ခုက partition အလုပ်ကို လုပ်ပါတယ်:

  • i က -1 ကနေ စပါတယ်။ “pivot ထက် ငယ်တာ ဒါမှမဟုတ် ညီတာ” အပိုင်းရဲ့ ညာဘက် အစွန်းကို မှတ်ထားပါတယ်။
  • j က index 0 ကနေ 6 အထိ ဘယ်ကနေ ညာကို ဖြတ်ကြည့်ပါတယ် (pivot ကလွဲပြီး ကျန်တာ အားလုံး)။
  • arr[j] <= pivot ဖြစ်ရင်: i ကို 1 တိုးပြီး arr[i] နဲ့ arr[j] ကို swap လုပ်ပါ။ ဒါက ငယ်တဲ့ တန်ဖိုးကို ဘယ်ဘက် အပိုင်းထဲ ဆွဲထည့်ပေးပါတယ်။
  • အဆုံးမှာ arr[i + 1] နဲ့ pivot ကို swap လုပ်ပြီး pivot ကို အပိုင်း နှစ်ပိုင်းကြားမှာ ထားပါ။
အဆင့် j arr[j] arr[j] <= 4? လုပ်ဆောင်ချက် i Array အခြေအနေ
အစ - - - စတင် သတ်မှတ် -1 [7, 2, 1, 6, 8, 5, 3, 4]
1 0 7 မဟုတ် ကျော် -1 [7, 2, 1, 6, 8, 5, 3, 4]
2 1 2 ဟုတ် i=0, swap(0, 1) 0 [2, 7, 1, 6, 8, 5, 3, 4]
3 2 1 ဟုတ် i=1, swap(1, 2) 1 [2, 1, 7, 6, 8, 5, 3, 4]
4 3 6 မဟုတ် ကျော် 1 [2, 1, 7, 6, 8, 5, 3, 4]
5 4 8 မဟုတ် ကျော် 1 [2, 1, 7, 6, 8, 5, 3, 4]
6 5 5 မဟုတ် ကျော် 1 [2, 1, 7, 6, 8, 5, 3, 4]
7 6 3 ဟုတ် i=2, swap(2, 6) 2 [2, 1, 3, 6, 8, 5, 7, 4]
နောက်ဆုံး - - - swap(i+1=3, index 7 က pivot) - [2, 1, 3, 4, 8, 5, 7, 6]

Partition ပြီးတဲ့အခါ pivot 4 က index 3 မှာ ရှိပါတယ်။ အဲဒါက စီပြီးသား array ထဲမှာ သူ ရှိရမယ့် နေရာ အမှန်ပါ။

  • ဘယ်ဘက် sub-array: [2, 1, 3] (index 0-2၊ အားလုံး <= 4)
  • ညာဘက် sub-array: [8, 5, 7, 6] (index 4-7၊ အားလုံး > 4)

အခု quicksort က [2, 1, 3] ပေါ်မှာရော [8, 5, 7, 6] ပေါ်မှာပါ သူ့ကိုယ်သူ ပြန်ခေါ်ပါတယ်။

ဥပမာ 2: Recursion tree အပြည့်အစုံ (ကိုးကားရန်)

ဥပမာ 1 ကနေ ဆက်ပြီး recursive call တိုင်းကလည်း သူ့ရဲ့ နောက်ဆုံး element ကို pivot အဖြစ် သုံးမယ်ဆိုရင် recursion tree အပြည့်အစုံက ဒီလို ဖြစ်ပါတယ်။ စက်ဝိုင်း တစ်ခုစီက ခေါ်မှု (call) တစ်ခုပါ။ စက်ဝိုင်းထဲမှာ အဲဒီ call ရွေးခဲ့တဲ့ pivot ကို ရေးထားပြီး အဲဒီ တန်ဖိုး နောက်ဆုံး ရောက်သွားမယ့် index ရဲ့ အပေါ်တည့်တည့်မှာ ထားထားပါတယ်။

[7, 2, 1, 6, 8, 5, 3, 4] ပေါ်မှာ quicksort လုပ်တဲ့ ခေါ်မှုတွေပါ၊ အပိုင်း တစ်ခုစီရဲ့ နောက်ဆုံး element ကို pivot အဖြစ် သုံးထားပါတယ်။ ပထမ ခေါ်မှုက array တစ်ခုလုံးကို 4 ကို အခြေခံပြီး partition လုပ်ပါတယ်။ 4 ရဲ့ ဘယ်ဘက်မှာ 3၊ ညာဘက်မှာ 6 ရှိပါတယ်။ 3 ရဲ့ ဘယ်ဘက်မှာ 1 ရှိပါတယ်။ 1 ရဲ့ ညာဘက်မှာ 2 ရှိပါတယ်။ 6 ရဲ့ ဘယ်ဘက်မှာ 5၊ ညာဘက်မှာ 8 ရှိပါတယ်။ 8 ရဲ့ ဘယ်ဘက်မှာ 7 ရှိပါတယ်။ 2၊ 5 နဲ့ 7 က တန်ဖိုး တစ်ခုတည်း ပါတဲ့ ခေါ်မှုတွေ ဖြစ်လို့ ချက်ချင်း return ပြန်ပါတယ်။ ခေါ်မှု တစ်ခုစီက သူ့ pivot နောက်ဆုံး ရောက်တဲ့ index ရဲ့ အပေါ်မှာ ရှိလို့ စက်ဝိုင်းတွေကို ဘယ်ကနေ ညာ ဖတ်ရင် စီပြီးသား array 1, 2, 3, 4, 5, 6, 7, 8 ကို ရပါတယ်။ 4 3 1 2 6 5 8 7 1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 first call: the whole array Each circle sits above the index where its value ends up. one value: already in place (base case)

ခေါ်မှုတွေက tree ရဲ့ အောက်ဘက်ကို ဆင်းသွားပါတယ်။ ခေါ်မှု တစ်ခုစီက သူ့ တန်ဖိုးရဲ့ နောက်ဆုံး index အပေါ်မှာ ရှိလို့ စက်ဝိုင်းတွေကို ဘယ်ကနေ ညာ ဖတ်ရင် စီပြီးသား array ကို ရပါတယ်။ 3 ရဲ့ ညာဘက်လို အလွတ် အပိုင်းပေါ်က ခေါ်မှုတွေက ချက်ချင်း return ပြန်လို့ ပုံမှာ မထည့်ထားပါဘူး။

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “first call: the whole array” က ပထမ ခေါ်မှု: array တစ်ခုလုံး၊ “Each circle sits above the index where its value ends up.” က စက်ဝိုင်း တစ်ခုစီက သူ့ တန်ဖိုး နောက်ဆုံး ရောက်တဲ့ index ရဲ့ အပေါ်မှာ ရှိတယ်၊ “one value: already in place (base case)” က တန်ဖိုး တစ်ခုတည်း: နေရာမှန် ရောက်ပြီးသား (base case) လို့ အဓိပ္ပာယ်ရပါတယ်။

Node တိုင်းမှာ ဘယ်ဘက် subtree၊ root၊ ညာဘက် subtree ဆိုတဲ့ in order အစဉ်နဲ့ tree ကို ဖတ်ရင် စီပြီးသား ရလဒ် [1, 2, 3, 4, 5, 6, 7, 8] ကို ပြန်ရပါတယ် (node က tree ထဲက စက်ဝိုင်း တစ်ခုစီ၊ root က အပေါ်ဆုံး node၊ subtree က node တစ်ခုရဲ့ အောက်က အကိုင်းခွဲ tree ပါ)။ Pivot တိုင်းကို partition က သူ့ နောက်ဆုံး နေရာမှာ ထားပြီးသား ဖြစ်လို့ recursion ပြီးဆုံးပြီး ခေါ်မှုတွေ ပြန်ထွက်လာတဲ့အခါ ထပ်ပြီး နေရာ ပြန်စီစရာ မလိုပါဘူး။

ဒီ tree က ဘာ မဟုတ်လဲ: quicksort က တည်ဆောက်တဲ့ ဒါမှမဟုတ် သိမ်းထားတဲ့ data structure (ဒေတာ သိမ်းဆည်းပုံ) တစ်ခု မဟုတ်ပါဘူး။ ဒါက ခေါ်မှု အဆက်အစပ်ကို ပြတဲ့ ပုံ ပါ: ဘယ်သူက ဘယ်သူ့ကို ခေါ်လဲဆိုတာ ဆွဲပြထားတာပါ။

ဥပမာ 3: Quicksort ရဲ့ recursion tree က BST ဖြစ်တယ်

ဥပမာ 2 က tree ကို BST တစ်ခုနဲ့ ဘေးချင်း ယှဉ်ကြည့်ပါ။ အဲဒီ BST ကို pivot တွေကို အပေါ်ကနေ level တစ်ခုချင်း (4၊ ပြီးရင် 3၊ ပြီးရင် 6၊ ပြီးရင် 1၊ ပြီးရင် 5၊ ပြီးရင် 8၊ ပြီးရင် 2၊ ပြီးရင် 7) ထည့်ပြီး တည်ဆောက်ထားပါတယ်:

[7, 2, 1, 6, 8, 5, 3, 4] ပေါ်မှာ quicksort ရဲ့ pivot တွေပါ: အပေါ်ဆုံးမှာ 4 ရှိပါတယ်။ 4 ရဲ့ ဘယ်ဘက်မှာ 3၊ ညာဘက်မှာ 6 ရှိပါတယ်။ 3 ရဲ့ ဘယ်ဘက်မှာ 1 ရှိပါတယ်။ 1 ရဲ့ ညာဘက်မှာ 2 ရှိပါတယ်။ 6 ရဲ့ ဘယ်ဘက်မှာ 5၊ ညာဘက်မှာ 8 ရှိပါတယ်။ 8 ရဲ့ ဘယ်ဘက်မှာ 7 ရှိပါတယ်။ Quicksort recursion tree 4 3 1 2 6 5 8 7 4, 3, 6, 1, 5, 8, 2 နဲ့ 7 ကို ထည့်ပြီးနောက် binary search tree ပါ: root မှာ 4 ရှိပါတယ်။ 4 ရဲ့ ဘယ်ဘက်မှာ 3၊ ညာဘက်မှာ 6 ရှိပါတယ်။ 3 ရဲ့ ဘယ်ဘက်မှာ 1 ရှိပါတယ်။ 6 ရဲ့ ဘယ်ဘက်မှာ 5၊ ညာဘက်မှာ 8 ရှိပါတယ်။ 1 ရဲ့ ညာဘက်မှာ 2 ရှိပါတယ်။ 8 ရဲ့ ဘယ်ဘက်မှာ 7 ရှိပါတယ်။ Quicksort tree နဲ့ ပုံသဏ္ဌာန် အတူတူပါပဲ။ BST: insert 4, 3, 6, 1, 5, 8, 2, 7 4 3 6 1 5 8 2 7

Tree နှစ်ခုက node တစ်ခုချင်းစီ ကိုက်ညီပါတယ်။

ပုံထဲက English ခေါင်းစဉ်တွေက “Quicksort recursion tree” (quicksort ရဲ့ recursion tree) နဲ့ “BST: insert 4, 3, 6, 1, 5, 8, 2, 7” (4, 3, 6, 1, 5, 8, 2, 7 ကို အစဉ်လိုက် ထည့်ထားတဲ့ BST) ပါ။

Tree နှစ်ခုက လုံးဝ တူညီပါတယ်။ အစဉ်စီတဲ့ စည်းမျဉ်း တစ်ခုတည်းကို လိုက်နာထားလို့ပါ:

  • BST: node တစ်ခုစီရဲ့ ဘယ်ဘက် subtree မှာ ပိုငယ်တဲ့ key (node ရဲ့ တန်ဖိုး) တွေ၊ ညာဘက် subtree မှာ ပိုကြီးတဲ့ key တွေ ရှိပါတယ်။
  • Quicksort partition: pivot တစ်ခုစီရဲ့ ဘယ်ဘက်မှာ ပိုငယ်တဲ့ တန်ဖိုးတွေ၊ ညာဘက်မှာ ပိုကြီးတဲ့ တန်ဖိုးတွေ ရှိပါတယ်။

စည်းမျဉ်းက တူပြီး ထည့်ထားတဲ့ နေရာပဲ ကွာပါတယ်။ ဒါကြောင့် quicksort ရဲ့ recursion tree က ဖွဲ့စည်းပုံအရ BST တစ်ခု ဖြစ်ပါတယ်။

ဥပမာ 4: Best case နဲ့ worst case recursion tree

Best case: pivot က sub-array တိုင်းကို အရွယ်အစား (နီးပါး) တူတဲ့ တစ်ဝက်စီ ခွဲပေးပါတယ်။

n = 7 အတွက် [5, 1, 7, 6, 3, 2, 4] ကို ယူကြည့်ပါ။ နောက်ဆုံး element ကို pivot အဖြစ် သုံးရင် partition တိုင်းက သူ့ အပိုင်းကို တူညီတဲ့ တစ်ဝက် နှစ်ခု ခွဲပေးလို့ tree က ညီညီမျှမျှ (balanced) ဖြစ်ပါတယ်: log2(7) က 2.8 ခန့် ဖြစ်လို့ level 3 ခု လိုပါတယ်။

[5, 1, 7, 6, 3, 2, 4] ပေါ်မှာ နောက်ဆုံး element ကို pivot အဖြစ် သုံးတဲ့ quicksort ပါ။ Partition တိုင်းက သူ့ အပိုင်းကို တူညီတဲ့ တစ်ဝက် နှစ်ခု ခွဲပါတယ်။ ခေါ်မှုတွေက level 3 ခု ဖြစ်ပါတယ်။ 4 ရဲ့ ဘယ်ဘက်မှာ 2၊ ညာဘက်မှာ 6 ရှိပါတယ်။ 2 ရဲ့ ဘယ်ဘက်မှာ 1၊ ညာဘက်မှာ 3 ရှိပါတယ်။ 6 ရဲ့ ဘယ်ဘက်မှာ 5၊ ညာဘက်မှာ 7 ရှိပါတယ်။ 1, 3, 5, 7 က တန်ဖိုး တစ်ခုတည်း ပါတဲ့ ခေါ်မှုတွေပါ။ 4 2 1 3 6 5 7 level 1 level 2 level 3 one value: already in place (base case)

Level တစ်ခုစီမှာ အပိုင်းတွေ တစ်ဝက် ဖြစ်သွားလို့ တန်ဖိုး 7 ခုအတွက် ခေါ်မှု level 3 ခုပဲ လိုပါတယ်။

ပုံထဲက “level 1”၊ “level 2”၊ “level 3” က အဆင့် 1၊ 2၊ 3 ကို ဆိုလိုပြီး “one value: already in place (base case)” က တန်ဖိုး တစ်ခုတည်း: နေရာမှန် ရောက်ပြီးသား (base case) လို့ ဆိုလိုပါတယ်။

စုစုပေါင်း အလုပ်: level တစ်ခုကို O(n) x level log n ခု = O(n log n)။

Worst case: pivot က အမြဲ အငယ်ဆုံး (ဒါမှမဟုတ် အကြီးဆုံး) element ဖြစ်နေပါတယ်။

စီပြီးသား input [1, 2, 3, 4, 5] မှာ နောက်ဆုံး element ကို pivot အဖြစ် ရွေးရင် partition တိုင်းက အကုန်လုံးကို တစ်ဖက်တည်းမှာ ထားပါတယ်:

စီပြီးသား array [1, 2, 3, 4, 5] ပေါ်မှာ နောက်ဆုံး element ကို pivot အဖြစ် သုံးတဲ့ quicksort ပါ။ Pivot တိုင်းက သူ့ အပိုင်းထဲမှာ အကြီးဆုံး တန်ဖိုး ဖြစ်လို့ ကျန်တာ အားလုံး သူ့ ဘယ်ဘက်ကို ရောက်ပါတယ်။ ခေါ်မှုတွေက level 5 ခု ဖြစ်ပါတယ်။ 5 ရဲ့ ဘယ်ဘက်မှာ 4၊ 4 ရဲ့ ဘယ်ဘက်မှာ 3၊ 3 ရဲ့ ဘယ်ဘက်မှာ 2၊ 2 ရဲ့ ဘယ်ဘက်မှာ 1 ရှိပါတယ်။ 1 က တန်ဖိုး တစ်ခုတည်း ပါတဲ့ ခေါ်မှုပါ။ 5 4 3 2 1 level 1 level 2 level 3 level 4 level 5 one value: already in place (base case)

Pivot တိုင်းက သူ့ အပိုင်းထဲမှာ အကြီးဆုံး တန်ဖိုး ဖြစ်လို့ ခေါ်မှု တစ်ခုစီက တန်ဖိုး တစ်ခုစီကိုပဲ ခွဲထုတ်ပါတယ်: တန်ဖိုး 5 ခုအတွက် level 5 ခု လိုပါတယ်။

ပုံထဲက English စာတွေက အပေါ်က ပုံနဲ့ အတူတူပါပဲ: “level 1” ကနေ “level 5” အထိက အဆင့် 1 ကနေ 5 အထိကို ဆိုလိုပါတယ်။

Tree က တစ်ဖက်စောင်း ဖြစ်နေပါတယ်: log n အစား level n ခု နက်ပါတယ်။ စုစုပေါင်း အလုပ်: level တစ်ခုကို O(n) x level n ခု = O(n^2)။ ဒါက BST ထဲကို တန်ဖိုးတွေကို စီပြီးသား အစဉ်အတိုင်း ထည့်တဲ့အခါ ဖြစ်တဲ့ ပြဿနာနဲ့ အတူတူပါပဲ: tree က ညီညီမျှမျှ ပုံစံ မဖြစ်ဘဲ ကွင်းဆက် တစ်ကြောင်းလို ဖြစ်သွားပါတယ်။

Worst case ကို လျှော့ချနည်းများ (ဒီနည်းတွေ ရှိတယ်ဆိုတာ သိထားရုံပါ၊ ကိုယ်တိုင် ရေးစရာ မလိုပါဘူး):

  • Pivot ကို ကျပန်း ရွေးပါ။
  • ရွေးထားတဲ့ element သုံးခု (ဥပမာ ပထမ၊ အလယ်နဲ့ နောက်ဆုံး) ရဲ့ median (အလယ် တန်ဖိုး) ကို ရွေးပြီး အဲဒီ တန်ဖိုးကို pivot အဖြစ် သုံးပါ။

ဘယ်နည်းကမှ worst case ကို လုံးဝ မဖယ်ရှားနိုင်ပေမယ့် လက်တွေ့ input တွေမှာ worst case ဖြစ်ဖို့ အလွန် နည်းသွားစေပါတယ်။

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

Q1. Array [5, 3, 8, 4, 2, 7, 1, 6] ကို နောက်ဆုံး element (6) ကို pivot အဖြစ် သုံးပြီး partition လုပ်ပါ။ ဒီ partition အဆင့် တစ်ခု အပြည့် ပြီးတဲ့အခါ pivot ရဲ့ နောက်ဆုံး index က ဘာလဲ။

Q2. နောက်ဆုံး element ကို pivot အဖြစ် အမြဲ ရွေးတဲ့အခါ ဘယ် input က quicksort ကို O(n^2) ဖြစ်စေသလဲ။

Q3. Quicksort ရဲ့ average-case time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) က ဘာလဲ။

Q4. Pivot P နဲ့ partition အဆင့် တစ်ခု အပြည့် ပြီးတဲ့အခါ P ရဲ့ နေရာအကြောင်း ဘာက မှန်သလဲ။

Q5. Recursion လုပ်နေစဉ် quicksort က element 1 ခုပဲ ပါတဲ့ sub-array ကို ရောက်လာပါတယ်။ နောက်ဘာ ဖြစ်မလဲ။

Q6. ဒီ algorithm တွေထဲက ဘယ်ဟာက recursive ဖြစ်သလဲ။

Q7. နောက်ဆုံး element ကို pivot အဖြစ် သုံးတဲ့အခါ စီပြီးသား input ပေါ်မှာ quicksort က ဘာကြောင့် O(n log n) မရနိုင်တာလဲ။

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

ဒီစာမျက်နှာက trace တိုင်းက partition အဆင့် တစ်ခု ပါ: partition ဖြတ်ကြည့်မှု တစ်ခေါက်ပဲ ဖြစ်ပါတယ်။ Recursion tree တစ်ခုလုံးကို trace လုပ်ခိုင်းတာ မဟုတ်ပါဘူး: recursion tree က နားလည်ဖို့ ပြထားတဲ့ ဥပမာ သက်သက်ပါ။

Trace 1: Element 8 ခုပါတဲ့ array ကို partition လုပ်ခြင်း

[8, 3, 6, 1, 4, 9, 2, 5] ကို နောက်ဆုံး element (5) ကို pivot အဖြစ် သုံးပြီး partition လုပ်ပါ။ i က -1 ကနေ စပြီး j က index 0 ကနေ 6 အထိ ဖြတ်ကြည့်ပါတယ်။

Trace: အတန်း တစ်ခုစီအတွက် i ရဲ့ တန်ဖိုးအသစ်နဲ့ အဲဒီ အဆင့် ပြီးနောက် array ရဲ့ အခြေအနေကို ဖြည့်ပါ။

အဆင့်jarr[j]arr[j] <= 5?လုပ်ဆောင်ချက်ပြီးနောက် iပြီးနောက် array
1 0 8 မဟုတ် ကျော် [8, 3, 6, 1, 4, 9, 2, 5]
2 1 3 ဟုတ် i++, swap(i, j)
3 2 6 မဟုတ် ကျော် [3, 8, 6, 1, 4, 9, 2, 5]
4 3 1 ဟုတ် i++, swap(i, j)
5 4 4 ဟုတ် i++, swap(i, j)
6 5 9 မဟုတ် ကျော် [3, 1, 4, 8, 6, 9, 2, 5]
7 6 2 ဟုတ် i++, swap(i, j)
နောက်ဆုံး -- -- -- swap(i+1, pivot) --

Pivot (5) ရဲ့ နောက်ဆုံး index:

Trace 2: Element 6 ခုပါတဲ့ array ကို partition လုပ်ခြင်း

[7, 2, 9, 1, 6, 4] ကို နောက်ဆုံး element (4) ကို pivot အဖြစ် သုံးပြီး partition လုပ်ပါ။ i က -1 ကနေ စပြီး j က index 0 ကနေ 4 အထိ ဖြတ်ကြည့်ပါတယ်။ arr[j] <= 4? ကော်လံမှာ yes (ဟုတ်တယ်) ဒါမှမဟုတ် no (မဟုတ်ဘူး) ကို English လို ရိုက်ထည့်ပါ။

Trace: Partition ကို အဆင့်ဆင့် လုပ်ကြည့်ပါ။ အဆင့်တိုင်း ပြီးနောက် i ကို ဖြည့်ပြီး swap လုပ်တဲ့ အဆင့်တိုင်းမှာ array ရဲ့ အခြေအနေကို ဖြည့်ပါ။

အဆင့်jarr[j]arr[j] <= 4?ပြီးနောက် iပြီးနောက် array
1 0 7 [7, 2, 9, 1, 6, 4]
2 1 2
3 2 9 [2, 7, 9, 1, 6, 4]
4 3 1
5 4 6 [2, 1, 9, 7, 6, 4]
နောက်ဆုံး -- -- swap(i+1, pivot) --

Pivot (4) ရဲ့ နောက်ဆုံး index: ။ ဘယ်ဘက် sub-array: ။ ညာဘက် sub-array:

Fill in the Prose (ရှင်းလင်းချက်ထဲက ကွက်လပ် ဖြည့်ခြင်း)

Quicksort က ရှင်းပြနိုင်ဖို့ပဲ လိုတဲ့ ခေါင်းစဉ် ဖြစ်လို့ ပုံမှန် Code Completion (code ကွက်လပ် ဖြည့်ခြင်း) လေ့ကျင့်ခန်းအစား ဒီအပိုင်းမှာ ပျောက်နေတဲ့ အဓိက term တွေကို ဖြည့်ပြီး ရေးထားတဲ့ ရှင်းလင်းချက်ကို ပြည့်စုံအောင် လုပ်ရပါမယ်။ ဒီစာပိုဒ်က “quicksort ဘယ်လို အလုပ်လုပ်လဲ ဖော်ပြပါ” ဆိုတဲ့ မေးခွန်းရဲ့ အဖြေ ပုံစံအတိုင်း ရေးထားတာမို့ ဖြည့်နိုင်သွားရင် အလွတ် ပြန်ရေး လေ့ကျင့်ပါ။

ကွက်လပ် ဖြည့်ပါ: quicksort က array ကို ဘယ်လို စီလဲဆိုတဲ့ ဖော်ပြချက်ကို ပြည့်စုံအောင် ဖြည့်ပါ။ ကွက်လပ်တွေကို English စကားလုံးနဲ့ ရိုက်ထည့်ပါ: English စာကြောင်းထဲမှာ ဝင်မယ့် ပုံစံအတိုင်း စာလုံး အသေးနဲ့ ရိုက်ပါ (ဥပမာ ကြိယာ ဆိုရင် "sorts" လို -s ပါတဲ့ ပုံစံ)။

Quicksort က array ကို စီတဲ့အခါ ပထမဆုံး လို့ ခေါ်တဲ့ element တစ်ခုကို ရွေးပါတယ်။ ပြီးရင် array ကို လုပ်ပါတယ်: အဲဒီ element ထက် ငယ်တဲ့ ဒါမှမဟုတ် ညီတဲ့ တန်ဖိုး အားလုံးက ဘက်ကို ရောက်ပြီး ပိုကြီးတဲ့ တန်ဖိုး အားလုံးက ဘက်ကို ရောက်ပါတယ်။ ဒီအဆင့် ပြီးတဲ့အခါ pivot က သူ့ရဲ့ sorted နေရာမှာ ရှိနေပါပြီ။ ပြီးရင် ဘက်တစ်ဖက်စီပေါ်မှာ quicksort ကို ခေါ်ပါတယ်။ Sub-array တစ်ခုမှာ element ခု ဒါမှမဟုတ် 0 ခုပဲ ရှိတော့ရင် ဒီလုပ်ငန်းစဉ် ရပ်ပါတယ်။ ဒါက case ပါ။

ကိုယ့်ဘာသာ အမှတ်ပေးတဲ့အခါ အဓိပ္ပာယ် မပြောင်းရင် လက်ခံနိုင်တဲ့ တခြား စကားလုံးများ: “final” / “correct”; “recursively” / “recursive”; “base” / “terminating”။

Spot the Claim (ပြောဆိုချက် မှန်မမှန် ခွဲခြားခြင်း)

ဒီမှာ “bug” (code ထဲက အမှား) တွေက code ထဲမှာ မဟုတ်ဘဲ အယူအဆမှာ ရှိပါတယ်: မှန်သလိုလို ထင်ရပေမယ့် မှားနေတဲ့ ပြောဆိုချက်တွေ၊ ဒါမှမဟုတ် မှန်ပေမယ့် ကျောင်းသားတွေ သံသယ ဖြစ်တတ်တဲ့ ပြောဆိုချက်တွေပါ။ ပြောဆိုချက် တစ်ခုစီ မှန်လား မှားလား ဆုံးဖြတ်ပြီး ရှင်းလင်းချက်ကို ဖတ်ပါ။

ပြောဆိုချက် 1. "Quicksort က အမြဲ O(n log n) အချိန်နဲ့ run ပါတယ်။"

ပြောဆိုချက် 2. "ပထမ partition အဆင့် ပြီးတဲ့အခါ pivot က စီပြီးသား array ထဲက သူ့ရဲ့ နောက်ဆုံး နေရာမှာ ရှိနေပါပြီ။"

ပြောဆိုချက် 3. "Quicksort က input ဘယ်လိုပဲ ဖြစ်ဖြစ် memory ပမာဏ အတူတူပဲ သုံးပါတယ်။"

ပြောဆိုချက် 4. "အလယ် element ကို pivot အဖြစ် အမြဲ ရွေးရင် quicksort က O(n^2) ကို ဘယ်တော့မှ မရောက်နိုင်ပါဘူး။"

ပြောဆိုချက် 5. "ပျမ်းမျှအားဖြင့် merge sort က quicksort ထက် memory အပို ပိုလိုပါတယ်။"

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

ဒီလေ့ကျင့်ခန်းတွေမှာ ပြီးသွားပြီဖြစ်တဲ့ partition ဒါမှမဟုတ် ပြီးသွားပြီဖြစ်တဲ့ recursion tree ကို ပေးထားပြီး အဲဒီကနေ သတ်မှတ်ထားတဲ့ ရလဒ် တစ်ခုကို ဖတ်ယူခိုင်းပါတယ်။ Recursion တစ်ခုလုံးကို ကိုယ်တိုင် trace လုပ်စရာ မလိုပါဘူး။

ကြိုခန့်မှန်းပါ: [9, 3, 7, 1, 5] ပေါ်မှာ pivot 5 နဲ့ partition အဆင့် တစ်ခု လုပ်ပြီးတဲ့အခါ array က [3, 1, 5, 9, 7] ဖြစ်သွားပါတယ်။ ဘယ်ဘက် sub-array (pivot ရဲ့ ရှေ့က အပိုင်း) က ဘာလဲ။

ကြိုခန့်မှန်းပါ: အောက်က recursion tree က element 4 ခုပါတဲ့ array ပေါ်မှာ quicksort run တဲ့အခါ ရွေးခဲ့တဲ့ pivot တစ်ခုစီကို ပြထားပါတယ်။ နောက်ဆုံး စီပြီးသား array က ဘာလဲ။

       3
      / \
     1   4
      \
       2

ကြိုခန့်မှန်းပါ: [5, 3, 8, 4, 2, 7, 1, 6] ပေါ်မှာ pivot 6 နဲ့ partition အဆင့် တစ်ခု လုပ်ပြီးတဲ့အခါ pivot က ဘယ်နေရာကို ရောက်သွားသလဲ။ သူ့ index ကို ဖြေပါ။

ကိုးကားရန်: Java နဲ့ ရေးထားတဲ့ Quicksort

ဒီ code က အပေါ်မှာ ဖော်ပြခဲ့တဲ့ algorithm ကို Java နဲ့ ရေးထားတဲ့ ပုံစံပါ။ စာမေးပွဲမှာ ဒီ code ကို အလွတ် ပြန်ရေးခိုင်းတာ မရှိပါဘူး၊ ဒီစာမျက်နှာက လေ့ကျင့်ခန်း တစ်ခုမှလည်း ဒီ code ကို ရေးခိုင်းတာ မရှိပါဘူး။ Quicksort ကို ကိုယ်တိုင် run ကြည့်နိုင်ဖို့ (ဥပမာ array အကြီးကြီးတွေမှာ bubble sort နဲ့ မြန်နှုန်း နှိုင်းယှဉ်ဖို့) နဲ့ IA project မှာ မြန်မြန် စီဖို့ လိုတဲ့ ကျောင်းသားတွေ ပြင်သုံးနိုင်ဖို့ ပေးထားတာပါ။

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {                            // base case: 0 or 1 elements
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);     // sort left sub-array
        quickSort(arr, pivotIndex + 1, high);    // sort right sub-array
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];                        // choose last element as pivot
    int i = low - 1;                              // right edge of smaller section
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];                    // swap arr[i] and arr[j]
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];                        // place pivot in correct position
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;                                 // return pivot's final index
}

def quick_sort(arr, low, high):
    if low < high:                               # base case: 0 or 1 elements
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)    # sort left sub-array
        quick_sort(arr, pivot_index + 1, high)   # sort right sub-array

def partition(arr, low, high):
    pivot = arr[high]                            # choose last element as pivot
    i = low - 1                                  # right edge of smaller section
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            temp = arr[i]                        # swap arr[i] and arr[j]
            arr[i] = arr[j]
            arr[j] = temp
    temp = arr[i + 1]                            # place pivot in correct position
    arr[i + 1] = arr[high]
    arr[high] = temp
    return i + 1                                 # return pivot's final index

Array တစ်ခုလုံးကို စီဖို့ quickSort(data, 0, data.length - 1) ကို ခေါ်ပါ (Python မှာ quick_sort(data, 0, len(data) - 1)): ပထမ ခေါ်မှုက array တစ်ခုလုံးကို ယူပြီး အဲဒီကနေ sub-array တွေကို recursion က ဆက်ကိုင်တွယ်ပေးပါတယ်။

Practice Exercises (လေ့ကျင့်ခန်းများ)

အောက်က လေ့ကျင့်ခန်း တိုင်းက explain / trace / compare (ရှင်းပြ / တစ်ဆင့်ချင်း လိုက်ကြည့် / နှိုင်းယှဉ်) မေးခွန်းတွေပါ။ Quicksort ကို အစကနေ ကိုယ်တိုင် ရေးခိုင်းတာ မရှိပါဘူး: အဲဒါက ဒီခေါင်းစဉ်အတွက် အကဲဖြတ်တဲ့ နယ်ပယ် ပြင်ပမှာပါ။ “[2 marks]” လို mark allocation (မေးခွန်း တစ်ခုစီအတွက် ပေးတဲ့ အမှတ်) တွေက ဒီ site လက်ရှိ လိုက်နာနေတဲ့ IB Paper 2 (IB Computer Science စာမေးပွဲမှာ ဖြေရတဲ့ မေးခွန်းစာစောင်တွေထဲက တစ်စောင်) ရဲ့ ပုံစံအတိုင်းပါ။ IB သင်တန်း မတက်တဲ့သူတွေကတော့ မေးခွန်း တစ်ခုစီ ဘယ်လောက် အလေးပေးရလဲ ပြတဲ့ လမ်းညွှန်အဖြစ် သုံးနိုင်ပါတယ်။

Core (အခြေခံ အဆင့်)

1. Quicksort algorithm မှာ “pivot” ဆိုတဲ့ term ကို Define (အဓိပ္ပာယ်ကို တိတိကျကျ ဖွင့်ဆိုပါ) လုပ်ပါ။ [2 marks]

2. Recursive quicksort algorithm ရဲ့ base case ကို State (ဖော်ပြပါ) လုပ်ပါ။ [1 mark]

3. Quicksort algorithm ရဲ့ အဓိက အဆင့်တွေကို Outline (အကျဉ်းချုပ် ဖော်ပြပါ) လုပ်ပါ။ [3 marks]

4. Array [6, 2, 8, 4, 1, 3] ပေါ်မှာ နောက်ဆုံး element (3) ကို pivot အဖြစ် သုံးပြီး partition အဆင့် တစ်ခုကို Trace လုပ်ပါ။ Comparison (တန်ဖိုး နှစ်ခုကို နှိုင်းယှဉ်ခြင်း) တစ်ခုစီ ပြီးနောက် array ရဲ့ အခြေအနေနဲ့ pivot ရဲ့ နောက်ဆုံး နေရာကို ပြပါ။ [4 marks]

Extension (တိုးချဲ့ အဆင့်)

5. Quicksort algorithm က array ကို ဘယ်လို စီလဲဆိုတာ Describe (ဖော်ပြရှင်းပြပါ) လုပ်ပါ။ Code ရေးစရာ မလိုပါဘူး။ [5 marks]

6. Quicksort ရဲ့ average case က O(n log n) ဖြစ်ပေမယ့် worst-case time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) က ဘာကြောင့် O(n^2) ဖြစ်လဲဆိုတာ Explain လုပ်ပါ။ [3 marks]

7. Quicksort နဲ့ bubble sort ကို Compare (နှစ်ခုကို ယှဉ်ပြီး ဖော်ပြပါ) လုပ်ပါ။ သင့်အဖြေမှာ time complexity နဲ့ sort တစ်ခုစီကို ဘယ်အချိန်မှာ ပိုသုံးသင့်လဲဆိုတာ ပါရပါမယ်။ [4 marks]

8. Quicksort ရဲ့ recursion tree နဲ့ binary search tree ကြားက ဖွဲ့စည်းပုံ ဆိုင်ရာ ဆက်စပ်မှုကို Explain လုပ်ပါ။ [3 marks]

Exam-Style (စာမေးပွဲ ပုံစံ မေးခွန်း၊ 14 marks)

9. ကျောင်း အားကစားပွဲ တစ်ခုမှာ အချိန်မှတ်သူ တစ်ယောက်က အပြေးသမား 32 ယောက်ရဲ့ ပန်းဝင်ချိန်တွေကို မှတ်ထားပြီး အဲဒီ စာရင်းကို အမြန်ဆုံးကနေ အနှေးဆုံးအထိ စီဖို့ လိုပါတယ်။

(a) ဒီ စီပြီးသား စာရင်းကို ရဖို့ bubble sort အစား quicksort ကို သုံးတဲ့ အားသာချက် တစ်ခုကို State လုပ်ပါ။ [2 marks]

(b) Bubble sort နဲ့ နှိုင်းယှဉ်ရင် quicksort ရဲ့ အားနည်းချက် တစ်ခုကို State လုပ်ပါ။ [2 marks]

(c) Code မရေးဘဲ အချိန်မှတ်သူရဲ့ ပန်းဝင်ချိန် array ကို quicksort algorithm က ဘယ်လို စတင် စီမလဲဆိုတာ Describe လုပ်ပါ။ Pivot ရဲ့ အခန်းကဏ္ဍနဲ့ partition လုပ်ငန်းစဉ်ကို ထည့်ပြီး ဒေတာပေါ်က တကယ့် အဆင့် တစ်ခုကို ကိုးကားပါ။ [4 marks]

(d) အချိန်မှတ်သူရဲ့ software က အပြေးသမား တစ်ယောက် ပန်းဝင်တိုင်း စာရင်းကို စီပြီးသား ဖြစ်လို့ ပွဲအဆုံးမှာ array က အစဉ်အတိုင်း နီးပါး ဖြစ်နေပါတယ်။ ဒီလို စီလုနီးပါး input ပေါ်မှာ quicksort (နောက်ဆုံး element ကို pivot အဖြစ် သုံးရင်) က ဘာကြောင့် ကောင်းကောင်း အလုပ် မလုပ်နိုင်လဲဆိုတာ Explain လုပ်ပါ။ [2 marks]

(e) Quicksort ရဲ့ recursion tree နဲ့ binary search tree ကြားက ဖွဲ့စည်းပုံ ဆိုင်ရာ ဆက်စပ်မှုကို Explain လုပ်ပါ။ [2 marks]

(f) Merge sort က စီဖို့ input အရွယ်အစားနဲ့ တူတဲ့ array အပို တစ်ခု လိုပါတယ်။ Quicksort နဲ့ နှိုင်းယှဉ်ရင် ဒါက ဘာကြောင့် အားနည်းချက် ဖြစ်လဲဆိုတာ Explain လုပ်ပါ။ [2 marks]

စိတ်ဝင်စားရင် ထပ်လေ့လာရန်

Quicksort အတွက် GitHub Classroom assignment (အလိုအလျောက် စစ်ဆေးတဲ့ test တွေပါတဲ့ programming လေ့ကျင့်ခန်း) မရှိပါဘူး။ ဒီခေါင်းစဉ်ကို စာရွက်ပေါ်မှာ ဖော်ပြတာ၊ trace လုပ်တာ၊ နှိုင်းယှဉ်တာနဲ့ပဲ လေ့လာပါတယ်: quicksort code ရေးတာကို အကဲဖြတ်တာ မရှိပါဘူး။ စိတ်ဝင်စားရင် အပေါ်က ကိုးကားစရာ code ကို run ကြည့်ပြီး အရင်က ရေးခဲ့တဲ့ sort တွေထက် ဘယ်လောက် ပိုမြန်လဲဆိုတာ ကိုယ်တိုင် ကြည့်နိုင်ပါတယ်။

  • ကိုးကားစရာ quicksort code ကို အရင် sorting သင်ခန်းစာက bubble sort နဲ့ selection sort code တွေနဲ့ အတူ ကိုယ့် IDE (code ရေးပြီး run ဖို့ သုံးတဲ့ software) ဒါမှမဟုတ် Codespace (browser ထဲမှာ code ရေးပြီး run လို့ရတဲ့ GitHub ရဲ့ နေရာ) ထဲကို copy ကူးပါ။ ပေးထားတဲ့ အရွယ်အစား ရှိတဲ့ ကျပန်း array တစ်ခု ထုတ်ပေးတဲ့ အကူ method တစ်ခု ထည့်ပါ။
  • System.nanoTime() ကို သုံးပြီး အရွယ်အစား 100၊ 1,000 နဲ့ 10,000 ရှိတဲ့ array တွေပေါ်မှာ sort တစ်ခုစီရဲ့ ကြာချိန်ကို တိုင်းပါ။ ရလဒ်တွေကို မှတ်ထားပါ။
  • ကြာချိန်တွေကို graph ဆွဲပါ ဒါမှမဟုတ် ဇယား လုပ်ပါ။ n = 10,000 ရောက်တဲ့အခါ O(n^2) နဲ့ O(n log n) ကြား ကွာခြားချက်ကို ရှင်းရှင်း မြင်ရပါလိမ့်မယ်။
  • ကိုယ့် IA project မှာ ဒေတာ စီဖို့ လိုရင် (အမှတ်ဇယား၊ အဆင့် သတ်မှတ်ခြင်း၊ ငွေပေးငွေယူ မှတ်တမ်းတွေကို အစဉ်လိုက် စီခြင်း စသဖြင့်) ဒီ ကိုးကားစရာ code ကို တရားဝင် သုံးလို့ရတဲ့ အစိတ်အပိုင်း တစ်ခုအဖြစ် သုံးနိုင်ပါတယ်: အစကနေ ပြန်ရေးမယ့်အစား ပြင်သုံးပါ။

ဒီ ထပ်လေ့လာမှုက လုံးဝ ကိုယ့်ဆန္ဒအလျောက်ပါ: test မရှိ၊ အလိုအလျောက် အမှတ်ပေးတာ မရှိ၊ တင်သွင်းစရာလည်း မရှိပါဘူး။

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

  • အရင် သိထားရမှာများ: Recursion: base case၊ recursive case၊ call stack။ Quicksort က branching recursion (ခေါ်မှု တစ်ခါမှာ သူ့ကိုယ်သူ တစ်ကြိမ်ထက် ပိုခေါ်တဲ့ recursion) ရဲ့ စံ ဥပမာ ဖြစ်ပါတယ်။
  • အရင် သိထားရမှာများ: Sorting Algorithms (ဒေတာကို အစဉ်လိုက် စီတဲ့ algorithm များ): bubble sort နဲ့ selection sort က quicksort ကို နှိုင်းယှဉ်တဲ့ O(n^2) အခြေခံ sort တွေပါ။
  • အရင် သိထားရမှာများ: Big-O Notation: best / average / worst case တွေကို နားလည်ဖို့ O(n log n) နဲ့ O(n^2) ကြား ကွာခြားချက်ကို သိထားရပါမယ်။
  • အရင် သိထားရမှာများ: Binary Search Trees: partition က “ငယ်တာ ဘယ်ဘက် / ကြီးတာ ညာဘက်” စည်းမျဉ်း အတူတူကို သုံးပါတယ်။ BST နဲ့ ဆက်စပ်ပုံက IB syllabus မှာ အမည်တပ်ပြီး ဖော်ပြထားတဲ့ linking question တစ်ခုပါ။
  • အရင် သိထားရမှာများ: 1D Arrays: index တွေ၊ swap တွေနဲ့ sub-array အကြောင်း စဉ်းစားပုံက partition အဆင့်ကို အလုပ်လုပ်စေပါတယ်။
  • ဆက်စပ်တာ: Searching Algorithms (ရှာဖွေရေး algorithm များ): binary search (တစ်ဝက်စီ ခွဲပြီး ရှာနည်း) က O(log n) / divide and conquer (ပြဿနာကို အပိုင်းလေးတွေ ခွဲပြီး ဖြေရှင်းနည်း) အယူအဆ နောက်တစ်ခုပါ၊ ဒီတစ်ခါတော့ မစီရသေးတဲ့ array မှာ မဟုတ်ဘဲ စီပြီးသား array မှာ သုံးတာပါ။
  • နောက်ပိုင်း: Merge sort: ဒီသင်တန်းမှာ ကိုယ်တိုင် မရေးရပေမယ့် နှိုင်းယှဉ်ဖို့ ဖော်ပြထားတာပါ။ Worst case မှာတောင် O(n log n) ကို အာမခံပေမယ့် input အရွယ်အစားနဲ့ တူတဲ့ array အပို တစ်ခု လိုအပ်ပါတယ်။

© 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.