1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [SORT BUBBLE]

2
00:00:02,840 --> 00:00:04,560
[JACKSON Steinkamp Πανεπιστήμιο Χάρβαρντ]

3
00:00:04,560 --> 00:00:07,500
[ΑΥΤΟ ΕΙΝΑΙ CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Ταξινόμηση φυσαλίδας είναι ένα παράδειγμα ενός αλγορίθμου διαλογής -

5
00:00:11,730 --> 00:00:14,460
δηλαδή, μια διαδικασία για τη διαλογή ενός συνόλου στοιχείων

6
00:00:14,460 --> 00:00:15,840
αύξουσα ή φθίνουσα σειρά.

7
00:00:15,840 --> 00:00:18,710
Για παράδειγμα, αν θέλετε να ταξινομήσετε μια σειρά που αποτελείται από τους αριθμούς

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], η ορθή εφαρμογή των Ταξινόμηση Bubble θα επιστρέψει το

9
00:00:23,060 --> 00:00:26,260
ταξινομημένο πίνακα [2, 3, 5, 9], σε αύξουσα σειρά.

10
00:00:26,260 --> 00:00:28,850
Τώρα, είμαι πρόκειται να εξηγήσω πώς σε ψευδοκώδικα ο αλγόριθμος λειτουργεί.

11
00:00:28,850 --> 00:00:34,000
>> Ας πούμε ότι είμαστε διαλογή μια λίστα από 5 ακέραιοι - 3, 2, 9, 6, και 5.

12
00:00:34,000 --> 00:00:37,650
Ο αλγόριθμος αρχίζει με μια ματιά τα δύο πρώτα στοιχεία, 3 και 2,

13
00:00:37,650 --> 00:00:40,850
και τον έλεγχο αν είναι εκτός σειράς σε σχέση προς το άλλο.

14
00:00:40,850 --> 00:00:43,150
Είναι - 3 είναι μεγαλύτερος από 2.

15
00:00:43,150 --> 00:00:45,190
Για να είναι σε αύξουσα σειρά, θα πρέπει να είναι ο άλλος τρόπος γύρω.

16
00:00:45,190 --> 00:00:46,610
Έτσι, μπορούμε να τους ανταλλάξει.

17
00:00:46,610 --> 00:00:49,760
Τώρα ο κατάλογος μοιάζει με αυτό: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Στη συνέχεια, θα εξετάσουμε το δεύτερο και το τρίτο στοιχείο, 3 και 9.

19
00:00:52,450 --> 00:00:55,770
Είναι στην σωστή σειρά ως προς το άλλο.

20
00:00:55,770 --> 00:00:58,800
Δηλαδή, το 3 είναι μικρότερο από 9, ώστε ο αλγόριθμος δεν τους ανταλλάξει.

21
00:00:58,800 --> 00:01:01,900
Στη συνέχεια, θα δούμε στις 9 και 6. Είναι εκτός λειτουργίας.

22
00:01:01,900 --> 00:01:04,260
>> Έτσι, θα πρέπει να τους ανταλλάξουν επειδή 9 είναι μεγαλύτερο από 6.

23
00:01:04,260 --> 00:01:08,840
Τέλος, θα εξετάσουμε τα τελευταία δύο ακέραιους αριθμούς, 9 και 5.

24
00:01:08,840 --> 00:01:10,850
Είναι εκτός λειτουργίας, οπότε θα πρέπει να ανταλλαχθούν.

25
00:01:10,850 --> 00:01:13,360
Μετά την πρώτη πλήρη διόδου μέσω του καταλόγου,

26
00:01:13,360 --> 00:01:17,140
μοιάζει με αυτό: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Δεν είναι κακό. Είναι σχεδόν ταξινομημένο.

28
00:01:19,690 --> 00:01:22,450
Αλλά θα πρέπει να τρέχει μέσα από τη λίστα και πάλι να το πάρει εντελώς ταξινομημένο.

29
00:01:22,450 --> 00:01:29,250
Δύο είναι λιγότερο από 3, οπότε δεν τα ανταλλάξουν.

30
00:01:29,250 --> 00:01:31,700
>> Τρεις είναι λιγότερο από 6, γι 'αυτό δεν τα ανταλλάξουν.

31
00:01:31,700 --> 00:01:35,500
Έξι είναι μεγαλύτερο από 5. Έχουμε ανταλλάξει.

