1
00:00:00,000 --> 00:00:02,826
>> [MUSIC PLAYING]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> Doug LLOYD: Jadi insertion sort adalah lain
algoritma bisa kita gunakan untuk mengurutkan array.

4
00:00:09,370 --> 00:00:12,350
Ide di balik algoritma ini
adalah untuk membangun array diurutkan Anda

5
00:00:12,350 --> 00:00:19,670
di tempat, pergeseran unsur dari
cara saat Anda pergi, untuk membuat ruang.

6
00:00:19,670 --> 00:00:22,240
Ini sedikit berbeda
dari pemilihan semacam atau gelembung

7
00:00:22,240 --> 00:00:25,460
semacam, misalnya, di mana
kita menyesuaikan lokasi,

8
00:00:25,460 --> 00:00:26,910
di mana kita membuat swap.

9
00:00:26,910 --> 00:00:29,760
>> Dalam hal ini apa yang kita benar-benar
lakukan adalah elemen geser

10
00:00:29,760 --> 00:00:31,390
lebih, keluar dari jalan.

11
00:00:31,390 --> 00:00:34,030
Bagaimana algoritma ini
bekerja di pseudocode?

12
00:00:34,030 --> 00:00:37,646
Nah mari kita sewenang-wenang mengatakan bahwa
elemen pertama dari array diurutkan.

13
00:00:37,646 --> 00:00:38,770
Kami sedang membangun di tempat.

14
00:00:38,770 --> 00:00:42,660
>> Kita akan pergi satu elemen pada suatu waktu dan
membangunnya, dan hal pertama yang kita lihat

15
00:00:42,660 --> 00:00:43,890
adalah array satu elemen.

16
00:00:43,890 --> 00:00:47,720
Dan menurut definisi, satu
elemen array diurutkan.

17
00:00:47,720 --> 00:00:50,850
>> Kemudian kita akan mengulangi proses ini until--
kita akan mengulangi proses berikut

18
00:00:50,850 --> 00:00:52,900
sampai semua elemen diurutkan.

19
00:00:52,900 --> 00:00:57,770
Lihatlah elemen disortir berikutnya dan
masukkan ke bagian diurutkan,

20
00:00:57,770 --> 00:01:01,209
dengan menggeser jumlah yang diperlukan
elemen keluar dari jalan.

21
00:01:01,209 --> 00:01:03,750
Semoga visualisasi ini
akan membantu Anda melihat apa yang

22
00:01:03,750 --> 00:01:05,980
terjadi dengan insertion sort.

23
00:01:05,980 --> 00:01:08,010
>> Jadi sekali lagi, inilah kami
seluruh array disortir,

24
00:01:08,010 --> 00:01:10,970
semua elemen yang ditunjukkan dengan warna merah.

25
00:01:10,970 --> 00:01:13,320
Dan mari kita ikuti
langkah dari pseudocode kami.

26
00:01:13,320 --> 00:01:16,970
Hal pertama yang kita lakukan, adalah kita sebut
elemen pertama dari array, diurutkan.

27
00:01:16,970 --> 00:01:20,920
Jadi kita hanya akan mengatakan
lima, Anda sekarang diurutkan.

28
00:01:20,920 --> 00:01:24,570
>> Kemudian kita melihat ke depan
elemen dari array disortir

29
00:01:24,570 --> 00:01:27,610
dan kami ingin memasukkan bahwa
ke bagian diurutkan,

30
00:01:27,610 --> 00:01:29,750
dengan menggeser elemen lebih.

31
00:01:29,750 --> 00:01:33,470
Jadi keduanya adalah disortir berikutnya
elemen dari array.

32
00:01:33,470 --> 00:01:36,250
Jelas itu milik sebelum
lima, jadi apa yang akan kami lakukan

33
00:01:36,250 --> 00:01:41,580
adalah semacam memegang dua disisihkan untuk kedua,
bergeser lima lebih, dan kemudian memasukkan dua

34
00:01:41,580 --> 00:01:43,210
sebelum lima, di mana untuk harus pergi.

35
00:01:43,210 --> 00:01:45,280
Dan sekarang kita dapat mengatakan bahwa dua diurutkan.

36
00:01:45,280 --> 00:01:48,400
>> Jadi seperti yang Anda lihat, kami telah hanya sejauh
melihat dua elemen array.

37
00:01:48,400 --> 00:01:50,600
Kami belum melihat di
beristirahat sama sekali, tapi kami sudah

38
00:01:50,600 --> 00:01:54,582
mendapat dua elemen Buruk
cara mekanisme pergeseran.

39
00:01:54,582 --> 00:01:56,410
>> Jadi kita ulangi proses lagi.

40
00:01:56,410 --> 00:01:58,850
Lihatlah disortir berikutnya
elemen, itu salah satu.

41
00:01:58,850 --> 00:02:04,010
Mari kita terus bahwa selain untuk kedua,
bergeser segalanya lebih, dan menempatkan satu

42
00:02:04,010 --> 00:02:05,570
di mana ia harus pergi.

43
00:02:05,570 --> 00:02:08,110
>> Sekali lagi, masih, kami telah hanya pernah
memandang satu, dua, dan lima.

