1
00:00:00,000 --> 00:00:03,360
>> [Παίζει μουσική]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
DOUG LLOYD: Εντάξει, έτσι
bubble sort είναι ένας αλγόριθμος

4
00:00:06,730 --> 00:00:08,730
που μπορείτε να χρησιμοποιήσετε για να ταξινομήσετε ένα σύνολο στοιχείων.

5
00:00:08,730 --> 00:00:10,850
Ας ρίξουμε μια ματιά στο πώς λειτουργεί.

6
00:00:10,850 --> 00:00:13,240
>> Έτσι, η βασική ιδέα πίσω
bubble sort είναι αυτό.

7
00:00:13,240 --> 00:00:17,340
Εμείς γενικά θέλουν να κινηθεί υψηλότερα
αποτιμώνται τα στοιχεία γενικά προς τα δεξιά,

8
00:00:17,340 --> 00:00:20,340
και χαμηλής εκτίμησης γενικά στοιχεία
προς τα αριστερά, όπως θα περιμέναμε.

9
00:00:20,340 --> 00:00:23,256
Θέλουμε τα κάτω τα πράγματα να είναι σε
η αρχή, και τα υψηλότερα πράγματα

10
00:00:23,256 --> 00:00:24,970
να είναι στο τέλος.

11
00:00:24,970 --> 00:00:26,130
>> Πώς μπορούμε να το κάνουμε αυτό;

12
00:00:26,130 --> 00:00:28,040
Λοιπόν στον κώδικα ψευδοκώδικα,
θα μπορούσαμε να πούμε, ας

13
00:00:28,040 --> 00:00:30,320
ορίσετε έναν μετρητή swap για μια μη μηδενική τιμή.

14
00:00:30,320 --> 00:00:32,570
Θα δούμε γιατί το κάνουμε αυτό σε μια δεύτερη.

15
00:00:32,570 --> 00:00:36,090
Και τότε θα επαναλάβω το εξής
διαδικασία έως ότου ο μετρητής swap είναι 0,

16
00:00:36,090 --> 00:00:39,910
ή έως ότου δεν κάνουμε ανταλλαγές σε όλα.

17
00:00:39,910 --> 00:00:43,170
>> Μηδενίστε το μετρητή του swap σε
0 αν δεν είναι ήδη 0.

18
00:00:43,170 --> 00:00:46,420
Στη συνέχεια, εξετάζει κάθε
γειτονικό ζεύγος των στοιχείων.

19
00:00:46,420 --> 00:00:49,550
Αν αυτά τα δύο στοιχεία
όχι με σκοπό, να ανταλλάξουν,

20
00:00:49,550 --> 00:00:51,620
και προσθέστε 1 στον πάγκο swap.

21
00:00:51,620 --> 00:00:53,870
Εάν σκέφτεστε για την
αυτό, πριν να το φανταστείτε,

22
00:00:53,870 --> 00:00:57,471
παρατηρήσετε ότι αυτό θα κινηθεί χαμηλότερα
αποτιμώνται στοιχεία προς τα αριστερά

23
00:00:57,471 --> 00:01:00,720
και υψηλότερες αποτιμώνται στοιχεία προς τα δεξιά,
αποτελεσματικά κάνει ό, τι θέλουμε να κάνουμε,

24
00:01:00,720 --> 00:01:03,940
η οποία είναι να μετακινήσετε αυτές τις ομάδες
των στοιχείων με τον τρόπο αυτό.

25
00:01:03,940 --> 00:01:07,035
Ας απεικονίσει το πώς αυτό
μπορεί να μοιάζει με τη χρήση συστοιχίας μας

26
00:01:07,035 --> 00:01:10,504
ότι χρησιμοποιείται για τη δοκιμή
από αυτούς τους αλγορίθμους.

27
00:01:10,504 --> 00:01:13,420
Έχουμε μια σειρά αδιαχώριστα και πάλι εδώ,
υποδεικνύεται από όλα τα στοιχεία

