1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Ταξινόμηση Insertion]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Πανεπιστήμιο του Χάρβαρντ]

3
00:00:04,240 --> 00:00:07,290
[Αυτό είναι CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Ας ρίξουμε μια ματιά στο είδος εισαγωγής, ένας αλγόριθμος για τη λήψη μια λίστα με τους αριθμούς και τη διαλογή τους.

5
00:00:13,060 --> 00:00:18,300
Ένας αλγόριθμος, να θυμάστε, είναι απλά ένα βήμα-προς-βήμα διαδικασία για την ολοκλήρωση μιας εργασίας.

6
00:00:18,300 --> 00:00:23,640
Η βασική ιδέα πίσω από ταξινόμηση με εισαγωγή, είναι να διαιρέσει λίστα μας σε δύο τμήματα,

7
00:00:23,640 --> 00:00:26,580
ένα ταξινομημένο τμήμα και ένα τμήμα αδιαχώριστα.

8
00:00:26,580 --> 00:00:29,290
>> Σε κάθε βήμα του αλγορίθμου, ένας αριθμός κινείται

9
00:00:29,290 --> 00:00:32,439
αδιαχώριστων από το τμήμα προς το τμήμα ταξινόμηση

10
00:00:32,439 --> 00:00:35,680
έως ότου τελικά ολόκληρη η λίστα είναι ταξινομημένη.

11
00:00:35,680 --> 00:00:43,340
Αυτή είναι η λίστα των έξι αδιαχώριστα αριθμών - 23, 42, 4, 16, 8, και 15.

12
00:00:43,340 --> 00:00:47,680
Δεδομένου ότι οι αριθμοί αυτοί δεν είναι όλοι σε αύξουσα σειρά, από όπου και αν έχουν υποστεί διαλογή.

13
00:00:47,680 --> 00:00:53,890
Από τη στιγμή που δεν έχουν ξεκινήσει ακόμη τη διαλογή, θα εξετάσουμε και τα έξι στοιχεία αδιαχώριστα τμήμα μας.

14
00:00:53,890 --> 00:00:59,270
>> Μόλις αρχίζουμε τη διαλογή, θα βάλουμε αυτούς τους αριθμούς ταξινόμηση προς τα αριστερά από αυτά.

15
00:00:59,270 --> 00:01:03,600
Λοιπόν, ας ξεκινήσουμε με το 23, το πρώτο στοιχείο στη λίστα μας.

16
00:01:03,600 --> 00:01:06,930
Δεν έχουμε κανένα στοιχείο σε ταξινομημένο τμήμα μας ακόμη,

17
00:01:06,930 --> 00:01:12,460
οπότε ας θεωρούν απλά 23 να είναι η αρχή και το τέλος της ταξινομημένο τμήμα μας.

18
00:01:12,460 --> 00:01:16,510
Τώρα, ταξινομημένο τμήμα μας έχει έναν αριθμό, 23,

19
00:01:16,510 --> 00:01:20,260
και αδιαχώριστα τμήμα μας έχει αυτά τα πέντε αριθμούς.

20
00:01:20,260 --> 00:01:27,320
Ας προστεθεί τώρα τον επόμενο αριθμό μαζί με τα υπόλοιπα τμήμα μας, 42, μέσα στο ταξινομημένο τμήμα.

21
00:01:27,320 --> 00:01:35,930
>> Για να γίνει αυτό, θα πρέπει να συγκρίνετε το 42 έως το 23 - το μόνο στοιχείο ταξινομημένο τμήμα μας μέχρι τώρα.

22
00:01:35,930 --> 00:01:41,980
Σαράντα δύο είναι μεγαλύτερο από 23, έτσι ώστε να μπορούμε απλά να προσθέσει 42 έως το τέλος

23
00:01:41,980 --> 00:01:45,420
του τμήματος ταξινόμηση της λίστας. Μεγάλη!

24
00:01:45,420 --> 00:01:51,850
Τώρα ταξινομημένο τμήμα μας έχει δύο στοιχεία, και αδιαχώριστα τμήμα μας έχει τέσσερα στοιχεία.

25
00:01:51,850 --> 00:01:57,200
Λοιπόν, ας προχωρήσουμε τώρα στο 4, το επόμενο στοιχείο της αδιαχώριστα τμήμα.

26
00:01:57,200 --> 00:02:00,230
Έτσι, όπου θα πρέπει αυτό να τοποθετείται στο ταξινομημένο τμήμα;

27
00:02:00,230 --> 00:02:04,220
>> Θυμηθείτε, θέλουμε να τοποθετήσετε τον αριθμό αυτό σε ταξινομημένη σειρά

28
00:02:04,220 --> 00:02:08,680
έτσι ταξινομημένο τμήμα μας παραμένει σωστά ταξινομημένο ανά πάσα στιγμή.

29
00:02:08,680 --> 00:02:14,380
Αν τοποθετήσετε τα 4 στα δεξιά του 42, τότε λίστα μας θα είναι εκτός λειτουργίας.

30
00:02:14,380 --> 00:02:18,380
Έτσι, ας συνεχίσει να κινείται από δεξιά προς τα αριστερά σε τμήμα του είδους μας.

31
00:02:18,380 --> 00:02:23,260
Καθώς προχωράμε, ας στραφούν κάθε αριθμό κάτω από ένα μέρος για να κάνει χώρο για το νέο αριθμό.

32
00:02:25,440 --> 00:02:31,740
Εντάξει, 4 είναι επίσης μικρότερη από 23, έτσι δεν μπορούμε να το τοποθετήσετε είτε εδώ.

33
00:02:31,740 --> 00:02:34,480
Ας προχωρήσουμε το 23 σωστό μέρος.

34
00:02:36,500 --> 00:02:43,120
>> Αυτό σημαίνει ότι θα θέλαμε να τοποθετήσετε τα 4 στην πρώτη υποδοχή στο ταξινομημένο τμήμα.

35
00:02:43,120 --> 00:02:46,300
Παρατηρήστε πως ο χώρος αυτός στον κατάλογο ήταν ήδη άδειο,

36
00:02:46,300 --> 00:02:51,120
επειδή έχουμε ήδη κινείται ταξινομημένο κάτω στοιχεία, όπως τους έχουμε συναντήσει.

37
00:02:51,120 --> 00:02:52,740
Εντάξει. Έτσι, είμαστε στα μισά του δρόμου εκεί.

38
00:02:52,740 --> 00:02:57,990
Ας συνεχίσουμε τον αλγόριθμο μας εισάγοντας το 16 στο ταξινομημένο τμήμα.

39
00:02:59,260 --> 00:03:03,820
Δεκαέξι είναι μικρότερη από 42, οπότε ας μετατόπιση των 42 προς τα δεξιά.

40
00:03:05,700 --> 00:03:10,190
Δεκαέξι είναι επίσης μικρότερη από 23, οπότε ας αλλάξει επίσης το στοιχείο αυτό.

41
00:03:11,790 --> 00:03:20,820
>> Τώρα, 16 είναι μεγαλύτερο από 4. Έτσι, μοιάζει θα θέλαμε να εισάγετε το 16 μεταξύ του 4 και του 23.

42
00:03:20,820 --> 00:03:24,620
Ενώ κινούνται διαμέσου του τμήματος με ταξινόμηση του καταλόγου από δεξιά προς αριστερά,

43
00:03:24,620 --> 00:03:29,160
4 είναι ο πρώτος αριθμός που έχουμε δει που είναι μικρότερος από τον αριθμό

44
00:03:29,160 --> 00:03:31,540
προσπαθούμε να εισάγετε.

45
00:03:31,540 --> 00:03:35,820
Έτσι, τώρα μπορούμε να εισάγουμε το 16 σε αυτή την κενή θέση,

46
00:03:35,820 --> 00:03:40,520
η οποία, θυμάστε, έχουμε δημιουργήσει με κινούμενα στοιχεία στο τμήμα είδος πάνω

47
00:03:40,520 --> 00:03:43,340
όπως έχουμε τους συναντήσει.

48
00:03:43,340 --> 00:03:47,900
>> Εντάξει. Τώρα, έχουμε τέσσερις ταξινομημένο στοιχεία και δύο αδιαχώριστα στοιχεία.

49
00:03:47,900 --> 00:03:51,600
Έτσι, ας προχωρήσουμε τα 8 στο ταξινομημένο τμήμα.

50
00:03:51,600 --> 00:03:55,010
Οκτώ είναι μικρότερη από 42.

51
00:03:55,010 --> 00:03:56,940
Οκτώ είναι μικρότερο από 23.

52
00:03:56,940 --> 00:04:00,230
Και 8 είναι μικρότερη από 16.

53
00:04:00,230 --> 00:04:03,110
Αλλά 8 είναι μεγαλύτερο από 4.

54
00:04:03,110 --> 00:04:07,280
Έτσι, θα θέλαμε να εισάγετε τα 8 μεταξύ του 4 και του 16.

55
00:04:09,070 --> 00:04:13,650
Και τώρα έχουμε μόνο ένα ακόμη στοιχείο για να ταξινομήσετε αριστερά - το 15.

56
00:04:13,950 --> 00:04:16,589
Δεκαπέντε είναι μικρότερη από 42,

57
00:04:16,589 --> 00:04:19,130
Δεκαπέντε είναι μικρότερο από 23.

58
00:04:19,130 --> 00:04:21,750
Και 15 είναι μικρότερο από 16.

59
00:04:21,750 --> 00:04:24,810
Αλλά 15 είναι μεγαλύτερη από 8.

60
00:04:24,810 --> 00:04:27,440
>> Έτσι, εδώ είναι που θέλουμε να κάνουν την τελική εισαγωγή μας.

61
00:04:28,770 --> 00:04:30,330
Και τελειώσαμε.

62
00:04:30,330 --> 00:04:33,540
Εμείς δεν έχουμε περισσότερα στοιχεία στο τμήμα αδιαχώριστα,

63
00:04:33,540 --> 00:04:36,670
και ταξινομημένο τμήμα μας είναι στη σωστή σειρά.

64
00:04:36,670 --> 00:04:40,270
Οι αριθμοί διέταξε από το μικρότερο στο μεγαλύτερο.

65
00:04:40,270 --> 00:04:44,330
Έτσι, ας ρίξουμε μια ματιά σε μερικά ψευδοκώδικα που περιγράφει τα βήματα που μόλις πραγματοποιήθηκε.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, μπορούμε να δούμε ότι θα χρειαστεί να επαναλάβει πάνω από κάθε στοιχείο στη λίστα

67
00:04:51,740 --> 00:04:57,060
εκτός από το πρώτο, δεδομένου ότι το πρώτο στοιχείο στο τμήμα αδιαχώριστων θα γίνει απλά

68
00:04:57,060 --> 00:05:00,220
το πρώτο στοιχείο στην ταξινόμηση τμήμα.

69
00:05:00,220 --> 00:05:06,320
Στις γραμμές 2 και 3, είμαστε παρακολουθώντας σημερινή μας θέση στο τμήμα αδιαχώριστα.

70
00:05:06,320 --> 00:05:10,450
Στοιχείο αντιπροσωπεύει τον αριθμό αυτή τη στιγμή κινείται στο ταξινομημένο τμήμα,

71
00:05:10,450 --> 00:05:15,600
και j αντιπροσωπεύει δείκτη μας στο τμήμα αδιαχώριστα.

72
00:05:15,600 --> 00:05:20,980
>> Στις γραμμή 4, είμαστε επανάληψη μέσω της ταξινομημένο τμήμα από τα δεξιά προς τα αριστερά.

73
00:05:20,980 --> 00:05:26,010
Θέλουμε να σταματήσουμε την επανάληψη αφού το στοιχείο προς τα αριστερά της τρέχουσας θέσης μας

74
00:05:26,010 --> 00:05:30,050
είναι μικρότερο από το στοιχείο προσπαθούμε να εισάγετε.

75
00:05:30,050 --> 00:05:35,600
Στη γραμμή 5, είμαστε μετατόπιση κάθε στοιχείο που συναντάμε ένα χώρο προς τα δεξιά.

76
00:05:35,600 --> 00:05:40,950
Με αυτόν τον τρόπο, θα έχουμε μια σαφή χώρο για να τοποθετήσετε μέσα όταν βρίσκουμε το πρώτο στοιχείο

77
00:05:40,950 --> 00:05:44,080
λιγότερο από ό, τι το στοιχείο κινούμαστε.

78
00:05:44,080 --> 00:05:50,800
On line 6, είμαστε ενημέρωση μετρητή μας να συνεχίσει να κινείται αριστερά από το ταξινομημένο τμήμα.

79
00:05:50,800 --> 00:05:56,860
Τέλος, επί της γραμμής 7, είμαστε εισαγωγή του στοιχείου εντός του τμήματος ταξινόμηση της λίστας.

80
00:05:56,860 --> 00:06:00,020
>> Γνωρίζουμε ότι είναι εντάξει για να εισάγετε στο j θέση,

81
00:06:00,020 --> 00:06:05,360
επειδή έχουμε ήδη μετακινηθεί το στοιχείο που χρησιμοποιείται για να υπάρχει ένα διάστημα προς τα δεξιά.

82
00:06:05,360 --> 00:06:09,460
Θυμηθείτε, είμαστε κινείται μέσα από την ταξινομημένο τμήμα από τα δεξιά προς τα αριστερά,

83
00:06:09,460 --> 00:06:13,960
αλλά είμαστε διακινούνται μέσω του τμήματος αδιαχώριστα από τα αριστερά προς τα δεξιά.

84
00:06:13,960 --> 00:06:19,090
Εντάξει. Ας ρίξουμε τώρα μια ματιά στο πώς λειτουργεί καιρό ότι ο αλγόριθμος πήρε.

85
00:06:19,090 --> 00:06:25,300
Θα ρωτήσω πρώτα το ερώτημα πόσο καιρό παίρνει για αυτό τον αλγόριθμο για να τρέξει στη χειρότερη περίπτωση.

86
00:06:25,300 --> 00:06:29,040
Υπενθυμίζουμε ότι εμείς εκπροσωπούμε αυτό το χρόνο λειτουργίας με μεγάλο συμβολισμό O.

87
00:06:32,530 --> 00:06:38,500
Για να ταξινομήσετε τη λίστα μας, είχαμε να επαναλάβει τα στοιχεία πάνω στα μικτά τμήμα,

88
00:06:38,500 --> 00:06:43,430
και για καθένα από τα στοιχεία αυτά, ενδεχομένως πάνω από όλα τα στοιχεία στο ταξινομημένο τμήμα.

89
00:06:43,430 --> 00:06:47,950
Διαισθητικά, αυτό ακούγεται σαν ένα O (n ^ 2) λειτουργία.

90
00:06:47,950 --> 00:06:51,840
>> Κοιτάζοντας ψευδοκώδικα μας, έχουμε ένα βρόχο ένθετα μέσα σε ένα άλλο βρόχο,

91
00:06:51,840 --> 00:06:55,290
η οποία, μάλιστα, ακούγεται σαν ένα O (n ^ 2) λειτουργία.

92
00:06:55,290 --> 00:07:01,590
Ωστόσο, η ταξινόμηση τμήμα του καταλόγου δεν περιέχουν ολόκληρη τη λίστα μέχρι το τέλος.

93
00:07:01,590 --> 00:07:06,920
Ακόμα, θα μπορούσαμε ενδεχομένως να προστεθεί ένα νέο στοιχείο στην αρχή του τμήματος ταξινόμηση

94
00:07:06,920 --> 00:07:09,320
σε κάθε επανάληψη του αλγορίθμου,

95
00:07:09,320 --> 00:07:14,500
πράγμα που σημαίνει ότι εμείς θα πρέπει να εξετάσουμε κάθε στοιχείο σήμερα στο ταξινομημένο τμήμα.

96
00:07:14,500 --> 00:07:20,090
Έτσι, αυτό σημαίνει ότι θα μπορούσε να κάνει ενδεχομένως μια σύγκριση για το δεύτερο στοιχείο,

97
00:07:20,090 --> 00:07:24,660
δύο συγκρίσεις για το τρίτο στοιχείο, και ούτω καθεξής.

98
00:07:24,660 --> 00:07:32,480
Έτσι, ο συνολικός αριθμός των βημάτων είναι το άθροισμα των ακεραίων από 1 έως το μήκος του καταλόγου μείον 1.

99
00:07:32,480 --> 00:07:35,240
Μπορούμε να αντιπροσωπεύει αυτό με μια άθροιση.

100
00:07:41,170 --> 00:07:47,270
>> Δεν θα υπεισέλθω σε αθροίσματα εδώ, αλλά αποδεικνύεται ότι αυτό το άθροισμα είναι ίσο με

101
00:07:47,270 --> 00:07:57,900
n (n - 1) πάνω από 2, το οποίο είναι ισοδύναμο ν ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Όταν μιλάμε για ασυμπτωτική runtime,

103
00:08:00,800 --> 00:08:05,170
αυτή n ^ 2 όρο αυτό πρόκειται να κυριαρχήσει αυτό το ν όρο.

104
00:08:05,170 --> 00:08:11,430
Έτσι, είναι είδος εισαγωγής Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Τι θα συμβεί αν τρέξαμε είδος εισαγωγής σε ήδη ταξινομημένη λίστα.

106
00:08:16,150 --> 00:08:20,960
Σε αυτή την περίπτωση, θα είχαμε απλώς δημιουργήσει το ταξινομημένο τμήμα από τα αριστερά προς τα δεξιά.

107
00:08:20,960 --> 00:08:25,050
Έτσι, θα πρέπει μόνο της τάξης του n βήματα.

108
00:08:25,050 --> 00:08:29,740
>> Αυτό σημαίνει ότι το είδος εισαγωγής έχει καλύτερη απόδοση περίπτωση του n,

109
00:08:29,740 --> 00:08:34,130
την οποία εμείς εκπροσωπούμε με Ω (n).

110
00:08:34,130 --> 00:08:36,190
Και αυτό είναι το είδος για την εισαγωγή,

111
00:08:36,190 --> 00:08:40,429
μόνο ένας από τους πολλούς αλγόριθμους που μπορούμε να χρησιμοποιήσουμε για να ταξινομήσετε μια λίστα.

112
00:08:40,429 --> 00:08:43,210
Το όνομά μου είναι ο Tommy, και αυτό είναι CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Ω, απλά δεν μπορεί να σταματήσει ότι μόλις ξεκινά.

115
00:09:01,620 --> 00:09:04,760
Ω, κάναμε ότι - Boom! >>