1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH: Γεια σου, είμαι ο Mark
Grozen-Smith, και αυτό είναι Quicksort.

3
00:00:10,390 --> 00:00:13,520
Ακριβώς όπως το είδος εισαγωγής και φούσκα
ταξινόμησης, Quicksort είναι ένας αλγόριθμος για

4
00:00:13,520 --> 00:00:15,720
διαλογής μιας λίστας ή μία συστοιχία των πραγμάτων.

5
00:00:15,720 --> 00:00:19,080
Για λόγους απλότητας, ας υποθέσουμε ότι οι
τα πράγματα είναι ακέραιοι αριθμοί, αλλά

6
00:00:19,080 --> 00:00:22,060
Γνωρίζουμε ότι Quicksort λειτουργεί για
κάτι περισσότερο από αριθμούς.

7
00:00:22,060 --> 00:00:24,720
Γρήγορης εκκίνησης είναι λίγο πιο περίπλοκη
από την εισαγωγή ή φούσκα, αλλά είναι

8
00:00:24,720 --> 00:00:27,560
Επίσης, πολύ πιο αποδοτική
στις περισσότερες περιπτώσεις.

9
00:00:27,560 --> 00:00:28,150
Περιμένετε ένα δευτερόλεπτο.

10
00:00:28,150 --> 00:00:30,760
Μήπως είπε "οι περισσότεροι
περιπτώσεις, "όχι" όλα ";

11
00:00:30,760 --> 00:00:31,710
Είναι ενδιαφέρον, όχι.

12
00:00:31,710 --> 00:00:33,560
Όχι όλες τις περιπτώσεις είναι η ίδια.

13
00:00:33,560 --> 00:00:36,650
Μην ανησυχείτε για αυτή τη λεπτομέρεια, αν
Δεν έχω δει μεγάλη O συμβολισμός ακόμα, αλλά

14
00:00:36,650 --> 00:00:39,730
Quicksort είναι O (n τετράγωνο) αλγόριθμο
στη χειρότερη περίπτωση, όπως ακριβώς

15
00:00:39,730 --> 00:00:41,430
εισαγωγή ή bubble sort.

16
00:00:41,430 --> 00:00:44,950
Ωστόσο, ενεργεί συνήθως πολύ πιο
σαν ένα παλιό αναλογικό m αλγόριθμο.

17
00:00:44,950 --> 00:00:45,750
Γιατί;

18
00:00:45,750 --> 00:00:46,810
Θα επιστρέψουμε σε αυτό αργότερα.

19
00:00:46,810 --> 00:00:49,610
Αλλά για τώρα, ας μάθουμε
πώς λειτουργεί Quicksort.

20
00:00:49,610 --> 00:00:53,080
>> Έτσι, ας δούμε τις Quicksorting αυτό
array ακεραίων από το μικρότερο

21
00:00:53,080 --> 00:00:54,260
στην μεγαλύτερη.

22
00:00:54,260 --> 00:01:00,110
Εδώ έχουμε τους ακέραιους αριθμούς 6,
5, 1, 3, 8, 4, 7, 9, και 2.

23
00:01:00,110 --> 00:01:03,480
Πρώτον, έχουμε πάρει το τελευταίο στοιχείο της
αυτή η διάταξη - στην προκειμένη περίπτωση, δύο -

24
00:01:03,480 --> 00:01:06,870
και καλέστε ότι το «άξονα». Στη συνέχεια, έχουμε
αρχίζουν να δούμε δύο πράγματα -

25
00:01:06,870 --> 00:01:10,220
ένα, το χαμηλότερο δείκτη, η οποία θα αναφερθώ
ως διαμένουν στα δεξιά του

26
00:01:10,220 --> 00:01:13,970
το τοίχωμα, και, δύο, η αριστερότερη
στοιχείο, το οποίο θα καλέσω το "ρεύμα

27
00:01:13,970 --> 00:01:17,260
στοιχείο. «Αυτό που πάμε να κάνουμε είναι
φαίνονται όλα τα άλλα στοιχεία, άλλες

28
00:01:17,260 --> 00:01:20,930
από τον άξονα, και να θέσει όλα τα στοιχεία
μικρότερο από το στροφέα προς την

29
00:01:20,930 --> 00:01:24,140
αριστερά του τείχους και όλους εκείνους
μεγαλύτερο από το στροφέα προς την

30
00:01:24,140 --> 00:01:25,570
δεξιά του τοίχου.

31
00:01:25,570 --> 00:01:29,560
Στη συνέχεια, τέλος, θα πέσει το pivot
ακριβώς πάνω από το τείχος για να το θέσω μεταξύ

