What's the fastest way to alphabetize your bookshelf? - Chand John

Translator: Sanntint Tint Reviewer: Myo Aung

You work at the college library.

သင်က ကောလိပ်စာကြည့်တိုက်မှာ အလုပ်လုပ်တယ်။

You're in the middle of a quiet afternoon

တိတ်ဆိတ်တဲ့ နေ့လည်ခင်းတစ်ခုရဲ့ အလယ်မှာ

when suddenly a shipment of 1,280 different books arrives.

ရုတ်တရတ် စာအုပ် ၁၂၈၀ ပို့ဆောင်မှု ရောက်ရှိလာတယ်။

စာအုပ်တွေကို ရှည်လျားတဲ့ မျဉ်းဖြောင့်တစ်ခုအတိုင်း ချပစ်ခဲ့ပေမဲ့

The books have been dropped of in one long straight line,

but they're all out of order,

အားလုံးက အစီအစဥ်မကျဘဲ

and the automatic sorting system is broken.

အလိုအလျောက် စီတဲ့စနစ်က ပျက်သွားတယ်။

To make matters worse, classes start tomorrow,

ပိုဆိုးစေတာက အတန်းတွေက မနက်ဖြန်စမယ်၊

which means that first thing in the morning,

ဆိုလိုတာက မနက်ခင်းမှာ ပထမဆုံး အရာက

ဒီစာအုပ်တွေကို ရှာရင်း ကျောင်းသားတွေက အစုလိုက်အပြုံလိုက် ပေါ်လာမှာပါ။

students will show up in droves looking for these books.

How can you get them all sorted in time?

ဒါတွေအားလုံးကို အချိန်မီ ဘယ်လို ခွဲထုတ်မလဲ။

One way would be to start at one end of the line with the first pair of books.

နည်းလမ်းတစ်ခုက ပထမ စာအုပ် အတွဲနဲ့အတူ မျဥ်းတစ်ဖက်မှာ စတင်တာဖြစ်မယ်။

If the first two books are in order, then leave them as they are.

ပထမစာအုပ်နှစ်အုပ်က အစီအစဥ်ကျရင် ဒီအတိုင်း ထားလိုက်ပါ။

Otherwise, swap them.

မဟုတ်ရင် ဒါတွေကို နေရာလဲလိုက်ပါ။

Then, look at the second and third books,

ဒီနောက် ဒုတိယနဲ့ တတိယစာအုပ်တွေကို ကြည့်ပါ။

repeat the process,

ဒီလုပ်ငန်းစဉ်ကို ပြန်လုပ်ပြီး

and continue until you reach the end of the line.

အတန်း အဆုံးကို ရောက်သည်အထိ ဆက်လက်လုပ်ဆောင်ပါ။

At some point, you'll come across the book that should be last,

တစ်နေရာရာမှာ နောက်ဆုံး ဖြစ်သင့်တဲ့ စာအုပ်ကို သင် တွေ့ရှိပြိး

and keep swapping it with every subsequent book,

၎င်းနဲ့ဆိုင်တဲ့ အဆုံးကို ရောက်တဲ့အထိ အတန်းအောက်ကို ရွှေ့ပေးရင်း

moving it down the line until it reaches the end where it belongs.

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

Then, start from the beginning and repeat the process

နောက်ဆုံးမတိုင်မီ စာအုပ်ကို နေရာတကျဖြစ်စေဖို့

to get the second to last book in its proper place,

အစကနေပြီး လုပ်ငန်းစဥ်ကို ပြန်လုပ်ပြီး

and keep going until all books are sorted.

စာအုပ်အားလုံး ခွဲပြီးသည်အထိ ဆက်လုပ်သွားပါ။

This approach is called Bubble Sort.

ဒီနည်းလမ်းကို Bubble Sort လို့ ခေါ်ပါတယ်။

It's simple but slow.

ရိုးရှင်းပေမဲ့ နှေးတယ်။

You'd make 1,279 comparisons in the first round,

ပထမအကျော့မှာ နှိုင်းယှဉ်မှုပေါင်း ၁,၂၇၉ ခု ပြုလုပ်နိုင်ပြီး

then 1,278, and so on,

နောက်တော့ ၁,၂၇၈ ခု စစသည်ဖြင့်

adding up to 818,560 comparisons.

နှိုင်းယှဉ်မှုပေါင်း ၈၁၈,၅၆၀ ခု အထိ တိုးသွားတယ်။