32
00:01:35,500 --> 00:01:38,460
Έξι είναι λιγότερο από 9. Δεν ανταλλάξουν.

33
00:01:38,460 --> 00:01:42,170
Μετά από το δεύτερο πέρασμα μέσω, μοιάζει με αυτό: [2, 3, 5, 6, 9]. Τέλεια.

34
00:01:42,170 --> 00:01:44,680
Τώρα, ας γράψω σε ψευδοκώδικα.

35
00:01:44,680 --> 00:01:48,450
Βασικά, για κάθε στοιχείο στη λίστα, θα πρέπει να το δει κανείς

36
00:01:48,450 --> 00:01:50,060
και το στοιχείο απευθείας προς τα δεξιά της.

37
00:01:50,060 --> 00:01:53,420
Αν αυτά είναι εκτός σειράς σε σχέση προς το άλλο - δηλαδή, εάν το στοιχείο στην αριστερή

38
00:01:53,420 --> 00:01:56,810
είναι μεγαλύτερη από τη μία στη δεξιά - θα πρέπει να ανταλλάξουν τα δύο στοιχεία.

39
00:01:56,810 --> 00:02:01,270
>> Το κάνουμε αυτό για κάθε στοιχείο της λίστας, και έχουμε κάνει ένα πέρασμα μέσα.

40
00:02:01,270 --> 00:02:05,160
Τώρα απλά πρέπει να κάνουμε τα pass-through αρκετές φορές για να εξασφαλιστεί η λίστα

41
00:02:05,160 --> 00:02:06,480
πλήρως, σωστά ταξινομημένο.

42
00:02:06,480 --> 00:02:08,889
Αλλά πόσες φορές θα πρέπει να περάσει μέσα από τη λίστα για να

43
00:02:08,889 --> 00:02:10,400
εγγυηθεί ότι τελειώσαμε;

44
00:02:10,400 --> 00:02:14,730
Λοιπόν, το χειρότερο σενάριο είναι αν έχουμε ένα εντελώς προς τα πίσω λίστα.

45
00:02:14,730 --> 00:02:17,840
Τότε παίρνει έναν αριθμό περνούν-throughs ίσο με τον αριθμό

46
00:02:17,840 --> 00:02:19,730
των στοιχείων ν-1.