32
00:01:29,560 --> 00:01:32,970
όλοι οι αριθμοί μικρότεροι από ό, τι
και όλοι οι αριθμοί μεγαλύτερο.

33
00:01:32,970 --> 00:01:34,460
>> Οπότε ας το κάνουμε αυτό.

34
00:01:34,460 --> 00:01:38,540
Σήκωσε το 2, βάλτε τον τοίχο κατά τη
αρχίζει, και καλέστε το 6 το «ρεύμα

35
00:01:38,540 --> 00:01:41,590
στοιχείου. "Έτσι θέλουμε να δούμε
τρέχον στοιχείο μας, το 6.

36
00:01:41,590 --> 00:01:44,200
Και δεδομένου ότι είναι μεγαλύτερο από ό, τι η
2, το αφήνουμε εκεί για να το

37
00:01:44,200 --> 00:01:45,610
δεξιά του τοίχου.

38
00:01:45,610 --> 00:01:48,980
Στη συνέχεια, θα προχωρήσουμε να εξετάσουμε το 5 όπως μας
τρέχον στοιχείο και να δούμε ότι αυτή η

39
00:01:48,980 --> 00:01:51,840
είναι, πάλι, μεγαλύτερο από το στροφέα, έτσι
αφήστε το όταν είναι σχετικά με το δικαίωμα

40
00:01:51,840 --> 00:01:53,190
πλευρά του τοίχου.

41
00:01:53,190 --> 00:01:53,880
Προχωράμε.

42
00:01:53,880 --> 00:01:56,750
Τρέχον στοιχείο μας είναι
τώρα 1, και - ω.

43
00:01:56,750 --> 00:01:58,030
Αυτό είναι διαφορετικό τώρα.

44
00:01:58,030 --> 00:02:00,890
Το τρέχον στοιχείο είναι σήμερα μικρότερη από ό, τι
ο άξονας, έτσι θέλουμε να το θέσω

45
00:02:00,890 --> 00:02:02,570
στα αριστερά του τοίχου.

46
00:02:02,570 --> 00:02:06,555
Για να το κάνετε αυτό, ας αλλάξουν το
τρέχουσα στοιχείου με το χαμηλότερο δείκτη

47
00:02:06,555 --> 00:02:07,970
να κάθεται στα δεξιά του τοίχου.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
Τώρα, προχωράμε στον τοίχο μέχρι ένα δείκτη
έτσι ώστε το 1 είναι στα αριστερά

50
00:02:17,570 --> 00:02:19,750
πλευρά του τοιχώματος τώρα.

51
00:02:19,750 --> 00:02:20,310
>> Περιμένετε.

52
00:02:20,310 --> 00:02:23,450
Απλά συγχέονται τα στοιχεία σχετικά με την
δεξιά πλευρά του τοίχου, έτσι δεν είναι;

53
00:02:23,450 --> 00:02:23,890
Μην ανησυχείτε.

54
00:02:23,890 --> 00:02:24,930
Αυτό είναι μια χαρά.

55
00:02:24,930 --> 00:02:27,570
Το μόνο πράγμα που μας νοιάζει προς το παρόν
είναι ότι όλα αυτά τα στοιχεία στο

56
00:02:27,570 --> 00:02:29,570
δεξιά του τοίχου είναι μεγαλύτερο
από τον άξονα περιστροφής.

57
00:02:29,570 --> 00:02:31,760
Δεν πραγματική σειρά θεωρείται ακόμα.

58
00:02:31,760 --> 00:02:33,200
>> Τώρα, πίσω στο διαλογή.

59
00:02:33,200 --> 00:02:35,840
Έτσι συνεχίζουμε κοιτάζοντας
το υπόλοιπο των στοιχείων.

60
00:02:35,840 --> 00:02:39,075
Και σε αυτή την περίπτωση, βλέπουμε ότι υπάρχουν
δεν υπάρχουν άλλα στοιχεία, λιγότερο από το

61
00:02:39,075 --> 00:02:42,100
περιστροφής, έτσι μπορούμε να τα αφήσει όλα για
η δεξιά πλευρά του τοίχου.

62
00:02:42,100 --> 00:02:45,980
Τέλος, έχουμε την ευκαιρία να το τρέχον στοιχείο
και να δούμε ότι είναι ο άξονας.

63
00:02:45,980 --> 00:02:48,830
Τώρα, αυτό σημαίνει ότι έχουμε δύο
τμήματα της συστοιχίας, το πρώτο ον