28
00:01:13,420 --> 00:01:14,840
είναι σε κόκκινο.

29
00:01:14,840 --> 00:01:17,970
Και εγώ που σε αντίθεση ανταλλαγής μου
σε μια μη μηδενική τιμή.

30
00:01:17,970 --> 00:01:20,610
Έχω επέλεξε αυθαίρετα
αρνητικό 1-- δεν είναι 0.

31
00:01:20,610 --> 00:01:23,840
Θέλουμε να επαναλάβετε αυτή τη διαδικασία
έως ότου ο μετρητής ανταλλαγής είναι 0.

32
00:01:23,840 --> 00:01:26,540
Αυτός είναι ο λόγος που έθεσα ανταλλαγής μου
σε αντίθεση με κάποια μη μηδενική τιμή,

33
00:01:26,540 --> 00:01:29,400
διότι διαφορετικά η
μετρητής ανταλλαγής θα είναι 0.

34
00:01:29,400 --> 00:01:31,610
Εμείς δεν θα είναι καν αρχίσει η
διαδικασία του αλγορίθμου.

35
00:01:31,610 --> 00:01:33,610
Έτσι και πάλι, τα βήματα are--
μηδενίσετε το μετρητή ανταλλαγής

36
00:01:33,610 --> 00:01:37,900
0, στη συνέχεια να εξετάσουμε σε κάθε παρακείμενο
ζευγάρι, και αν είναι εκτός λειτουργίας,

37
00:01:37,900 --> 00:01:40,514
ανταλλαγής τους, και προσθέστε 1
στον πάγκο swap.

38
00:01:40,514 --> 00:01:41,680
Οπότε ας ξεκινήσουμε αυτή τη διαδικασία.

39
00:01:41,680 --> 00:01:44,430
Έτσι, το πρώτο πράγμα που κάνουμε είναι
θέσαμε το μετρητή του swap σε 0,

40
00:01:44,430 --> 00:01:46,660
και στη συνέχεια θα αρχίσει να ψάχνει
σε κάθε γειτονικό ζεύγος.

41
00:01:46,660 --> 00:01:49,140
>> Γι 'αυτό πρώτα να αρχίσει να ψάχνει σε 5 και 2.

42
00:01:49,140 --> 00:01:52,410
Βλέπουμε ότι είναι έξω από
παραγγείλετε και έτσι μπορούμε να τα ανταλλάξουν.

43
00:01:52,410 --> 00:01:53,830
Και προσθέτουμε 1 στο μετρητή swap.

44
00:01:53,830 --> 00:01:57,860
Έτσι τώρα πάγκο ανταλλαγής μας είναι 1,
και 2 και 5 έχουν αλλάξει.

45
00:01:57,860 --> 00:01:59,370
Τώρα επαναλάβετε τη διαδικασία.

46
00:01:59,370 --> 00:02:03,540
>> Κοιτάμε το επόμενο γειτονικό ζεύγος,
5 και 1-- είναι επίσης εκτός λειτουργίας,

47
00:02:03,540 --> 00:02:06,960
έτσι μπορούμε να τα ανταλλάξουν και να προσθέσετε
1 στον πάγκο swap.

48
00:02:06,960 --> 00:02:08,900
Στη συνέχεια, εξετάζουμε 5 και 3.

49
00:02:08,900 --> 00:02:13,830
Είναι εκτός λειτουργίας, έτσι ώστε να ανταλλάξετε
τους και προσθέτουμε 1 στο μετρητή swap.

50
00:02:13,830 --> 00:02:15,550
Στη συνέχεια, εξετάζουμε 5 και 6.

51
00:02:15,550 --> 00:02:18,630
Είναι σε σειρά, έτσι δεν το κάνουμε πραγματικότητα
Πρέπει να ανταλλάξουν τίποτα αυτή τη φορά.

52
00:02:18,630 --> 00:02:20,250
Στη συνέχεια, εξετάζουμε 6 και 4.

