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

Επιμέλεια: Chryssa Rapessi

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.

Είναι απλή, αλλά αργή.

Στον πρώτο γύρο, θα χρειαζόταν να πραγματοποιήσετε 1.279 συγκρίσεις,

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

then 1,278, and so on,

έπειτα 1.278 και ούτω καθεξής,

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.

Κάθε γύρος «τμηματοποίησης» απαιτεί περίπου 1.280 συγκρίσεις.

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.

ή 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.

Άλλη μια «άγρια» μέρα στη βιβλιοθήκη.