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

المترجم: Nada Shokry المدقّق: Fatima Zahra El Hafa

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.

إحدى الطرق هي البدء بناحية واحدة من الخط بالزوج الأول من الكتب.

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,

ستقوم بإجراء 1279 مقارنة في الجولة الأولى

then 1,278, and so on,

ثم 1278، وهكذا،

adding up to 818,560 comparisons.

ليبلغ المجموع 818560 مقارنة.

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,

سيكون 409280،

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.

كل جولة من التقسيم تتطلب حوالي 1280 مقارنة.

If your partitions are pretty balanced,

إذا كانت الأقسام متوازنة نوعًا ما،

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

فإن تقسيم الكتب إلى 128 خطًا فرعيًا من عشرة سوف يستغرق حوالي سبع جولات،

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.

يمكنها ترتيب الكتب في أقل من ثلاث ساعات ونصف.

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.

مجرد يوم مشوق آخر في المكتبة.