53
00:02:20,250 --> 00:02:24,920
Είναι, επίσης, εκτός λειτουργίας, έτσι ώστε να ανταλλάξετε
τους και προσθέτουμε 1 στο μετρητή swap.

54
00:02:24,920 --> 00:02:26,230
>> Τώρα παρατηρήσετε τι συνέβη.

55
00:02:26,230 --> 00:02:29,514
Έχουμε μετακινηθεί 6 σε όλη τη διαδρομή μέχρι το τέλος.

56
00:02:29,514 --> 00:02:32,180
Έτσι, στην ταξινόμηση με επιλογή, αν έχετε
φαίνεται ότι το βίντεο, αυτό που κάναμε ήταν

57
00:02:32,180 --> 00:02:35,290
καταλήξαμε κινείται η
μικρότερα στοιχεία για την οικοδόμηση

58
00:02:35,290 --> 00:02:39,640
η ταξινομημένο πίνακα ουσιαστικά από
αριστερά προς τα δεξιά, το μικρότερο στο μεγαλύτερο.

59
00:02:39,640 --> 00:02:43,200
Στην περίπτωση του bubble sort, αν είμαστε
μετά από αυτό το συγκεκριμένο αλγόριθμο,

60
00:02:43,200 --> 00:02:46,720
είμαστε πραγματικά πρόκειται να είναι η αξιοποίηση
η ταξινομημένο πίνακα από δεξιά

61
00:02:46,720 --> 00:02:49,100
προς τα αριστερά, μεγαλύτερο προς το μικρότερο.

62
00:02:49,100 --> 00:02:53,840
Έχουμε αποτελεσματικά διοχετεύεται 6, το
Η μεγαλύτερη αξία, σε όλη τη διαδρομή μέχρι το τέλος.

63
00:02:53,840 --> 00:02:56,165
>> Και έτσι τώρα μπορούμε να δηλώνουμε
ότι είναι ταξινομημένο,

64
00:02:56,165 --> 00:02:59,130
και στο μέλλον iterations--
που διέρχεται από τη συστοιχία again--

65
00:02:59,130 --> 00:03:01,280
δεν έχουμε να εξετάσουμε 6 πια.

66
00:03:01,280 --> 00:03:03,850
Δεν έχουμε παρά να εξετάσουμε
τα αδιαχώριστα στοιχεία

67
00:03:03,850 --> 00:03:06,299
όταν ψάχνουμε σε γειτονικά ζεύγη.

68
00:03:06,299 --> 00:03:08,340
Έτσι έχουμε τελειώσει ένα
περνούν μέσα από bubble sort.

69
00:03:08,340 --> 00:03:11,941
Έτσι, τώρα πάμε πίσω στο θέμα,
επαναλάβετε μέχρι ο μετρητής ανταλλαγής είναι 0.

70
00:03:11,941 --> 00:03:13,690
Λοιπόν ο μετρητής ανταλλαγής
είναι 4, οπότε θα πάμε

71
00:03:13,690 --> 00:03:15,410
να το επαναλαμβάνουμε και πάλι αυτή τη διαδικασία.

72
00:03:15,410 --> 00:03:19,180
>> Εμείς πάμε για να μηδενίσετε το μετρητή ανταλλαγής
0, και να εξετάσουμε σε κάθε γειτονικό ζεύγος.

73
00:03:19,180 --> 00:03:21,890
Ξεκινάμε λοιπόν με 2 και 1-- ότι είναι
εκτός λειτουργίας, έτσι μπορούμε να τα ανταλλάξουν

74
00:03:21,890 --> 00:03:23,620
και προσθέτουμε 1 στο μετρητή swap.

75
00:03:23,620 --> 00:03:25,490
2 και 3, είναι σε τάξη.

76
00:03:25,490 --> 00:03:27,060
Δεν χρειάζεται να κάνετε τίποτα.

77
00:03:27,060 --> 00:03:28,420
3 και 5 είναι σε τάξη.

78
00:03:28,420 --> 00:03:30,150
Δεν χρειάζεται να κάνετε τίποτα εκεί.