44
00:02:08,110 --> 00:02:12,480
Kami tidak tahu apa lagi yang akan datang,
tapi kami sudah diurutkan tiga unsur.

45
00:02:12,480 --> 00:02:16,030
>> Unsur berikutnya adalah disortir
tiga, jadi kita akan sisihkan.

46
00:02:16,030 --> 00:02:18,200
Kami akan bergeser atas apa yang kita
perlu yang, saat ini

47
00:02:18,200 --> 00:02:21,820
bukan segalanya seperti pada sebelumnya
dua kasus, itu hanya lima.

48
00:02:21,820 --> 00:02:25,440
Dan kemudian kita akan tetap tiga,
antara dua dan lima.

49
00:02:25,440 --> 00:02:27,849
>> Enam adalah berikutnya disortir
elemen array.

50
00:02:27,849 --> 00:02:31,140
Dan pada kenyataannya enam lebih besar dari lima, sehingga
kita bahkan tidak perlu melakukan swapping apapun.

51
00:02:31,140 --> 00:02:35,710
Kami hanya dapat taktik enam tepat ke
akhir dari bagian diurutkan.

52
00:02:35,710 --> 00:02:38,270
>> Terakhir, empat adalah
elemen disortir lalu.

53
00:02:38,270 --> 00:02:42,060
Jadi kita akan sisihkan, bergeser lebih
unsur-unsur yang kita perlu menggeser lebih,

54
00:02:42,060 --> 00:02:43,780
dan kemudian menempatkan empat tempatnya.

55
00:02:43,780 --> 00:02:46,400
Dan sekarang lihat, kita sudah semacam
dari semua elemen.

56
00:02:46,400 --> 00:02:48,150
Perhatikan dengan penyisipan
semacam, kami tidak memiliki

57
00:02:48,150 --> 00:02:50,240
untuk pergi bolak-balik melintasi array.

58
00:02:50,240 --> 00:02:54,720
Kami hanya pergi di array
satu waktu, dan kami bergeser hal-hal

59
00:02:54,720 --> 00:02:59,870
bahwa kita sudah dihadapi, dalam rangka
untuk memberikan ruang bagi elemen baru.

60
00:02:59,870 --> 00:03:02,820
>> Jadi apa kasus terburuk
Skenario dengan insertion sort?

61
00:03:02,820 --> 00:03:05,090
Dalam kasus terburuk,
array dalam urutan terbalik.

62
00:03:05,090 --> 00:03:11,180
Anda harus menggeser masing-masing elemen n
hingga posisi n, setiap kali kita tunggal

63
00:03:11,180 --> 00:03:12,880
membuat penyisipan.

64
00:03:12,880 --> 00:03:15,720
Itu banyak pergeseran.

65
00:03:15,720 --> 00:03:18,014
>> Dalam kasus terbaik,
array sempurna diurutkan.

66
00:03:18,014 --> 00:03:20,680
Dan semacam seperti apa yang terjadi
dengan lima dan enam dalam contoh,

67
00:03:20,680 --> 00:03:23,779
di mana kita bisa taktik pada
tanpa harus melakukan pergeseran,

68
00:03:23,779 --> 00:03:24,820
kita pada dasarnya akan melakukan itu.

69
00:03:24,820 --> 00:03:27,560
>> Jika Anda membayangkan bahwa kami
Array adalah satu sampai enam,

70
00:03:27,560 --> 00:03:29,900
kami akan memulai dengan
menyatakan satu diurutkan.

71
00:03:29,900 --> 00:03:33,300
Dua datang setelah satu sehingga kita bisa hanya
mengatakan, OK, baik satu dan dua diurutkan.

72
00:03:33,300 --> 00:03:36,190
Tiga datang setelah dua demikian, OK,
satu dan dua dan tiga diurutkan.

73
00:03:36,190 --> 00:03:39,590
>> Kami tidak membuat swap, kami
hanya bergerak baris sewenang-wenang ini

74
00:03:39,590 --> 00:03:42,460
antara diurutkan dan disortir seperti yang kita pergi.

75
00:03:42,460 --> 00:03:46,646
Seefektif yang kita lakukan pada contoh,
mengubah elemen biru, seperti yang kita lanjutkan.

76
00:03:46,646 --> 00:03:48,270
Jadi apa kasus runtime terburuk, maka?

77
00:03:48,270 --> 00:03:51,854
Ingat, jika kita harus menggeser setiap
elemen n mungkin posisi n,

78
00:03:51,854 --> 00:03:54,020
mudah-mudahan yang memberi Anda
ide bahwa kasus terburuk

79
00:03:54,020 --> 00:03:57,770
runtime adalah O Big n kuadrat.

80
00:03:57,770 --> 00:04:00,220
>> Jika array adalah sempurna
diurutkan, semua harus kita lakukan

81
00:04:00,220 --> 00:04:04,480
adalah melihat setiap elemen tunggal
sekali, dan kemudian kami sudah selesai.

82
00:04:04,480 --> 00:04:08,440
Jadi dalam kasus terbaik, itu omega dari n.

83
00:04:08,440 --> 00:04:09,490
>> Aku Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Ini adalah CS50.

85
00:04:11,760 --> 00:04:13,119