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

3,894,455 views ・ 2016-11-28

TED-Ed


Κάντε διπλό κλικ στους αγγλικούς υπότιτλους παρακάτω για να αναπαραγάγετε το βίντεο.

Επιμέλεια: Chryssa Rapessi
00:06
You work at the college library.
0
6911
2266
Δουλεύετε στη βιβλιοθήκη του πανεπιστημίου.
Βρίσκεστε στη μέση ενός ήσυχου απογεύματος
00:09
You're in the middle of a quiet afternoon
1
9177
2220
00:11
when suddenly a shipment of 1,280 different books arrives.
2
11397
6614
όταν ξαφνικά καταφτάνει ένα φορτίο 1.280 διαφορετικών βιβλίων.
Τα βιβλία έχουν παραταχθεί σε μια μεγάλη ευθεία γραμμή,
00:18
The books have been dropped of in one long straight line,
3
18011
3679
00:21
but they're all out of order,
4
21690
1598
αλλά είναι όλα εκτός σειράς
00:23
and the automatic sorting system is broken.
5
23288
3743
και το σύστημα αυτόματης ταξινόμησης είναι εκτός λειτουργίας.
Για κακή σας τύχη, αύριο αρχίζουν τα μαθήματα,
00:27
To make matters worse, classes start tomorrow,
6
27031
2636
00:29
which means that first thing in the morning,
7
29667
2338
πράγμα που σημαίνει ότι αύριο πρωί - πρωί,
θα εμφανιστούν ορδές φοιτητών προς αναζήτηση αυτών των βιβλίων.
00:32
students will show up in droves looking for these books.
8
32005
4552
00:36
How can you get them all sorted in time?
9
36557
2936
Πώς μπορείτε να τα ταξινομήσετε όλα εγκαίρως;
00:39
One way would be to start at one end of the line with the first pair of books.
10
39493
5286
Ένας τρόπος θα ήταν να ξεκινήσετε από τη μία άκρη της γραμμής,
με τα πρώτα δύο βιβλία.
00:44
If the first two books are in order, then leave them as they are.
11
44779
3847
Εάν τα δύο πρώτα βιβλία είναι στη σειρά, τότε τα αφήνετε ως έχουν.
00:48
Otherwise, swap them.
12
48626
2294
Αλλιώς, τα αντιμεταθέτετε.
00:50
Then, look at the second and third books,
13
50920
2296
Έπειτα, ελέγχετε το δεύτερο και το τρίτο βιβλίο,
00:53
repeat the process,
14
53216
1663
επαναλαμβάνετε τη διαδικασία
00:54
and continue until you reach the end of the line.
15
54879
3056
και συνεχίζετε έως ότου να φτάσετε στο τέλος της γραμμής.
00:57
At some point, you'll come across the book that should be last,
16
57935
3250
Κάποια στιγμή, θα βρείτε το βιβλίο που θα έπρεπε να είναι τελευταίο
01:01
and keep swapping it with every subsequent book,
17
61185
3525
και συνεχίζοντας να το αντιμεταθέτετε με όλα τα επόμενα βιβλία,
01:04
moving it down the line until it reaches the end where it belongs.
18
64710
4570
το μετακινείτε έως το τέλος της γραμμής, όπου είναι και η θέση του.
01:09
Then, start from the beginning and repeat the process
19
69280
2945
Τότε, ξεκινάτε από την αρχή και επαναλαμβάνετε τη διαδικασία,
01:12
to get the second to last book in its proper place,
20
72225
3285
για να βάλετε το προτελευταίο βιβλίο στη σωστή του θέση
01:15
and keep going until all books are sorted.
21
75510
3311
και συνεχίζετε μέχρι όλα τα βιβλία να είναι ταξινομημένα.
01:18
This approach is called Bubble Sort.
22
78821
3041
Αυτή η προσέγγιση ονομάζεται «Ταξινόμηση Φυσαλίδας».
01:21
It's simple but slow.
23
81862
2294
Είναι απλή, αλλά αργή.
Στον πρώτο γύρο, θα χρειαζόταν να πραγματοποιήσετε 1.279 συγκρίσεις,
01:24
You'd make 1,279 comparisons in the first round,
24
84156
5175
01:29
then 1,278, and so on,
25
89331
4292
έπειτα 1.278 και ούτω καθεξής,
01:33
adding up to 818,560 comparisons.
26
93623
4919
πραγματοποιώντας συνολικά 818.560 συγκρίσεις.
01:38
If each took just one second, the process would take over nine days.
27
98542
5731
Εάν η κάθε μία έπαιρνε ένα δευτερόλεπτο, όλο αυτό θα διαρκούσε εννέα ημέρες.
Μια δεύτερη στρατηγική θα ήταν να ξεκινούσατε ταξινομώντας
01:44
A second strategy would be to start by sorting just the first two books.
28
104273
4296
απλώς τα πρώτα δύο βιβλία.
01:48
Then, take the third book and compare it with the book in the second spot.
29
108569
5164
Έπειτα, συγκρίνετε το τρίτο βιβλίο με αυτό στη δεύτερη θέση.
01:53
If it belongs before the second book, swap them,
30
113733
3440
Εάν ανήκει πριν το δεύτερο βιβλίο, τα αντιμεταθέτετε,
και μετά το συγκρίνετε με το πρώτο βιβλίο,
01:57
then compare it with the book in the first spot,
31
117173
2468
01:59
and swap again if needed.
32
119641
2041
και τα αντιμεταθέτετε κι αυτά, εάν πρέπει.
02:01
Now you've sorted the first three books.
33
121682
2198
Τώρα έχετε ταξινομήσει τα πρώτα τρία βιβλία.
02:03
Keep adding one book at a time to the sorted sub-line,
34
123880
3852
Συνεχίζετε να προσθέτετε ένα βιβλίο τη φορά στα ήδη ταξινομημένα,
02:07
comparing and swapping the new book with the one before it
35
127732
4077
συγκρίνοντας και αντιμεταθέτοντας το νέο βιβλίο με το ακριβώς προηγούμενο,
02:11
until it's correctly placed among the books sorted so far.
36
131809
4195
μέχρι να είναι σωστά τοποθετημένο ανάμεσα στα έως τώρα ταξινομημένα βιβλία.
Αυτή ονομάζεται «Ταξινόμηση με Εισαγωγή».
02:16
This is called Insertion Sort.
37
136004
2209
Αντίθετα από την Ταξινόμηση Φυσαλίδας, συνήθως δεν χρειάζεται να συγκρίνουμε
02:18
Unlike Bubble Sort, it usually doesn't require comparing every pair of books.
38
138213
4731
όλα τα ζεύγη βιβλίων.
02:22
On average, we'd expect to only need to compare each book
39
142944
4010
Κατά μέσο όρο, θα αναμέναμε να χρειαζόταν να συγκρίνουμε κάθε βιβλίο
02:26
to half of the books that came before it.
40
146954
2460
με τα μισά όσων βρίσκονταν πριν από αυτό.
02:29
In that case, the total number of comparisons
41
149414
2709
Σε αυτήν την περίπτωση, ο συνολικός αριθμός συγκρίσεων
02:32
would be 409,280,
42
152123
3860
θα ανερχόταν στις 409.280,
02:35
taking almost five days.
43
155983
2152
διαρκώντας σχεδόν πέντε ημέρες.
Ακόμα πραγματοποιείτε υπερβολικά πολλές συγκρίσεις.
02:38
You're still doing way too many comparisons.
44
158135
2489
02:40
Here's a better idea.
45
160624
1891
Ορίστε μια καλύτερη ιδέα.
02:42
First, pick a random book.
46
162515
2370
Αρχικά, διαλέξτε ένα τυχαίο βιβλίο.
02:44
Call it the partition and compare it to every other book.
47
164885
4721
Ονομάστε το στοιχείο διαχωρισμού και συγκρίνετέ το με κάθε άλλο βιβλίο.
02:49
Then, divide the line
48
169606
1909
Στη συνέχεια, χωρίστε τη γραμμή
02:51
by placing all the books that come before the partition on its left
49
171515
4151
τοποθετώντας όλα τα βιβλία που είναι πριν από αυτό, στα αριστερά του
02:55
and all the ones that come after it on its right.
50
175666
3159
και όλα εκείνα που είναι μετά, στα δεξιά του.
02:58
You've just saved loads of time
51
178825
1590
Μόλις γλιτώσατε πολύ χρόνο,
03:00
by not having to compare any of the books on the left
52
180415
3430
καθώς δεν θα χρειαστεί ποτέ να συγκρίνετε κανένα βιβλίο στα αριστερά
03:03
to any of the ones on the right ever again.
53
183845
3400
με κανένα από εκείνα που είναι στα δεξιά.
Τώρα, κοιτώντας μόνο τα βιβλία στα αριστερά,
03:07
Now, looking only at the books on the left,
54
187245
2420
03:09
you can again pick a random partition book
55
189665
2877
μπορείτε να διαλέξετε εκ νέου ένα τυχαίο βιβλίο διαχωρισμού
03:12
and separate those books that come before it from those that come after it.
56
192542
4724
και να διαχωρίσετε τα βιβλία που είναι πριν από αυτό, από εκείνα που είναι μετά.
03:17
You can keep creating sub-partitions like this
57
197266
2470
Μπορείτε να συνεχίσετε να φτιάχνετε επιμέρους τμήματα
03:19
until you have a bunch of small sub-lines,
58
199736
2648
έως ότου να έχετε αρκετές μικρές υποομάδες βιβλίων,
03:22
each of which you'd sort quickly using another strategy, like Insertion Sort.
59
202384
5380
που θα μπορούσατε να ταξινομήσετε γρήγορα χρησιμοποιώντας κάποια άλλη μέθοδο,
όπως Ταξινόμηση με Εισαγωγή.
03:27
Each round of partitioning requires about 1,280 comparisons.
60
207764
5162
Κάθε γύρος «τμηματοποίησης» απαιτεί περίπου 1.280 συγκρίσεις.
03:32
If your partitions are pretty balanced,
61
212926
2540
Εάν τα τμήματά σας είναι αρκετά ισορροπημένα,
03:35
dividing the books into 128 sub-lines of ten would take about seven rounds,
62
215466
5790
το να χωρίσετε τα βιβλία σε 128 υποομάδες των δέκα θα χρειαζόταν περίπου επτά γύρους
03:41
or 8,960 seconds.
63
221256
2691
ή 8.960 δευτερόλεπτα.
03:43
Sorting these sub-lines would add about 22 seconds each.
64
223947
4789
Το να ταξινομήσετε αυτές τις υποομάδες θα προσέθετε 22 δευτερόλεπτα για κάθε μία.
03:48
All in all, this method known as QuickSort
65
228736
3081
Τελικά, αυτή η μέθοδος, γνωστή ως «Ταχεία Ταξινόμηση»
03:51
could sort the books in under three and a half hours.
66
231817
3066
θα μπορούσε να ταξινομήσει τα βιβλία σε λιγότερο από τρεισήμισι ώρες.
03:54
But there's a catch.
67
234883
1114
Αλλά υπάρχει παγίδα.
03:55
Your partitions could end up lopsided, saving no time at all.
68
235997
3578
Τα τμήματα μπορεί να καταλήξουν ασύμμετρα,
και να φάνε πολύ χρόνο.
03:59
Luckily, this rarely happens.
69
239575
1902
Ευτυχώς, αυτό σπανίως συμβαίνει.
04:01
That's why QuickSort is one of the most efficient strategies
70
241477
3433
Για αυτό η Ταχεία Ταξινόμηση είναι από τις πιο αποδοτικές μεθόδους
04:04
used by programmers today.
71
244910
2006
που χρησιμοποιούν οι προγραμματιστές σήμερα.
04:06
They use it for things like sorting items in an online store by price,
72
246916
3931
Τη χρησιμοποιούν για ταξινόμηση προϊόντων ηλεκτρονικών μαγαζιών, βάσει τιμής
04:10
or creating a list of all the gas stations close to a given location
73
250847
4011
ή για να δημιουργούν λίστες με όλα τα βενζινάδικα κοντά σε μια τοποθεσία
04:14
sorted by distance.
74
254858
1521
ταξινομημένα με βάση την απόσταση.
04:16
In your case, you're done quick sorting with time to spare.
75
256379
4028
Εσείς, κάνατε μια γρήγορη ταξινόμηση και σας περίσσεψε και χρόνος.
04:20
Just another high-stakes day in the library.
76
260407
2261
Άλλη μια «άγρια» μέρα στη βιβλιοθήκη.
Σχετικά με αυτόν τον ιστότοπο

Αυτός ο ιστότοπος θα σας παρουσιάσει βίντεο στο YouTube που είναι χρήσιμα για την εκμάθηση της αγγλικής γλώσσας. Θα δείτε μαθήματα αγγλικών που διδάσκουν κορυφαίοι καθηγητές από όλο τον κόσμο. Κάντε διπλό κλικ στους αγγλικούς υπότιτλους που εμφανίζονται σε κάθε σελίδα βίντεο για να αναπαράγετε το βίντεο από εκεί. Οι υπότιτλοι μετακινούνται συγχρονισμένα με την αναπαραγωγή του βίντεο. Εάν έχετε οποιαδήποτε σχόλια ή αιτήματα, παρακαλούμε επικοινωνήστε μαζί μας χρησιμοποιώντας αυτή τη φόρμα επικοινωνίας.

https://forms.gle/WvT1wiN1qDtmnspy7