64
00:02:48,830 --> 00:02:51,820
μικρή επί του στροφέα και στην αριστερή πλευρά
του τείχους, και ενώ το δεύτερο

65
00:02:51,820 --> 00:02:54,500
μεγαλύτερο από το στροφέα προς την
δεξιά πλευρά του τοίχου.

66
00:02:54,500 --> 00:02:57,040
Θέλουμε να βάλουμε το στοιχείο περιστροφής μεταξύ
τα δύο, και τότε θα ξέρουμε

67
00:02:57,040 --> 00:03:01,000
ότι ο στροφέας είναι το δικαίωμα του
τελική ταξινομημένη θέση.

68
00:03:01,000 --> 00:03:04,980
Έτσι, αλλάζουμε το πρώτο στοιχείο για το
δεξιά πλευρά του τοίχου με τον άξονα περιστροφής,

69
00:03:04,980 --> 00:03:06,410
και ξέρουμε ότι ο άξονας περιστροφής του
στη δεξιά θέση του.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> Στη συνέχεια, επαναλάβετε αυτή τη διαδικασία για την
υποπαρατάξεων αριστερά και δεξιά του στροφέα.

72
00:03:15,650 --> 00:03:18,700
Δεδομένου ότι η τελευταία υπο-συστοιχίας είναι μόνο μία
στοιχείο καιρό, γνωρίζουμε ότι είναι ήδη

73
00:03:18,700 --> 00:03:22,480
ταξινομημένη, γιατί πώς μπορείς να είσαι έξω από
διατάξει αν είστε μόνο ένα στοιχείο;

74
00:03:22,480 --> 00:03:28,860
Για τη δεξιά πλευρά του υπο-συστοιχίας, εμείς
δείτε ότι ο στροφέας είναι 5, και ο τοίχος

75
00:03:28,860 --> 00:03:32,250
είναι ακριβώς αριστερά από το 6.

76
00:03:32,250 --> 00:03:34,970
Και το τρέχον στοιχείο, επίσης,
ξεκινά ως το 6.

77
00:03:34,970 --> 00:03:36,200
Έτσι 6 είναι μεγαλύτερο από 5.

78
00:03:36,200 --> 00:03:38,590
Το αφήνουμε όπου είναι σχετικά με την
δεξιά πλευρά του τοίχου.

79
00:03:38,590 --> 00:03:41,060
Τώρα, κινείται, 3 είναι μικρότερη από 5.

80
00:03:41,060 --> 00:03:44,160
Γι 'αυτό και το διακόπτη με το πρώτο στοιχείο
ακριβώς δεξιά από τον τοίχο.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
Τώρα, πήγα τον τοίχο μέχρι ένα.

83
00:03:50,750 --> 00:03:53,010
Τώρα, κινείται προς την 8.

84
00:03:53,010 --> 00:03:56,480
8 είναι μεγαλύτερο από 5,
και γι 'αυτό αφήστε το.

85
00:03:56,480 --> 00:03:58,720
Το 4 είναι μικρότερη από 5, έτσι ώστε να το ενεργοποιήσετε.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
Και.

88
00:04:03,570 --> 00:04:04,820
Και.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> Κάθε φορά επαναλαμβάνουμε τη διαδικασία για την
αριστερή και δεξιά πλευρά της συστοιχίας. εμείς

91
00:04:13,670 --> 00:04:17,010
επιλέξετε έναν άξονα και να κάνουμε τις συγκρίσεις
και να δημιουργήσει ένα άλλο επίπεδο αριστερά και

92
00:04:17,010 --> 00:04:18,240
δεξιά υποπαρατάξεων.

93
00:04:18,240 --> 00:04:21,500
Αυτή η αναδρομική κλήση θα συνεχιστεί έως ότου
φτάνουμε στο τέλος, όταν έχουμε

94
00:04:21,500 --> 00:04:25,290
διαιρείται το συνολικό πίνακα σε
μόνο υποπαρατάξεων μήκους 1.

95
00:04:25,290 --> 00:04:28,060
Από εκεί, γνωρίζουμε ότι η σειρά είναι ταξινομημένο
διότι κάθε στοιχείο έχει, σε

96
00:04:28,060 --> 00:04:29,330
κάποιο σημείο, ήταν ένα άξονα.

97
00:04:29,330 --> 00:04:32,720
Με άλλα λόγια, για κάθε στοιχείο, όλα
οι αριθμοί προς τα αριστερά είναι μικρότερο

98
00:04:32,720 --> 00:04:36,420
αξίες και όλοι οι αριθμοί στην
το δικαίωμα να έχουν μεγαλύτερες τιμές.

