1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Sortir Penyisipan]

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

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 insertion sort, algoritma untuk mengambil daftar nomor dan menyortir mereka.

5
00:00:13,060 --> 00:00:18,300
Sebuah algoritma, ingat, hanyalah sebuah prosedur langkah-demi-langkah untuk menyelesaikan suatu tugas.

6
00:00:18,300 --> 00:00:23,640
Ide dasar dibalik insertion sort, adalah untuk membagi daftar kami menjadi dua bagian,

7
00:00:23,640 --> 00:00:26,580
sebagian diurutkan dan bagian unsorted.

8
00:00:26,580 --> 00:00:29,290
>> Pada setiap langkah algoritma, nomor tersebut akan dipindahkan

9
00:00:29,290 --> 00:00:32,439
dari bagian unsorted ke bagian diurutkan

10
00:00:32,439 --> 00:00:35,680
sampai akhirnya seluruh daftar yang diurutkan.

11
00:00:35,680 --> 00:00:43,340
Berikut adalah daftar dari enam nomor disortir - 23, 42, 4, 16, 8, dan 15.

12
00:00:43,340 --> 00:00:47,680
Karena angka-angka ini tidak semua dalam urutan, mereka unsorted.

13
00:00:47,680 --> 00:00:53,890
Karena kita belum mulai menyortir lagi, kami akan mempertimbangkan semua enam elemen sebagian unsorted kami.

14
00:00:53,890 --> 00:00:59,270
>> Setelah kita mulai menyortir, kita akan menempatkan angka-angka diurutkan di sebelah kiri ini.

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

16
00:01:03,600 --> 00:01:06,930
Kami tidak memiliki unsur-unsur dalam porsi kami belum diurutkan,

17
00:01:06,930 --> 00:01:12,460
jadi mari kita hanya mempertimbangkan 23 menjadi awal dan akhir dari bagian kami diurutkan.

18
00:01:12,460 --> 00:01:16,510
Sekarang, sebagian kami diurutkan memiliki satu nomor, 23,

19
00:01:16,510 --> 00:01:20,260
dan bagian unsorted kami memiliki lima angka.

20
00:01:20,260 --> 00:01:27,320
Sekarang mari kita masukkan nomor berikutnya di bagian unsorted kami,, 42 ke bagian diurutkan.

21
00:01:27,320 --> 00:01:35,930
>> Untuk melakukannya, kita harus membandingkan 42 ke 23 - satu-satunya unsur dalam porsi kami diurutkan sejauh ini.

22
00:01:35,930 --> 00:01:41,980
Empat puluh dua lebih besar dari 23, sehingga kita hanya dapat menambahkan 42 sampai akhir

23
00:01:41,980 --> 00:01:45,420
dari bagian diurutkan dari daftar. Great!

24
00:01:45,420 --> 00:01:51,850
Sekarang bagian kami diurutkan memiliki dua elemen, dan bagian unsorted kami memiliki empat elemen.

25
00:01:51,850 --> 00:01:57,200
Jadi, mari kita sekarang pindah ke 4, elemen berikutnya di bagian unsorted.

26
00:01:57,200 --> 00:02:00,230
Jadi, di mana hal ini harus ditempatkan di bagian diurutkan?

27
00:02:00,230 --> 00:02:04,220
>> Ingat, kita ingin menempatkan nomor ini dalam rangka diurutkan

28
00:02:04,220 --> 00:02:08,680
sehingga porsi kami diurutkan tetap benar diurutkan setiap saat.

29
00:02:08,680 --> 00:02:14,380
Jika kita menempatkan 4 di sebelah kanan dari 42, maka daftar kami akan rusak.

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

31
00:02:18,380 --> 00:02:23,260
Ketika kita bergerak, mari kita bergeser ke setiap nomor tempat untuk memberikan ruang bagi nomor baru.

32
00:02:25,440 --> 00:02:31,740
Oke, 4 juga kurang dari 23, jadi kami tidak dapat menempatkan di sini baik.

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

