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

Translator: Deren Dlsoz Reviewer: Daban Q. Jaff

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.

ئەم نزیکبوونەوەیە پێی دەگوترێت ریزکردنی بڵق.

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.

تا ئەو کاتەی بە شێوەیەکی دروست دانرا لە نێوان ئەو کتێبانەی تا ئێستا پۆلێنکراون.

This is called Insertion Sort.

ئەمە پێی دەوترێت ڕیزکردنی دانان.

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

بە پێچەوانەی ڕیزکردنی بڵق، بە زۆری پێویستی بە بەراوردکردنی هەموو دوو کتێبێک نییە.

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.

هەر یەکێکیان بە خێرایی بەکارهێنانی ستراتیژیەکی تر، وەک ڕیزکردنی دانان.

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

هەموو ئەمانە، ئەم شێوازە ناسراوە بە ڕیزکردنی خێرا

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

لەبەر ئەوەیە ڕیزکردنی خێرا یەکێکە لە زۆرترین ستراتیژی کارامە

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.

تەنها ڕۆژێکی تری بەرز لە کتێبخانەکە.