79
00:03:30,150 --> 00:03:32,515
>> 5 και 4, που είναι έξω
της τάξης, και γι 'αυτό

80
00:03:32,515 --> 00:03:35,130
Πρέπει να τους ανταλλάξουν και να προσθέσετε
1 στον πάγκο swap.

81
00:03:35,130 --> 00:03:38,880
Και τώρα έχουμε μετακινηθεί 5,
Το επόμενο μεγαλύτερο στοιχείο,

82
00:03:38,880 --> 00:03:40,920
στο τέλος του τμήματος αδιαχώριστα.

83
00:03:40,920 --> 00:03:44,360
Έτσι μπορούμε να αποκαλούμε σήμερα ότι
μέρος του τμήματος ταξινομημένο.

84
00:03:44,360 --> 00:03:47,180
>> Τώρα κοιτάτε το
οθόνη και να πείτε ίσως,

85
00:03:47,180 --> 00:03:50,130
όπως μπορώ, ότι η διάταξη
ταξινομούνται τώρα.

86
00:03:50,130 --> 00:03:51,820
Αλλά δεν μπορούμε να αποδείξουμε ότι ακόμα.

87
00:03:51,820 --> 00:03:54,359
Δεν έχουμε εγγύηση
ότι είναι ταξινομημένο.

88
00:03:54,359 --> 00:03:56,900
Αλλά αυτό είναι όπου η ανταλλαγή
μετρητή πρόκειται να μπαίνουν στο παιχνίδι.

89
00:03:56,900 --> 00:03:59,060
>> Έτσι, έχουμε ολοκληρώσει ένα πέρασμα.

90
00:03:59,060 --> 00:04:00,357
Ο μετρητής swap είναι 2.

91
00:04:00,357 --> 00:04:02,190
Έτσι θα πάμε να επαναλάβουμε
αυτή η διαδικασία και πάλι,

92
00:04:02,190 --> 00:04:04,290
επαναλάβετε μέχρι ο μετρητής ανταλλαγής είναι 0.

93
00:04:04,290 --> 00:04:05,550
Μηδενίστε το μετρητή του swap σε 0.

94
00:04:05,550 --> 00:04:06,820
Γι 'αυτό και θα το επαναφέρετε.

95
00:04:06,820 --> 00:04:09,810
>> Τώρα κοιτάξτε κάθε γειτονικό ζεύγος.

96
00:04:09,810 --> 00:04:11,880
Αυτό είναι σε σειρά, 1 και 2.

97
00:04:11,880 --> 00:04:13,590
2 και 3 είναι σε τάξη.

98
00:04:13,590 --> 00:04:15,010
3 και 4 είναι σε τάξη.

99
00:04:15,010 --> 00:04:19,250
Έτσι, σε αυτό το σημείο, να παρατηρήσετε έχουμε ολοκληρώσει
κοιτάζοντας κάθε γειτονικό ζεύγος,

100
00:04:19,250 --> 00:04:22,530
αλλά ο μετρητής ανταλλαγής είναι ακόμα 0.

101
00:04:22,530 --> 00:04:25,520
>> Αν δεν έχουμε να στραφούν
οποιαδήποτε στοιχεία, τότε

102
00:04:25,520 --> 00:04:28,340
Πρέπει να είναι εντάξει, με
Δυνάμει αυτής της διαδικασίας.

103
00:04:28,340 --> 00:04:32,000
Και έτσι η αποτελεσματικότητα του είδους,
ότι οι επιστήμονες που αγαπούν τον υπολογιστή,

104
00:04:32,000 --> 00:04:35,560
είναι τώρα μπορούμε να δηλώνουμε
η όλη διάταξη πρέπει να

105
00:04:35,560 --> 00:04:38,160
να ταξινομηθούν, γιατί δεν το κάναμε
Πρέπει να ανταλλάξουν κάποια στοιχεία.

