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

מה הדרך המהירה ביותר לסדר את מדף הספרים שלכם לפי הא"ב? – צ'אנד ג'ון

תרגום: Ido Dekkers עריכה: Sigal Tifferet

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.

כשפתאום מגיע משלוח של 1,280 ספרים שונים.

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.

עד שתגיעו ל 818,560 השוואות.

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,

יהיה 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.

כל סיבוב של חלוקה דורש בערך 1280 השוואות.

If your partitions are pretty balanced,

אם המחיצות שלכם די מאוזנות,

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

חלוקת הספרים ל 129 תת-שורות של עשר תקח בערך שבעה סבבים,

or 8,960 seconds.

או 8,960 שניות.

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.

זהו עוד יום של חיים על הקצה בספריה.