99
00:04:36,420 --> 00:04:38,980
>> Αυτή η μέθοδος λειτουργεί πολύ καλά, αν η
αξία του στροφέα που επιλέγεται είναι

100
00:04:38,980 --> 00:04:41,930
περίπου στη μέση
εύρος των τιμών καταλόγου.

101
00:04:41,930 --> 00:04:45,630
Αυτό θα σήμαινε ότι, μετά κινούμαστε
στοιχεία γύρω, υπάρχουν περίπου όσες

102
00:04:45,630 --> 00:04:48,390
στοιχεία στα αριστερά του στροφέα
καθώς υπάρχουν προς τα δεξιά.

103
00:04:48,390 --> 00:04:52,380
Και το διαίρει και βασίλευε φύση του
Αλγόριθμος Quicksort τότε λαμβάνεται

104
00:04:52,380 --> 00:04:53,850
πλήρη αξιοποίηση του.

105
00:04:53,850 --> 00:04:57,500
Αυτό δημιουργεί ένα runtime του O (n log n,)
το n, επειδή έχουμε να κάνουμε n μείον 1

106
00:04:57,500 --> 00:05:01,640
συγκρίσεις σε κάθε γενιά και καταγραφής
n γιατί θα πρέπει να μοιράσουμε τη λίστα

107
00:05:01,640 --> 00:05:03,210
log n φορές.

108
00:05:03,210 --> 00:05:06,160
Ωστόσο, στις χειρότερες περιπτώσεις, αυτό
αλγόριθμος μπορεί πραγματικά να είναι O (n

109
00:05:06,160 --> 00:05:09,850
τετράγωνο.) Ας υποθέσουμε ότι σε κάθε γενιά,
ο άξονας ακριβώς έτσι συμβαίνει να είναι η

110
00:05:09,850 --> 00:05:12,520
μικρότερο ή το μεγαλύτερο από το
αριθμοί είμαστε διαλογής.

111
00:05:12,520 --> 00:05:15,870
Αυτό θα σήμαινε το σπάσιμο κάτω από τον κατάλογο
n φορές και λήψης n μείον 1

112
00:05:15,870 --> 00:05:17,690
συγκρίσεις κάθε φορά.

113
00:05:17,690 --> 00:05:20,490
Έτσι, o κ τετράγωνο.

114
00:05:20,490 --> 00:05:22,000
>> Πώς μπορεί να βελτιωθεί η μέθοδος;

115
00:05:22,000 --> 00:05:25,100
Ένας καλός τρόπος για να βελτιωθεί η μέθοδος είναι
να μειώσει την πιθανότητα ότι

116
00:05:25,100 --> 00:05:28,150
ο χρόνος εκτέλεσης είναι ποτέ πραγματικά
o κ τετράγωνο.

117
00:05:28,150 --> 00:05:31,860
Θυμηθείτε αυτό το χειρότερο, το χειρότερο σενάριο
μπορεί να συμβεί μόνο όταν η

118
00:05:31,860 --> 00:05:35,320
pivot επιλεγεί είναι πάντα η υψηλότερη
ή χαμηλότερη τιμή στη συστοιχία.

119
00:05:35,320 --> 00:05:38,630
Για να εξασφαλιστεί αυτό είναι λιγότερο πιθανό να συμβεί,
μπορούμε να βρούμε τον άξονα του

120
00:05:38,630 --> 00:05:42,610
επιλέγοντας πολλαπλά στοιχεία και
λαμβάνοντας τη μέση τιμή.

121
00:05:42,610 --> 00:05:44,650
>> Το όνομά μου είναι Mark Grozen-Smith,
και αυτό είναι CS50.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> Για λόγους απλότητας, ας υποθέσουμε ότι οι
τα πράγματα είναι ακέραιοι αριθμοί, αλλά

124
00:05:50,930 --> 00:05:51,970
Γνωρίζουμε ότι Quicksert -

125
00:05:51,970 --> 00:05:53,160
Quicksert;

126
00:05:53,160 --> 00:05:55,200
Λυπάμαι.

127
00:05:55,200 --> 00:06:02,000
>> Εδώ έχουμε τους ακέραιους
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> ΟΜΙΛΗΤΗΣ 1: Αλήθεια;

129
00:06:03,200 --> 00:06:04,850
>> ΟΜΙΛΗΤΗΣ 2: Μην σταματάς εκεί.

130
00:06:04,850 --> 00:06:06,100
>> ΟΜΙΛΗΤΗΣ 1: Αλήθεια;

131
00:06:06,100 --> 00:06:08,491