106
00:04:38,160 --> 00:04:40,380
Αυτό είναι πολύ ωραίο.

107
00:04:40,380 --> 00:04:43,260
>> Έτσι ποια είναι η χειρότερη περίπτωση
σενάριο με bubble sort;

108
00:04:43,260 --> 00:04:46,240
Στη χειρότερη περίπτωση, η συστοιχία είναι
σε εντελώς αντίστροφη σειρά,

109
00:04:46,240 --> 00:04:49,870
και έτσι πρέπει να φούσκα κάθε
των μεγάλων στοιχείων όλων

110
00:04:49,870 --> 00:04:51,780
τον τρόπο σε όλη την σειρά.

111
00:04:51,780 --> 00:04:55,350
Και πράγματι πρέπει επίσης να
φούσκα όλα τα μικρά στοιχεία πίσω

112
00:04:55,350 --> 00:04:57,050
σε όλη τη διαδρομή κατά μήκος της διάταξης, πάρα πολύ.

113
00:04:57,050 --> 00:05:01,950
Έτσι, κάθε ένα από τα n στοιχεία πρέπει να κινηθεί
σε όλες τις άλλες n στοιχεία.

114
00:05:01,950 --> 00:05:04,102
Έτσι, αυτό είναι το χειρότερο σενάριο.

115
00:05:04,102 --> 00:05:05,810
Στην καλύτερη περίπτωση
σενάριο όμως, αυτό είναι

116
00:05:05,810 --> 00:05:07,880
ελαφρώς διαφορετικό από το είδος επιλογής.

117
00:05:07,880 --> 00:05:10,040
Η σειρά είναι ήδη
ταξινομούνται όταν πάμε στο.

118
00:05:10,040 --> 00:05:12,550
Δεν έχουμε να κάνει οποιαδήποτε
swaps για το πρώτο πέρασμα.

119
00:05:12,550 --> 00:05:14,940
Έτσι, θα μπορούσαμε να πρέπει να κοιτάξουμε
σε λιγότερα στοιχεία, σωστά;

120
00:05:14,940 --> 00:05:18,580
Δεν έχουμε να επαναλάβουμε
επεξεργάζονται αρκετές φορές πάνω.

121
00:05:18,580 --> 00:05:19,540
>> Λοιπόν, τι σημαίνει αυτό;

122
00:05:19,540 --> 00:05:22,390
Έτσι ποια είναι η χειρότερη περίπτωση
για bubble sort, και τι είναι

123
00:05:22,390 --> 00:05:25,330
το καλύτερο σενάριο για bubble sort;

124
00:05:25,330 --> 00:05:27,770
Μήπως να μαντέψετε αυτό;

125
00:05:27,770 --> 00:05:32,420
Στη χειρότερη περίπτωση, θα πρέπει να επαναλάβει
σε όλα τα στοιχεία n n φορές.

126
00:05:32,420 --> 00:05:34,220
Έτσι, η χειρότερη περίπτωση είναι n τετράγωνο.

127
00:05:34,220 --> 00:05:36,550
>> Εάν η συστοιχία είναι τέλεια
ταξινομημένων όμως, το μόνο που

128
00:05:36,550 --> 00:05:38,580
Πρέπει να εξετάσουμε κάθε
των στοιχείων φορά.

129
00:05:38,580 --> 00:05:42,670
Και αν ο μετρητής swap είναι ακόμα 0,
μπορείτε να πείτε αυτός ο πίνακας είναι ταξινομημένο.

130
00:05:42,670 --> 00:05:45,780
Και έτσι στην καλύτερη περίπτωση, αυτό είναι
στην πραγματικότητα καλύτερα από ό, τι η επιλογή

131
00:05:45,780 --> 00:05:49,230
sort-- είναι ωμέγα του ν.

132
00:05:49,230 --> 00:05:50,270
>> Είμαι ο Νταγκ Lloyd.

133
00:05:50,270 --> 00:05:52,140
Αυτό είναι CS50.

134
00:05:52,140 --> 00:05:54,382