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

Translator: Batchansaa Batzorig Reviewer: Sundari Enkhtugs

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.

гэнэт 1280 өөр өөр номны ачаа ирлээ.

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.

Нэг үзүүрийн эхний 2 номноос эхэлж болох юм.

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

Хэрэв эхний 2 ном нь зөв байрлалд байвал байгаагаар нь орхи.

Otherwise, swap them.

Үгүй бол байрыг нь соль.

Then, look at the second and third books,

Дараа нь 2 болон 3 дахь номнуудад өмнөх үйлдлийг

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.

Энэхүү аргыг "Хөөсөн ангилалт" гэдэг.

It's simple but slow.

Энэ нь амархан боловч их цаг шаарддаг.

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

Хамгийн эхэнд 1279 харьцуулалт хийгдэнэ.

then 1,278, and so on,

Дараа нь 1278 гэсээр

adding up to 818,560 comparisons.

нийт 818,560 харьцуулалт хийгдэнэ.

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

Хэрэв харьцуулалт тус бүрт нэг сэкунд зарцуулвал, нийт 9 өдөр үргэлжлэнэ.

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

2 дахь арга нь эхний 2 номыг ангилж эхэлнэ.

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

Үүний дараа 3 дахь номыг 2 дахь номтой харьцуулна.

If it belongs before the second book, swap them,

Хэрэв 3 дугаар нь 2 дахь номныхоо өмнө байх хэрэгтэй бол байрыг нь соль.

then compare it with the book in the first spot,

Үүний дараа 1-р байранд байгаа номтой харьцуулаад

and swap again if needed.

солих шаардлагатай бол байрыг нь солино.

Now you've sorted the first three books.

Одоо эхний 3 ном ангилагдчихлаа.

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.

ангилагдсан номнуудын дунд зөв байранд нь оруулна.

This is called Insertion Sort.

Үүнийг "Нэмэгдэх ангилалт" гэж нэрлэнэ.

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

"Хөөсөн ангилалт" - аас ялгаатай нь 2 ном болгоныг харьцуулах шаардлагагүй.

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,

409280 болж

taking almost five days.

ойролцоогоор 5 өдөр шаардана.

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.

"Нэмэгдэх ангилал" мэтийг ашиглан хурдан ангилна.

Each round of partitioning requires about 1,280 comparisons.

Хуваагдалт болгон 1280 харьцуулалт хийгдэнэ.

If your partitions are pretty balanced,

Хэрэв чиний хуваалтууд тэгш хэмтэй бол

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

нийт номоо 10 аар хуваасан 128 жижиг цуваа болгоход 7 үе шаардна

or 8,960 seconds.

эсвэл 8960 сэкунд.

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

Жижиг цуваануудыг ангилах нь тус тус 22 сэкунд шаардна.

All in all, this method known as QuickSort

Энэхүү "Хурдан ангилалт" нь

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

бүх номыг 3 цаг хагаст ангилж дуусгана.

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

Ийм учраас "Хурдан ангилалт" нь хамгийн ашигтай аргуудын нэг бөгөөд

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.

Номын санчийн бас нэгэн завгүй өдөр.