1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Insertion Sort]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Universiti Harvard]

3
00:00:04,240 --> 00:00:07,290
[Ini adalah CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Mari kita lihat pada apapun kemasukan, algoritma untuk mengambil senarai nombor dan menyusun mereka.

5
00:00:13,060 --> 00:00:18,300
Algoritma, ingat, hanya satu prosedur langkah-demi-langkah untuk mencapai tugas.

6
00:00:18,300 --> 00:00:23,640
Idea asas di sebalik jenis kemasukan, adalah untuk membahagikan senarai kami ke dalam dua bahagian,

7
00:00:23,640 --> 00:00:26,580
sebahagian disusun dan bahagian Unsorted.

8
00:00:26,580 --> 00:00:29,290
>> Pada setiap langkah algoritma, nombor berpindah

9
00:00:29,290 --> 00:00:32,439
dari bahagian Unsorted untuk bahagian disusun

10
00:00:32,439 --> 00:00:35,680
sehingga akhirnya seluruh senarai diisih.

11
00:00:35,680 --> 00:00:43,340
Berikut adalah senarai enam nombor Unsorted - 23, 42, 4, 16, 8, dan 15.

12
00:00:43,340 --> 00:00:47,680
Sejak nombor-nombor ini tidak semua dalam tertib menaik, mereka Unsorted.

13
00:00:47,680 --> 00:00:53,890
Kerana kita telah tidak mula sorting lagi, kita akan mempertimbangkan kesemua enam elemen bahagian Unsorted kami.

14
00:00:53,890 --> 00:00:59,270
>> Sebaik sahaja kita mula menyusun, kami akan meletakkan nombor-nombor yang disusun di sebelah kiri ini.

15
00:00:59,270 --> 00:01:03,600
Jadi, mari kita mulakan dengan 23, elemen pertama dalam senarai kami.

16
00:01:03,600 --> 00:01:06,930
Kami tidak mempunyai sebarang unsur-unsur di bahagian disusun kami lagi,

17
00:01:06,930 --> 00:01:12,460
jadi mari kita hanya mempertimbangkan 23 hingga menjadi permulaan dan akhir bahagian disusun kami.

18
00:01:12,460 --> 00:01:16,510
Sekarang, bahagian kami disusun mempunyai satu nombor, 23,

19
00:01:16,510 --> 00:01:20,260
dan bahagian Unsorted kami mempunyai kelima-lima nombor.

20
00:01:20,260 --> 00:01:27,320
Mari kita kini memasukkan nombor seterusnya dalam bahagian Unsorted kami, 42, ke bahagian disusun.

21
00:01:27,320 --> 00:01:35,930
>> Untuk berbuat demikian, kita akan perlu untuk membandingkan 42 hingga 23 - elemen hanya di bahagian disusun kami setakat ini.

22
00:01:35,930 --> 00:01:41,980
Empat puluh dua adalah lebih besar daripada 23, jadi kita hanya boleh menambah 42 hingga akhir

23
00:01:41,980 --> 00:01:45,420
bahagian disusun senarai. Hebat!

24
00:01:45,420 --> 00:01:51,850
Sekarang bahagian kami disusun mempunyai dua unsur, dan bahagian Unsorted kami mempunyai empat unsur.

25
00:01:51,850 --> 00:01:57,200
Jadi, mari kita kini bergerak ke 4, elemen seterusnya dalam bahagian Unsorted.

26
00:01:57,200 --> 00:02:00,230
Jadi, di mana ini harus diletakkan di bahagian disusun?

27
00:02:00,230 --> 00:02:04,220
>> Ingat, kita mahu meletakkan nombor ini dalam usaha disusun

28
00:02:04,220 --> 00:02:08,680
jadi bahagian kita disusun kekal disusun dengan betul pada setiap masa.

29
00:02:08,680 --> 00:02:14,380
Jika kita meletakkan 4, ke kanan daripada 42, maka senarai kami akan keluar perintah.

30
00:02:14,380 --> 00:02:18,380
Jadi, mari kita terus bergerak ke kanan-ke-kiri di bahagian apapun kami.

31
00:02:18,380 --> 00:02:23,260
Seperti yang kita bergerak, mari kita beralih setiap nombor ke tempat untuk membuat ruang untuk nombor baru.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 adalah juga kurang daripada 23, jadi kita tidak boleh meletakkan di sini sama ada.

33
00:02:31,740 --> 00:02:34,480
Mari kita bergerak 23 betul satu tempat.

34
00:02:36,500 --> 00:02:43,120
>> Ini bermakna kita ingin meletakkan 4, ke dalam slot yang pertama di bahagian disusun.

35
00:02:43,120 --> 00:02:46,300
Perhatikan bagaimana ruang ini dalam senarai sudah kosong,

36
00:02:46,300 --> 00:02:51,120
kerana kita telah bergerak disusun unsur-unsur seperti yang kita temui mereka.

37
00:02:51,120 --> 00:02:52,740
Semua hak. Jadi, kita sudah separuh di sana.

38
00:02:52,740 --> 00:02:57,990
Mari kita terus algoritma kami dengan memasukkan 16 ke bahagian disusun.

39
00:02:59,260 --> 00:03:03,820
Sixteen adalah kurang dari 42, jadi mari kita beralih daripada 42 ke kanan.

40
00:03:05,700 --> 00:03:10,190
Sixteen juga kurang dari 23, jadi mari kita juga beralih elemen yang.

41
00:03:11,790 --> 00:03:20,820
>> Sekarang, 16 adalah lebih besar daripada 4. Jadi, ia kelihatan seperti kita ingin memasukkan 16 antara 4 dan 23.

42
00:03:20,820 --> 00:03:24,620
Walaupun bergerak melalui bahagian disusun senarai dari kanan ke kiri,

43
00:03:24,620 --> 00:03:29,160
4 adalah nombor pertama kita telah melihat yang lebih kecil daripada bilangan

44
00:03:29,160 --> 00:03:31,540
kita sedang berusaha untuk memasukkan.

45
00:03:31,540 --> 00:03:35,820
Jadi, sekarang kita boleh memasukkan 16 ke dalam slot ini kosong,

46
00:03:35,820 --> 00:03:40,520
ingat, kita telah dicipta oleh unsur-unsur yang bergerak di bahagian apapun lebih

47
00:03:40,520 --> 00:03:43,340
seperti yang kita temui mereka.

48
00:03:43,340 --> 00:03:47,900
>> Semua hak. Sekarang, kita mempunyai empat unsur-unsur disusun dan dua elemen Unsorted.

49
00:03:47,900 --> 00:03:51,600
Jadi, mari kita menggerakkan 8 ke bahagian disusun.

50
00:03:51,600 --> 00:03:55,010
Lapan adalah kurang daripada 42.

51
00:03:55,010 --> 00:03:56,940
Lapan adalah kurang daripada 23.

52
00:03:56,940 --> 00:04:00,230
Dan 8 adalah kurang daripada 16.

53
00:04:00,230 --> 00:04:03,110
Tetapi 8 adalah lebih besar daripada 4.

54
00:04:03,110 --> 00:04:07,280
Jadi, kami ingin untuk memasukkan 8 antara 4 dan 16 yang.

55
00:04:09,070 --> 00:04:13,650
Dan sekarang kita hanya mempunyai satu elemen yang lebih ditinggalkan untuk menyusun - 15 hingga.

56
00:04:13,950 --> 00:04:16,589
Lima belas adalah kurang daripada 42,

57
00:04:16,589 --> 00:04:19,130
Lima belas adalah kurang daripada 23.

58
00:04:19,130 --> 00:04:21,750
Dan 15 adalah kurang daripada 16.

59
00:04:21,750 --> 00:04:24,810
Tetapi 15 adalah lebih besar daripada 8.

60
00:04:24,810 --> 00:04:27,440
>> Jadi, di sini adalah di mana kita mahu untuk membuat kemasukan akhir kami.

61
00:04:28,770 --> 00:04:30,330
Dan kami sudah selesai.

62
00:04:30,330 --> 00:04:33,540
Kami tidak mempunyai unsur-unsur yang lebih dalam bahagian Unsorted,

63
00:04:33,540 --> 00:04:36,670
dan bahagian kami disusun dalam susunan yang betul.

64
00:04:36,670 --> 00:04:40,270
Nombor disusun daripada yang terkecil hingga terbesar.

65
00:04:40,270 --> 00:04:44,330
Jadi, mari kita melihat pseudokod beberapa yang menerangkan langkah-langkah yang kita hanya dilakukan.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, kita dapat melihat bahawa kita perlukan untuk melelar atas setiap elemen dalam senarai

67
00:04:51,740 --> 00:04:57,060
kecuali yang pertama, kerana elemen yang pertama dalam bahagian Unsorted hanya akan menjadi

68
00:04:57,060 --> 00:05:00,220
elemen pertama dalam bahagian disusun.

69
00:05:00,220 --> 00:05:06,320
Pada baris 2 dan 3, kami sedang mengesan tempat semasa kami di bahagian Unsorted.

70
00:05:06,320 --> 00:05:10,450
Unsur mewakili bilangan yang kita sedang bergerak ke bahagian disusun,

71
00:05:10,450 --> 00:05:15,600
dan j mewakili indeks kami ke bahagian Unsorted.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, kita iterating melalui bahagian yang disusun dari kanan ke kiri.

73
00:05:20,980 --> 00:05:26,010
Kami mahu menghentikan iterating sekali unsur ke kiri kedudukan semasa kami

74
00:05:26,010 --> 00:05:30,050
adalah kurang daripada elemen yang kita sedang berusaha untuk memasukkan.

75
00:05:30,050 --> 00:05:35,600
Pada baris 5, kita beralih setiap elemen kita menghadapi satu ruang ke kanan.

76
00:05:35,600 --> 00:05:40,950
Cara itu, kita akan mempunyai ruang yang jelas untuk memasukkan ke dalam apabila kita dapati elemen pertama

77
00:05:40,950 --> 00:05:44,080
kurang daripada elemen yang kita sedang bergerak.

78
00:05:44,080 --> 00:05:50,800
On line 6, kami sedang mengemaskini kaunter kami untuk terus bergerak kiri melalui bahagian disusun.

79
00:05:50,800 --> 00:05:56,860
Akhirnya, on line 7, kita sedang memasukkan unsur ke bahagian disusun senarai.

80
00:05:56,860 --> 00:06:00,020
>> Kita tahu bahawa ia adalah ok untuk masukkan ke dalam kedudukan j,

81
00:06:00,020 --> 00:06:05,360
kerana kita sudah berpindah elemen yang digunakan untuk berada di sana satu ruang ke kanan.

82
00:06:05,360 --> 00:06:09,460
Ingat, kita sedang bergerak melalui bahagian yang disusun dari kanan ke kiri,

83
00:06:09,460 --> 00:06:13,960
tetapi kita bergerak melalui bahagian Unsorted dari kiri ke kanan.

84
00:06:13,960 --> 00:06:19,090
Semua hak. Mari kita kini mengambil melihat berapa lama berjalan bahawa algoritma mengambil.

85
00:06:19,090 --> 00:06:25,300
Kita mula-mula akan bertanya soalan berapa lama ia mengambil masa untuk algoritma ini untuk menjalankan dalam kes terburuk.

86
00:06:25,300 --> 00:06:29,040
Ingatlah bahawa kita mewakili kali ini berjalan dengan notasi O Big.

87
00:06:32,530 --> 00:06:38,500
Dalam usaha untuk menyusun senarai kami, kami terpaksa untuk melelar lebih unsur-unsur di bahagian Unsorted,

88
00:06:38,500 --> 00:06:43,430
dan bagi setiap unsur-unsur, yang berpotensi ke atas semua unsur dalam bahagian disusun.

89
00:06:43,430 --> 00:06:47,950
Intuitif, ini bunyi seperti operasi O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Melihat pseudokod kita, kita mempunyai gelung bersarang di dalam gelung lain,

91
00:06:51,840 --> 00:06:55,290
yang, sememangnya, bunyi seperti operasi O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
Walau bagaimanapun, bahagian yang disusun senarai tidak mengandungi senarai keseluruhan sehingga akhir sangat.

93
00:07:01,590 --> 00:07:06,920
Namun, kita berpotensi memasukkan elemen baru pada awal-awal bahagian disusun

94
00:07:06,920 --> 00:07:09,320
pada setiap lelaran algoritma,

95
00:07:09,320 --> 00:07:14,500
yang bermaksud bahawa kita akan perlu untuk melihat setiap elemen kini dalam bahagian disusun.

96
00:07:14,500 --> 00:07:20,090
Jadi, ini bermakna kita berpotensi membuat satu perbandingan untuk elemen kedua,

97
00:07:20,090 --> 00:07:24,660
dua perbandingan bagi unsur ketiga, dan sebagainya.

98
00:07:24,660 --> 00:07:32,480
Jadi, jumlah langkah-langkah adalah jumlah integer dari 1 hingga panjang senarai tolak 1.

99
00:07:32,480 --> 00:07:35,240
Kita boleh mewakili ini dengan penjumlahan.

100
00:07:41,170 --> 00:07:47,270
>> Kami tidak akan pergi ke dalam penjumlahan di sini, tetapi ia ternyata bahawa penjumlahan ini adalah sama dengan

101
00:07:47,270 --> 00:07:57,900
n (n - 1) lebih dari 2, yang bersamaan n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Apabila bercakap tentang runtime asimptot,

103
00:08:00,800 --> 00:08:05,170
ini n ^ 2 istilah itu akan menguasai istilah ini n.

104
00:08:05,170 --> 00:08:11,430
Jadi, apapun kemasukan adalah Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Bagaimana jika kita berlari apapun kemasukan dalam senarai yang sudah disusun.

106
00:08:16,150 --> 00:08:20,960
Dalam kes itu, kita hanya mahu membina bahagian yang disusun dari kiri ke kanan.

107
00:08:20,960 --> 00:08:25,050
Jadi, kita hanya perlukan atas perintah langkah n.

108
00:08:25,050 --> 00:08:29,740
>> Ini bermakna bahawa apapun kemasukan mempunyai prestasi terbaik kes n,

109
00:08:29,740 --> 00:08:34,130
yang kita mewakili Ω (n).

110
00:08:34,130 --> 00:08:36,190
Dan itulah ia untuk menyelesaikan kemasukan,

111
00:08:36,190 --> 00:08:40,429
hanya salah satu daripada banyak algoritma yang boleh kita gunakan untuk menyusun senarai.

112
00:08:40,429 --> 00:08:43,210
Nama saya adalah Tommy, dan ini adalah CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, anda hanya tidak boleh menghentikan bahawa apabila ia bermula.

115
00:09:01,620 --> 00:09:04,760
Oh, kita lakukan bahawa - >> Boom!