تۆ لە کتێبخانەی کۆلێژ کار دەکەیت. تۆ لە ناوەڕاستی نیورۆیەکی بێدەنگیت کاتێک لەناکاو بارێک لە ١٢٨٠ کتێبی جیاواز دەگات. کتێبەکان لەسه ر کەمکراوەتەوه لە هێڵی ڕاست و درێژ، بەڵام ھەمووی ڕیزبەندیان تێکچووە، و سیستەمی ڕیزکردنی ئۆتۆماتیکی تێکچووە. بۆ ئەوەی بابەتەکە خراپتر بێت لە بەیانی وانە دەستپێدەکات، واتا یەکەم شت لە بەیانی، قوتابیان بە مێگەل دێن بۆ گەڕان بە دوای ئەو کتێبانە. چۆن دەتوانیت لە کاتی خۆی ڕێکیان بخەیت؟ یەک ڕێگە دەبێت بە دەست پێکردن لە کۆتایی هێڵ لەگەڵ یەکەم جووت کتێب. ئەگەر دوو کتێبی یەکەم ڕیزبن کەواتە وازیان لێ بێنە وەک خۆیان. ئەگەر نا، بیانگۆڕە دواتر، سەیری دووەم و سێیەم کتێب بکە، پڕۆسەکە دووبارە بکەوە، و بەردەوام بە تاکو بە کۆتایی ھێڵ دەگەیت. لە هەندێک خاڵ، تۆ دێیتە پێشی ئەو کتێبەی کە دەبێت کۆتا بێت، و بەردەوام بیگۆڕینەوە لەگەڵ هەموو کتێبی دواتر، لە هێڵەکە بیجوڵێنەوە تا ئەو کاتەی دەگاتە کۆتایی کە ئەو شوێنەی کە هی ئەوە. پاشان، لە سەرەتاوە دەست پێ بکە و پرۆسەکە دووبارە بکەوە بۆ ئەوەی دووەم کتێب بهینە کتێبی کۆتا لە شوێنی گونجاوی خۆی، بەردەوام بە تا هەموو کتێبەکان پۆلێن کراون. ئەم نزیکبوونەوەیە پێی دەگوترێت ریزکردنی بڵق. ئاسانە بەڵام ھێواشە. تۆ ١٢٧٩ بەراوردکاری دەکەیت لە خولی یەکەمدا، دواتر ١٢٧٨ و بەم شێوەیە، زیادکردن بۆ ٨١٨٥٦٠ بەراوردکردن. ئەگەر هەر یەک چرکەیەک بخایەنێت پرۆسەکە نۆ ڕۆژ دەخایەنێت. ڕێگەی دووەم بە ڕیزکردنی تەنھا دوو کتێبی یەکەمە. دواتر، سێیەم کتێب بھێنە و بەراوردی بکە لەگەڵ شوێنی کتێبی دووەم. ئەگەر هی کتێبی دووەم بێت، بیانگۆڕەوە، پاشان بەراوردی بکە لەگەڵ کتێبی خاڵی یەکەمدا، و ئەگەر پێویست بوو دووبارە ئاڵوگۆڕ بکە. ئێستا تۆ سێ کتێبی یەکەمت ڕیزکردووە. بەردەوام بە لە زیادکردنی یەک کتێب لە هەر کاتێک بۆ هێڵی لاوەکی پۆلێنکراو، بەراوردکردن و گۆڕینەوەی کتێبە نوێیەکە لەگەڵ ئەوەی پێش خۆی تا ئەو کاتەی بە شێوەیەکی دروست دانرا لە نێوان ئەو کتێبانەی تا ئێستا پۆلێنکراون. ئەمە پێی دەوترێت ڕیزکردنی دانان. بە پێچەوانەی ڕیزکردنی بڵق، بە زۆری پێویستی بە بەراوردکردنی هەموو دوو کتێبێک نییە. بە تێکڕا، ئێمە پێشبینی دەکەین تەنها پێویستمان بۆ بەراوردکردنی هەر کتێبێک بۆ نیوەی ئەو کتێبانەی کە پێش ئەوە هاتوون. لەو حاڵەتەدا، کۆی ژمارەی بەراوردەکان ٤٠٩٢٨٠ دەبن، ٥ ڕۆژی پێدەچێت. ھێشتا بەراوردی زۆر دەکەیت. بیرۆکەیەکی باشتر. یەکەم، کتێبێک ھەڕەمیەکانە ھەڵبژێرە. پێی بلێ دابەشکاری و بەراوردی بکە بۆ هەموو کتێبێکی تر. پاشان، ھێڵەکە دابەش بکە بە دانانی هەموو کتێبەکان کە پێش بەشکردنەکەی لای چەپی دێت و ھەموو ئەوانەی دوای ئەو دێن ھی لای ڕاستن. تۆ ئێستا کاتت پاشەکەوت کرد بە بەراورد نەکردنی کتێبەکانی لای چەپ بۆ هەر یەکێک لە ڕاستدا دووبارە. ئێستا، تەنھا سەیری کتێبەکانی لای چەپ بکە، تۆ دەتوانیت دووبارە پەرتووکی بەشکردنی هەڕەمەکی هەڵبژێریت و ئەو کتێبانەی کە دێن جیای کەنەوە ئەوەی لە پێشی و لە دوای دا بێت. دەتوانیت بەردەوام بیت لە دروست کردنی بەشکردن لەم شێوەیە تا ئەو کاتەی کە کۆمەڵێک هێڵی لاوەکی بچوکت هەیە، هەر یەکێکیان بە خێرایی بەکارهێنانی ستراتیژیەکی تر، وەک ڕیزکردنی دانان. هەر دەورێکی دابەشکردن پێویستی بە نزیکەی ١٢٨٠ بەراوردکاری ھەیە. ئەگەر بەشەکانتان هاوسەنگ بن، دابەشکردنی کتێبەکان بۆ ١٢٨ هێڵی لاوەکی لە دە حەوت خول بخایەنێت، یان ٨٩٦٠ چرکە. پۆلێنکردنی ئەم ژێرهێڵانە زیاد دەکات هەر یەک لە ٢٢ چرکە. هەموو ئەمانە، ئەم شێوازە ناسراوە بە ڕیزکردنی خێرا دەتوانێت کتێبەکان پۆلێن بکات لە ژێر سێ کاتژمێر و نیودا. بەڵام تەلەیەک ھەیە. لەوانەیە بەش بەشکردنەکانت ناھاوسەنگ بێت، هیچ کات پاشەکەوت ناکات. خۆشبەختانە، ئەمە زۆر کەم ڕوودەدات. لەبەر ئەوەیە ڕیزکردنی خێرا یەکێکە لە زۆرترین ستراتیژی کارامە ئەمڕۆ لەلایەن بەرنامەکارانەوە بەکاردێت. بۆ شتی وەک پۆلێنکردنی کەلوپەل بەکاریدەھێنن لە فرۆشگایەکی ئۆنلاین بە نرخ، یان دروستکردنی لیستێک لە هەموو بەنزینخانەکان نزیک لە شوێنێکی دیاریکراو بە دووری ڕیزکراوە. لە حاڵەتەکەت، تۆ تەواو بووی لەڕیزکردنی خێرا لەگەڵ کات بۆ پاشەکەوت کردن. تەنها ڕۆژێکی تری بەرز لە کتێبخانەکە.
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.