If each took just one second, the process would take over nine days.

တစ်ခုစီက တစ်စက္ကန့်သာ ကြာရင် လုပ်ငန်းစဉ်က ကိုးရက်ကျော်ကြာမှာပါ။

A second strategy would be to start by sorting just the first two books.

ဒုတိယနည်းဗျူဟာက ပထမစာအုပ်နှစ်အုပ်ကိုပဲ စီတာနဲ့ စတင်မှာပါ။

Then, take the third book and compare it with the book in the second spot.

ဒီနောက် တတိယစာအုပ်ကို ယူပြီး ဒုတိယနေရာက စာအုပ်နဲ့ နှိုင်းယှဉ်တာပါ။

If it belongs before the second book, swap them,

ဒုတိယစာအုပ်ရှေ့မှာ သက်ဆိုင်ရင် ဒါတွေကို နေရာလဲလိုက်ပါ။

then compare it with the book in the first spot,

ပြီးရင် ပထမနေရာက စာအုပ်နဲ့ နှိုင်းယှဥ်ပါ။

and swap again if needed.

လိုအပ်ရင် ထပ်မံ နေရာလဲပါ။

Now you've sorted the first three books.

အခု ပထမဆုံး စာအုပ်သုံးအုပ်ကို စီပြီးသွားပြီ။

Keep adding one book at a time to the sorted sub-line,

စီထားတဲ့ အတန်းခွဲတွေထဲမှာ တစ်ကြိမ်ကို စာအုပ်တစ်အုပ် ဆက်ထည့်ပါ။

comparing and swapping the new book with the one before it

အခုချိန်ထိ စီထားတဲ့ စာအုပ်တွေကြားမှာ မှန်ကန်စွာ နေရာကျသည်အထိ

until it's correctly placed among the books sorted so far.

ရှေ့က တစ်အုပ်နဲ့ စာအုပ်အသစ်ကို နှိုင်းယှဉ်ပြီး လဲလှယ်ပါ။

ဒါကို Insertion Sort လို့ ခေါ်ပါတယ်။

This is called Insertion Sort.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

Bubble Sort နဲ့မတူတာက ဒါက များသောအားဖြင့် စာအုပ်တွဲတိုင်းကို ယှဉ်ဖို့ မလိုတာပါ။

On average, we'd expect to only need to compare each book

ပျမ်းမျှအနေနဲ့ စာအုပ်တစ်အုပ်စီကို ၎င်းရှေ့က လာတဲ့ စာအုပ်တွေရဲ့ ထက်ဝက်နဲ့ပဲ

to half of the books that came before it.

နှိုင်းယှဉ်ဖို့ လိုတယ်လို့ မျှော်လင့်တာပါ။

In that case, the total number of comparisons

ဒီအခြေအနေမှာ စုစုပေါင်း နှိုင်းယှဉ်မှုအရေအတွက်က

would be 409,280,

၄၀၉,၂၈၀ ခု ဖြစ်မယ်ဆိုရင်

taking almost five days.

ငါးရက် နီးပါးကြာပါတယ်။

You're still doing way too many comparisons.

များပြားလွန်းတဲ့ နှိုင်းယှဥ်မှုတွေ လုပ်နေတုန်းပါ။

Here's a better idea.

ဒီမှာ ပိုကောင်းတဲ့ စိတ်ကူးတစ်ခုပါ။

First, pick a random book.

ပထမဆုံး ကျပန်းစာအုပ်တစ်အုပ်ကို ရွေးပါ။

Call it the partition and compare it to every other book.

ဒါကို အပိုင်းခွဲ လို့ခေါ်ပြီး အခြား စာအုပ်တိုင်းနဲ့ ၎င်းကို နှိုင်းယှဉ်ပါ။

Then, divide the line

ဒီနောက် ဘယ်ဘက်ခြမ်းက အပိုင်းခွဲမှာ

by placing all the books that come before the partition on its left

အရင်လာတဲ့ စာအုပ်တွေအားလုံးနဲ့ ညာဘက် နောက်ပိုင်းလာတာတွေကို

and all the ones that come after it on its right.

နေရာချထားခြင်းအားဖြင့် အတန်းကို ပိုင်းလိုက်ပါ။

You've just saved loads of time

ဘယ်ဘက်က စာအုပ်တွေကို

by not having to compare any of the books on the left

