Sorting Algorithms — O(n²) နှင့် O(n log n) များကို နှိုင်းယှဉ်ခြင်း

နားလည်ထားရမယ့် အချက်

Sorting algorithm တွေကို ကျယ်ကျယ်ပြန့်ပြန့် နှစ်မျိုးခွဲလို့ရတယ်။ Simple algorithm တွေဖြစ်တဲ့ bubble sort၊ insertion sort တို့က neighbor element တွေကို ထပ်ခါထပ်ခါ compare လုပ်ပြီး ရွှေ့ပေးတာမို့ O(n²) time ကုန်တယ် — element n ခုစီအတွက် ကျန် element n ခုလောက်ကို scan ဖြတ်ရနိုင်လို့ပါ။ Insertion sort က ရှင်းလင်းတဲ့ ဥပမာတစ်ခုဖြစ်ပြီး sorted region ကို element တစ်ခုချင်းစီ တည်ဆောက်သွားတယ် — element အသစ်တစ်ခုကို ယူပြီး၊ ကြီးတဲ့ sorted element တွေကို left ဘက်ကနေ ကျော်ဖြတ်ရွှေ့ပြီး correct slot ကိုရောက်အောင် ထည့်ပေးတယ်။ ဒါက simple ပြီး data size သေးလေ၊ almost-sorted ဖြစ်လေ မြန်လေဖြစ်ပေမယ့် scale ကျယ်လာရင် ညံ့တယ် — input နှစ်ဆတိုးရင် work လေးဆလောက် တက်သွားနိုင်တယ်။ Efficient algorithm တွေဖြစ်တဲ့ merge sort၊ quicksort (နောက် lesson မှာ အသေးစိတ် လေ့လာမယ်) တို့က divide-and-conquer သုံးပြီး O(n log n) အထိ လျှော့ချနိုင်တယ် — comparison-based sorting အတွက် လက်တွေ့ ceiling ပဲ။ သတိထားသင့်တဲ့ property တစ်ခုက stability ပါ — stable sort ဆိုတာ equal ဖြစ်တဲ့ element တွေရဲ့ original relative order ကို ထိန်းသိမ်းပေးတဲ့ sort ပါ။ ဒါက search result တွေကို relevance score အရ sort လုပ်တဲ့အခါ တကယ့်လက်တွေ့ ကိုက်ညီတယ် — lesson နှစ်ခုက score 0.82 tie ဖြစ်နေရင် stable sort က publish date လို tie-breaking order အဟောင်းကို ဆက်ထိန်းပေးမယ်၊ unstable sort ကတော့ ဒီ order ကို ခန့်မှန်းလို့မရအောင် ရှုပ်ပစ်လိုက်နိုင်တယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform က learner search လုပ်တိုင်း search result တွေကို relevance score အရ sort လုပ်ပေးတယ်။ Insertion sort ကိုယ်တိုင်က result set အပြည့်အစုံအတွက် အလွန်ဖြေးတယ်၊ ဒါပေမယ့် ၎င်းရဲ့ stability requirement ကတော့ platform လိုအပ်ချက်နဲ့ တိုက်ရိုက်ကိုက်ညီတယ် — lesson နှစ်ခု relevance tie ဖြစ်ရင် user တွေက search တိုင်း result order ပြန်ရှုပ်နေတာထက် consistent ordering (publish date အလိုက်ဆိုပါစို့) ကို မျှော်လင့်ကြတယ်။ ဒီနေရာမှာ sorting algorithm ရွေးချယ်ခြင်းဆိုတာ speed တစ်ခုတည်းအတွက်မဟုတ်ဘဲ product requirement နဲ့ algorithm guarantee ဘယ်ဟာက ကိုက်ညီသလဲဆိုတာပါ။ Ranking pipeline တစ်ခုက run တိုင်း tie ကို မတူညီအောင် ချိုးဖျက်ရင် top result မှန်နေသေးလင့်ကစား result အပေါ် user ယုံကြည်မှု ကျဆင်းနိုင်တယ်။

O(n²) algorithm တွေ (bubble/insertion sort) က small/nearly-sorted data အတွက် ရိုးရှင်းပြီး လက်တွေ့ကျတယ်။
Insertion sort က sorted region ကို element တစ်ခုချင်း correct slot ထဲ ထည့်သွားတဲ့ နည်းလမ်းပါ။
Stable sort က equal element တွေရဲ့ original order ကို ထိန်းသိမ်းပေးတယ် — tie-breaking အတွက် အရေးကြီးတယ်။

အတူတူ စမ်းရေးကြည့်မယ်

python

def insertion_sort(arr):
    # O(n^2) worst/average case: for each element, shift larger
    # elements one position right until we find its correct slot.
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

result = insertion_sort([9, 3, 7, 1, 5])
print(result)

You should see

[1, 3, 5, 7, 9] ဟု sorted list တစ်ခု print ထုတ်ပေးမည်။

၅ မိနစ် စမ်းကြည့်

insertion_sort function ထဲမှာ comparison operation ကို count လုပ်ပေးမယ့် counter တစ်ခု ထည့်ကြည့်ပြီး၊ already-sorted list တစ်ခုနဲ့ reverse-sorted list တစ်ခုကို run လုပ်ကြည့်ပါ — comparison အရေအတွက်က ဘယ်လို ကွာခြားသလဲ။

သတိလေးတစ်ချက်

Insertion sort ကို large dataset (element ထောင်ချီ) အတွက် production code ထဲ တိုက်ရိုက်သုံးမိတတ်တယ် — O(n²) ဖြစ်လို့ data ကြီးလာတာနဲ့ latency ချက်ချင်း ကျယ်လာနိုင်တယ်။

Sort ကို 'stable' လား 'fast' လားဆိုတာ စစ်မကြည့်ဘဲ built-in sort function ကို default assume လုပ်တတ်တယ် — language အလိုက် stability guarantee ကွာနိုင်တယ်။

Wikipedia — Sorting algorithm — Data Structures & Algorithms