47
00:02:19,730 --> 00:02:24,720
Αν αυτό δεν έχει νόημα διαισθητικά, σκεφτείτε μια απλή υπόθεση - ο κατάλογος [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Αυτό πρόκειται να λάβει ένα pass-through για να ταξινομήσετε σωστά.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Η χειρότερη περίπτωση είναι ότι με 3 στοιχεία ταξινόμηση προς τα πίσω,

50
00:02:33,060 --> 00:02:34,830
πρόκειται να πάρει 2 επαναλήψεις σε είδος.

51
00:02:34,830 --> 00:02:37,980
Μετά από μία επανάληψη, είναι [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Η δεύτερη δίδει την ταξινόμηση array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Έτσι, ξέρετε ότι ποτέ δεν πρέπει να περάσουν από τη σειρά, σε γενικές γραμμές,

54
00:02:43,350 --> 00:02:46,790
περισσότερο από n-1 φορές, όπου n είναι ο αριθμός των στοιχείων της συστοιχίας.

55
00:02:47,090 --> 00:02:50,470
Λέγεται Ταξινόμηση Bubble, διότι τα μεγαλύτερα στοιχεία τείνουν να «φούσκα-up»

56
00:02:50,470 --> 00:02:51,950
προς τα δεξιά αρκετά γρήγορα.

57
00:02:51,950 --> 00:02:53,980
Στην πραγματικότητα, αυτός ο αλγόριθμος έχει πολύ ενδιαφέρουσα συμπεριφορά.

58
00:02:53,980 --> 00:02:57,410
>> Μετά από m επαναλήψεις διαμέσου ολόκληρου συστοιχίας,

59
00:02:57,410 --> 00:02:59,000
είναι εγγυημένα τα δεξιά στοιχεία m

60
00:02:59,000 --> 00:03:01,000
να ταξινομηθούν σε σωστή θέση τους.

61
00:03:01,000 --> 00:03:02,280
Αν θέλετε να δείτε αυτό για τον εαυτό σας,

62
00:03:02,280 --> 00:03:05,500
μπορούμε να προσπαθήσουμε για μια εντελώς προς τα πίσω λίστα [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Μετά από μία διέλευση μέσω της ολόκληρη τη λίστα,

64
00:03:08,220 --> 00:03:09,220
[Ήχος της γραφής]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
το δεξιότερο στοιχείο 9 είναι στην κατάλληλη θέση της.

67
00:03:21,250 --> 00:03:24,760
Μετά τη δεύτερη pass-through, τα 6 θα έχει «φυσαλίδες προς τα πάνω» για το

68
00:03:24,760 --> 00:03:26,220
δεύτερος δεξιά θέση.

69
00:03:26,220 --> 00:03:28,840
Τα δύο αυτά στοιχεία σχετικά με το δικαίωμα - 6 και 9 - θα είναι σε σωστές θέσεις τους

70
00:03:28,840 --> 00:03:30,580
μετά τα δύο πρώτα pass-throughs.

71
00:03:30,580 --> 00:03:32,590
>> Έτσι, πώς μπορούμε να χρησιμοποιήσουμε αυτό για να βελτιστοποιήσει τον αλγόριθμο;

72
00:03:32,590 --> 00:03:34,850
Λοιπόν, μετά από μια επανάληψη διαμέσου της συστοιχίας

73
00:03:34,850 --> 00:03:37,690
δεν πρέπει πραγματικά να ελέγξετε το δεξιότερο στοιχείο

74
00:03:37,690 --> 00:03:39,200
γιατί ξέρουμε ότι είναι ταξινομημένο.

75
00:03:39,200 --> 00:03:43,050
Μετά από δύο επαναλήψεις, γνωρίζουμε με βεβαιότητα τα δεξιά δύο στοιχεία είναι στη θέση τους.

76
00:03:43,050 --> 00:03:48,260
Έτσι, σε γενικές γραμμές, μετά από k επαναλήψεις μέσω της πλήρους συστοιχίας,

77
00:03:48,260 --> 00:03:51,550
ελέγχοντας τα τελευταία στοιχεία k είναι περιττή αφού γνωρίζουμε

78
00:03:51,550 --> 00:03:52,360
ότι είναι στη σωστή θέση ήδη.

79
00:03:52,360 --> 00:03:54,870
>> Έτσι, εάν είστε διαλογή μια σειρά από n στοιχεία,

80
00:03:54,870 --> 00:03:57,870
για την πρώτη επανάληψη - εσείς πρέπει να ταξινομηθούν όλα τα στοιχεία - το πρώτο ν-0.

81
00:03:57,870 --> 00:04:04,170
Με τη δεύτερη επανάληψη, θα πρέπει να εξετάσουμε όλα τα στοιχεία, αλλά η τελευταία -

82
00:04:04,170 --> 00:04:07,090
η πρώτη ν-1.

83
00:04:07,090 --> 00:04:10,520
Μια άλλη βελτιστοποίηση θα μπορούσε να είναι να ελέγξετε αν η λίστα έχει ήδη ταξινομημένο

84
00:04:10,520 --> 00:04:11,710
μετά από κάθε επανάληψη.

85
00:04:11,710 --> 00:04:13,900
Αν είναι ήδη ταξινομημένο, δεν χρειάζεται να προβούν σε οποιαδήποτε περισσότερες επαναλήψεις

86
00:04:13,900 --> 00:04:15,310
μέσω του καταλόγου.

87
00:04:15,310 --> 00:04:16,220
Πώς μπορούμε να το κάνουμε αυτό;

88
00:04:16,220 --> 00:04:19,360
Λοιπόν, αν δεν κάνουμε κανένα swaps για τη μετακύλιση του καταλόγου,

89
00:04:19,360 --> 00:04:22,350
Είναι σαφές ότι ο κατάλογος ήταν ήδη ταξινομημένο γιατί δεν αλλάζετε τίποτα.

90
00:04:22,350 --> 00:04:24,160
Γι 'αυτό και σίγουρα δεν πρέπει να ταξινομήσετε και πάλι.

91
00:04:24,160 --> 00:04:27,960
>> Ίσως θα μπορούσατε να προετοιμάσει μια μεταβλητή που ονομάζεται σημαία »δεν ταξινομημένο» να

92
00:04:27,960 --> 00:04:30,990
false και αλλάξτε την σε πραγματική, αν έχετε να ανταλλάξουν στοιχεία σχετικά με οποιεσδήποτε

93
00:04:30,990 --> 00:04:32,290
μία επανάληψη διαμέσου της συστοιχίας.

94
00:04:32,290 --> 00:04:35,350
Ή ομοίως, να κάνει ένα μετρητή να μετρήσει πόσες swaps που κάνετε

95
00:04:35,350 --> 00:04:37,040
σε οποιαδήποτε δεδομένη επανάληψη.

96
00:04:37,040 --> 00:04:40,040
Στο τέλος της μιας επανάληψης, αν δεν ανταλλάξουν οποιοδήποτε από τα στοιχεία,

97
00:04:40,040 --> 00:04:41,780
γνωρίζετε ότι η λίστα είναι ήδη ταξινομημένο και είστε έτοιμοι.

98
00:04:41,780 --> 00:04:44,090
Ταξινόμηση φούσκα, όπως και οι άλλοι αλγόριθμοι ταξινόμησης, μπορεί να είναι

99
00:04:44,090 --> 00:04:46,960
tweaked να εργαστούν για οποιαδήποτε στοιχεία τα οποία έχουν μια μέθοδος παραγγελίας.

100
00:04:46,960 --> 00:04:50,610
>> Δηλαδή, δύο στοιχεία που έχετε έναν τρόπο να πει εάν η πρώτη

101
00:04:50,610 --> 00:04:53,770
είναι μεγαλύτερη από, ίση ή μικρότερη από τη δεύτερη.

102
00:04:53,770 --> 00:04:56,870
Για παράδειγμα, μπορείτε να ταξινομήσετε τα γράμματα του αλφαβήτου με το ρητό

103
00:04:56,870 --> 00:05:00,520
ότι α <b, b <c, κλπ.

104
00:05:00,520 --> 00:05:03,830
Εναλλακτικά, μπορείτε να ταξινομήσετε τις ημέρες της εβδομάδας, όπου Κυριακή είναι μικρότερη από Δευτέρα

105
00:05:03,830 --> 00:05:05,110
οποία είναι μικρότερη από την Τρίτη.

106
00:05:05,110 --> 00:05:09,630
>> Ταξινόμηση Bubble είναι με κανένα τρόπο μια πολύ αποτελεσματική και γρήγορη αλγόριθμο ταξινόμησης.

107
00:05:09,630 --> 00:05:12,370
Στη χειρότερη περίπτωση εκτέλεσης του είναι Big O ν ²

108
00:05:12,370 --> 00:05:14,810
επειδή έχετε να κάνετε n επαναλήψεις σε μια λίστα

109
00:05:14,810 --> 00:05:18,430
τον έλεγχο όλων των στοιχείων κάθε n pass-through, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Αυτό το χρόνο εκτέλεσης σημαίνει ότι ο αριθμός των στοιχείων είστε διαλογής αυξήσεις,

111
00:05:22,730 --> 00:05:24,330
ο χρόνος λειτουργίας αυξάνεται τετραγωνικώς.

112
00:05:24,330 --> 00:05:27,330
>> Αλλά αν απόδοσης δεν είναι μια σημαντική ανησυχία του προγράμματός σας

113
00:05:27,330 --> 00:05:29,550
ή αν είστε διαλογή μόνο ένα μικρό αριθμό στοιχείων,

114
00:05:29,550 --> 00:05:31,660
μπορείτε να βρείτε Ταξινόμηση Bubble χρήσιμο γιατί

115
00:05:31,660 --> 00:05:33,360
είναι ένα από τα απλούστερα αλγορίθμων ταξινόμησης να κατανοήσουν

116
00:05:33,360 --> 00:05:34,250
και να κωδικοποιήσει.

117
00:05:34,250 --> 00:05:37,270
Είναι επίσης ένας πολύ καλός τρόπος για να πάρετε την εμπειρία με τη μετάφραση ενός θεωρητικού

118
00:05:37,270 --> 00:05:40,220
αλγορίθμου σε πραγματικό κώδικα λειτουργία.

119
00:05:40,220 --> 00:05:43,000
Λοιπόν, αυτό είναι Ταξινόμηση Bubble για σας. Ευχαριστώ για την προσοχή.

120
00:05:43,000 --> 00:05:44,000
CS50.TV