ညာဘက်က ဘယ်စာအုပ်နဲ့မှ ထပ်ပြီး နှိုင်းယှဥ်စရာမလိုဘဲ

to any of the ones on the right ever again.

အချိန်များစွာ သက်သာစေတာပါ။

Now, looking only at the books on the left,

အခု ဘယ်ဘက်မှာရှိတဲ့ စာအုပ်တွေကိုပဲ ကြည့်နေရင်းက

you can again pick a random partition book

ကျပန်း အပိုင်းခွဲ စာအုပ်ကို ထပ်မံရွေးချယ်နိုင်ပြီး

and separate those books that come before it from those that come after it.

၎င်းရဲ့ နောက်ကလာတဲ့ စာအုပ်တွေကနေ ရှေ့ကလာတာတွေကို ခွဲထုတ်နိုင်တယ်။

You can keep creating sub-partitions like this

အတန်းခွဲလေးတွေ အတွဲလိုက်ရတဲ့အထီ ဒီလို အပိုင်းခွဲတွေ

until you have a bunch of small sub-lines,

ဆက်လက်ဖန်တီးနိုင်ပါတယ်။

each of which you'd sort quickly using another strategy, like Insertion Sort.

တစ်ခုချင်းစီကို Insertion Sort လို အခြား နည်းဗျူဟာသုံးရင်း အမြန် ခွဲထုတ်တာပါ။

Each round of partitioning requires about 1,280 comparisons.

အပိုင်းပိုင်းခွဲခြင်းတိုင်းဟာ နှိုင်းယှဉ်မှု ၁,၂၈၀ လောက်လိုအပ်တယ်။

If your partitions are pretty balanced,

အပိုင်းခွဲတွေက အတော်လေး ဟန်ချက်ညီရင်

dividing the books into 128 sub-lines of ten would take about seven rounds,

စာအုပ်တွေကို အတန်းခွဲ ၁၂၈ ခုပါတဲ့ ၁၀ တန်းက ခုနစ်ကျော့ သို့မဟုတ်

or 8,960 seconds.

၈,၉၆၀ စက္ကန့် ကြာမှာပါ။

Sorting these sub-lines would add about 22 seconds each.

ဒီအတန်း ခွဲတွေေကို စီခွဲတာက ၂၂ စက္ကန့်လောက် ပေါင်းထည့်မှာပါ။

All in all, this method known as QuickSort

ခြုံပြောရရင် QuickSortt လို့ခေါ်တဲ့ ဒီနည်းလမ်းက

could sort the books in under three and a half hours.

စာအုပ်တွေကို သုံးနာရီခွဲအတွင်း အမျိုးအစားခွဲနိုင်ပေမဲ့

But there's a catch.

မြှုပ်ကွက်တစ်ခုရှိတယ်။

Your partitions could end up lopsided, saving no time at all.

သင့်ရဲ့အပိုင်းခွဲတွေက အချိန်လုံးဝ မသက်သာစေဘဲ တစ်ဖက်စောင်းနင်းဖြစ်နိုင်တယ်။

Luckily, this rarely happens.

ကံကောင်းတာက ဒီလိုဖြစ်ခဲပါတယ်။

That's why QuickSort is one of the most efficient strategies

ဒါကြောင့် QuickSort ဟာ ယနေ့ခေတ် ပရိုဂရမ်မာတွေ အသုံးပြုတဲ့ အထိရောက်ဆုံး

used by programmers today.

နည်းဗျူဟာတွေထဲက တစ်ခုပါ။

They use it for things like sorting items in an online store by price,

ဈေးနှုန်းအရ အွန်လိုင်းစတိုးတစ်ခု ထဲက ပစ္စည်းတွေကို ခွဲထုတ်တာ သို့မဟုတ်

or creating a list of all the gas stations close to a given location

အကွာအဝေးအလိုက် ပေ;ထားတဲ့ တည်နေရာအနီးက ဓာတ်ဆီဆိုင်အားလုံးရဲ့စာရင်းကို ဖန်တီးတာလို

sorted by distance.

အရာတွေအတွက် ဒါကို အသုံးပြုတယ်။

In your case, you're done quick sorting with time to spare.

သင့်ကိစ္စမှာတော့ အပိုချိန်နဲ့အတူ အမြန်စီပြီးသွားပါပြီ။

Just another high-stakes day in the library.

စာကြည့်တိုက်မှာ နောက်ထပ် စွန့်စားရတဲ့ နေ့တစ်နေ့ပေါ့။