34
00:02:36,500 --> 00:02:43,120
>> Itu berarti kita ingin menempatkan 4 ke dalam slot pertama di bagian diurutkan.

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

36
00:02:46,300 --> 00:02:51,120
karena kami sudah bergerak elemen diurutkan turun seperti yang kita temui mereka.

37
00:02:51,120 --> 00:02:52,740
Baiklah. Jadi, kami setengah jalan di sana.

38
00:02:52,740 --> 00:02:57,990
Mari kita lanjutkan algoritma kami dengan memasukkan 16 ke bagian diurutkan.

39
00:02:59,260 --> 00:03:03,820
Enam belas kurang dari 42, jadi mari kita menggeser ke kanan 42.

40
00:03:05,700 --> 00:03:10,190
Enam belas juga kurang dari 23, jadi mari kita juga menggeser elemen.

41
00:03:11,790 --> 00:03:20,820
>> Sekarang, 16 lebih besar dari 4. Jadi, sepertinya kita ingin memasukkan 16 antara 4 dan 23.

42
00:03:20,820 --> 00:03:24,620
Sementara bergerak melalui bagian diurutkan daftar dari kanan ke kiri,

43
00:03:24,620 --> 00:03:29,160
4 adalah angka pertama kita lihat yang lebih kecil dari jumlah

44
00:03:29,160 --> 00:03:31,540
kami mencoba untuk memasukkan.

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

46
00:03:35,820 --> 00:03:40,520
yang, ingat, kami telah diciptakan oleh elemen bergerak di bagian atas semacam

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

48
00:03:43,340 --> 00:03:47,900
>> Baiklah. Sekarang, kami memiliki empat elemen diurutkan dan dua elemen unsorted.

49
00:03:47,900 --> 00:03:51,600
Jadi, mari kita memindahkan 8 ke bagian diurutkan.

50
00:03:51,600 --> 00:03:55,010
Delapan kurang dari 42.

51
00:03:55,010 --> 00:03:56,940
Delapan kurang dari 23.

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

53
00:04:00,230 --> 00:04:03,110
Tapi 8 lebih besar dari 4.

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

55
00:04:09,070 --> 00:04:13,650
Dan sekarang kita hanya memiliki satu elemen yang tersisa untuk memilah - 15.

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

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

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

59
00:04:21,750 --> 00:04:24,810
Tapi 15 lebih besar dari 8.

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

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

62
00:04:30,330 --> 00:04:33,540
Kami tidak memiliki elemen lebih di bagian unsorted,

63
00:04:33,540 --> 00:04:36,670
dan bagian kami diurutkan dalam urutan yang benar.

64
00:04:36,670 --> 00:04:40,270
Angka-angka yang dipesan dari terkecil sampai terbesar.

65
00:04:40,270 --> 00:04:44,330
Jadi, mari kita lihat beberapa pseudocode yang menggambarkan langkah-langkah kita hanya dilakukan.

66
00:04:46,760 --> 00:04:51,740
>> On line 1, kita dapat melihat bahwa kita harus iterate atas setiap elemen dalam daftar

67
00:04:51,740 --> 00:04:57,060
kecuali yang pertama, sejak elemen pertama di bagian unsorted hanya akan menjadi

68
00:04:57,060 --> 00:05:00,220
elemen pertama di bagian diurutkan.

69
00:05:00,220 --> 00:05:06,320
Pada baris 2 dan 3, kita melacak tempat kami saat ini di bagian unsorted.

70
00:05:06,320 --> 00:05:10,450
Elemen merupakan jumlah kami sedang bergerak ke bagian diurutkan,

71
00:05:10,450 --> 00:05:15,600
dan j merupakan indeks kami ke bagian unsorted.

72
00:05:15,600 --> 00:05:20,980
>> On line 4, kita iterasi melalui bagian diurutkan dari kanan ke kiri.

73
00:05:20,980 --> 00:05:26,010
Kami ingin menghentikan iterasi sekali elemen di sebelah kiri posisi kita saat ini

74
00:05:26,010 --> 00:05:30,050
kurang dari elemen kita mencoba untuk memasukkan.

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

76
00:05:35,600 --> 00:05:40,950
Dengan begitu, kita akan memiliki ruang yang jelas untuk memasukkan ke dalam ketika kita menemukan elemen pertama

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

78
00:05:44,080 --> 00:05:50,800
On line 6, kami meng-update counter kami untuk terus bergerak ke kiri melalui bagian diurutkan.

79
00:05:50,800 --> 00:05:56,860
Akhirnya, pada baris 7, kita memasukkan elemen ke bagian diurutkan dari daftar.

80
00:05:56,860 --> 00:06:00,020
>> Kita tahu bahwa tidak apa-apa untuk memasukkan ke posisi j,

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

82
00:06:05,360 --> 00:06:09,460
Ingat, kita bergerak melalui bagian diurutkan dari kanan ke kiri,

83
00:06:09,460 --> 00:06:13,960
tapi kami bergerak melalui bagian unsorted dari kiri ke kanan.

84
00:06:13,960 --> 00:06:19,090
Baiklah. Mari sekarang kita lihat berapa lama berjalan yang mengambil algoritma.

85
00:06:19,090 --> 00:06:25,300
Kami pertama-tama akan bertanya berapa lama waktu yang diperlukan untuk algoritma ini berjalan dalam kasus terburuk.

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

87
00:06:32,530 --> 00:06:38,500
Untuk menyelesaikan daftar kami, kami harus iterate atas unsur-unsur di bagian unsorted,

88
00:06:38,500 --> 00:06:43,430
dan untuk masing-masing elemen, berpotensi atas seluruh elemen di bagian diurutkan.

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

90
00:06:47,950 --> 00:06:51,840
>> Melihat pseudocode kami, kami memiliki loop bersarang di dalam loop lain,

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

92
00:06:55,290 --> 00:07:01,590
Namun, bagian diurutkan daftar tidak mengandung seluruh daftar sampai akhir.

93
00:07:01,590 --> 00:07:06,920
Namun, kita berpotensi bisa memasukkan unsur baru pada awal dari bagian diurutkan

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

95
00:07:09,320 --> 00:07:14,500
yang berarti bahwa kita harus melihat setiap elemen saat ini di bagian diurutkan.

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

97
00:07:20,090 --> 00:07:24,660
dua perbandingan untuk elemen ketiga, dan seterusnya.

98
00:07:24,660 --> 00:07:32,480
Jadi, jumlah langkah adalah jumlah dari bilangan bulat dari 1 sampai panjang daftar dikurangi 1.

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

100
00:07:41,170 --> 00:07:47,270
>> Kami tidak akan masuk ke penjumlahan di sini, tapi ternyata bahwa penjumlahan ini sama dengan

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

102
00:07:57,900 --> 00:08:00,800
Ketika berbicara tentang runtime asimtotik,

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

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

105
00:08:11,430 --> 00:08:16,150
Bagaimana jika kita berlari insertion sort pada daftar yang sudah diurutkan.

106
00:08:16,150 --> 00:08:20,960
Dalam hal ini, kita hanya akan membangun bagian diurutkan dari kiri ke kanan.

107
00:08:20,960 --> 00:08:25,050
Jadi, kita hanya perlu pada urutan langkah n.

108
00:08:25,050 --> 00:08:29,740
>> Itu berarti bahwa insertion sort memiliki performa terbaik-kasus n,

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

110
00:08:34,130 --> 00:08:36,190
Dan itu untuk insertion sort,

111
00:08:36,190 --> 00:08:40,429
hanya salah satu dari banyak algoritma yang bisa kita gunakan untuk mengurutkan daftar.

112
00:08:40,429 --> 00:08:43,210
Nama saya 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 tidak bisa berhenti bahwa setelah dimulai.

115
00:09:01,620 --> 00:09:04,760
Oh, kami melakukan itu - Boom >>!