1
00:00:00,000 --> 00:00:02,826
>> [Bermain muzik]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Jadi jenis kemasukan adalah satu lagi
algoritma boleh kita gunakan untuk menyelesaikan array.

4
00:00:09,370 --> 00:00:12,350
Idea di sebalik algoritma ini
adalah untuk membina pelbagai disusun anda

5
00:00:12,350 --> 00:00:19,670
di tempat, beralih unsur-unsur daripada
jalan sebagai anda pergi, untuk memberi ruang.

6
00:00:19,670 --> 00:00:22,240
Ini adalah sedikit berbeza
dari jenis pemilihan atau gelembung

7
00:00:22,240 --> 00:00:25,460
jenis, sebagai contoh, 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 kes ini apa yang kita sebenarnya
lakukan adalah unsur-unsur gelongsor

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

11
00:00:31,390 --> 00:00:34,030
Bagaimana algoritma ini
bekerja dalam kod pseudo?

12
00:00:34,030 --> 00:00:37,646
Nah mari kita sewenang-wenangnya mengatakan bahawa
Elemen pertama array disusun.

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

14
00:00:38,770 --> 00:00:42,660
>> Kita akan pergi satu elemen pada satu masa dan
membinanya, dan perkara pertama yang kita lihat

15
00:00:42,660 --> 00:00:43,890
adalah pelbagai satu unsur.

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

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

18
00:00:50,850 --> 00:00:52,900
sehingga semua unsur-unsur yang disusun.

19
00:00:52,900 --> 00:00:57,770
Lihatlah unsur terisih depan dan
masukkannya ke dalam bahagian yang disusun,

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

21
00:01:01,209 --> 00:01:03,750
Mudah-mudahan visualisasi ini
akan membantu anda melihat dengan jelas apa yang

22
00:01:03,750 --> 00:01:05,980
berlaku dengan jenis kemasukan.

23
00:01:05,980 --> 00:01:08,010
>> Jadi sekali lagi, di sini kami
pelbagai keseluruhan terisih,

24
00:01:08,010 --> 00:01:10,970
semua unsur-unsur yang ditunjukkan dalam merah.

25
00:01:10,970 --> 00:01:13,320
Dan mari kita ikut
langkah-langkah pseudokod kami.

26
00:01:13,320 --> 00:01:16,970
Perkara pertama yang kita lakukan, adalah kita panggil
Elemen pertama array, disusun.

27
00:01:16,970 --> 00:01:20,920
Jadi kami hanya akan berkata
lima, anda sedang disusun.

28
00:01:20,920 --> 00:01:24,570
>> Kemudian kami melihat seterusnya
unsur terisih array

29
00:01:24,570 --> 00:01:27,610
dan kami mahu memasukkan bahawa
ke dalam bahagian yang disusun,

30
00:01:27,610 --> 00:01:29,750
dengan mengalihkan unsur berakhir.

31
00:01:29,750 --> 00:01:33,470
Jadi kedua-duanya adalah terisih seterusnya
elemen array.

32
00:01:33,470 --> 00:01:36,250
Jelas sekali ia tergolong sebelum
lima, jadi apa yang kita nak buat

33
00:01:36,250 --> 00:01:41,580
umpama memegang dua diketepikan untuk kali kedua,
beralih lima lebih, dan kemudian masukkan 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 boleh mengatakan bahawa dua disusun.

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

37
00:01:48,400 --> 00:01:50,600
Kami tidak melihat kepada
berehat di semua, tetapi kami telah

38
00:01:50,600 --> 00:01:54,582
mendapat kedua-dua unsur-unsur disusun mengikut
cara mekanisme peralihan.

39
00:01:54,582 --> 00:01:56,410
>> Oleh itu, kita mengulangi proses lagi.

40
00:01:56,410 --> 00:01:58,850
Lihatlah terisih seterusnya
elemen, itu satu.

41
00:01:58,850 --> 00:02:04,010
Mari kita berpegang bahawa selain untuk kali kedua,
beralih segala-galanya ke atas, dan meletakkan 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
melihat satu, dua, dan lima.

44
00:02:08,110 --> 00:02:12,480
Kita tidak tahu apa lagi yang akan datang,
tetapi kami telah disusun ketiga-tiga unsur-unsur.

45
00:02:12,480 --> 00:02:16,030
>> Seterusnya elemen terisih adalah
tiga, jadi kita akan mengetepikannya.

46
00:02:16,030 --> 00:02:18,200
Kami akan beralih terhadap apa yang kita
perlu yang, kali ini

47
00:02:18,200 --> 00:02:21,820
bukan segala-galanya seperti dalam sebelumnya
dua kes, ia hanya lima.

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

49
00:02:25,440 --> 00:02:27,849
>> Enam adalah terisih seterusnya
elemen untuk array.

50
00:02:27,849 --> 00:02:31,140
Dan sebenarnya enam adalah lebih besar daripada lima, jadi
kita tidak perlu melakukan apa-apa bertukar-tukar.

51
00:02:31,140 --> 00:02:35,710
Kita hanya boleh jelujur enam kanan ke
akhir bahagian yang disusun.

52
00:02:35,710 --> 00:02:38,270
>> Akhir sekali, empat adalah
unsur terisih lepas.

53
00:02:38,270 --> 00:02:42,060
Jadi kita akan mengetepikannya, beralih ke atas
unsur-unsur yang perlu kita beralih ke atas,

54
00:02:42,060 --> 00:02:43,780
dan kemudian meletakkan empat mana ia tergolong.

55
00:02:43,780 --> 00:02:46,400
Dan kini melihat, kami telah menyusun
semua unsur-unsur.

56
00:02:46,400 --> 00:02:48,150
Perhatikan dengan kemasukan
jenis, kita tidak mempunyai

57
00:02:48,150 --> 00:02:50,240
untuk kembali dan sebagainya di seluruh array.

58
00:02:50,240 --> 00:02:54,720
Kami hanya pergi di seluruh array
satu masa, dan kita beralih perkara

59
00:02:54,720 --> 00:02:59,870
bahawa kita sudah sedang dihadapi, agar
untuk memberi ruang kepada unsur-unsur baru.

60
00:02:59,870 --> 00:03:02,820
>> Jadi apa kes yang paling teruk
senario dengan jenis kemasukan?

61
00:03:02,820 --> 00:03:05,090
Dalam kes paling teruk,
Pelbagai adalah secara terbalik.

62
00:03:05,090 --> 00:03:11,180
Anda perlu beralih setiap n unsur
sehingga n jawatan, setiap kita kali tunggal

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

64
00:03:12,880 --> 00:03:15,720
Itulah banyak beralih.

65
00:03:15,720 --> 00:03:18,014
>> Dalam kes yang terbaik,
lokasi sempurna disusun.

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

67
00:03:20,680 --> 00:03:23,779
di mana kita boleh jelujur pada
tanpa perlu melakukan apa-apa penukaran gear,

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

69
00:03:24,820 --> 00:03:27,560
>> Jika anda bayangkan bahawa kami
lokasi adalah satu melalui enam,

70
00:03:27,560 --> 00:03:29,900
kita akan memulakan dengan
mengisytiharkan satu disusun.

71
00:03:29,900 --> 00:03:33,300
Dua datang selepas satu supaya kita boleh hanya
berkata, OK, baik satu dan dua yang disusun.

72
00:03:33,300 --> 00:03:36,190
Tiga datang selepas dua jadi, OK,
satu dan dua dan tiga disusun.

73
00:03:36,190 --> 00:03:39,590
>> Kami tidak membuat apa-apa pertukaran, kami
hanya bergerak garis sewenang-wenangnya ini

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

75
00:03:42,460 --> 00:03:46,646
Dengan berkesan seperti yang kita lakukan dalam contoh,
beralih elemen biru, seperti yang kita meneruskan.

76
00:03:46,646 --> 00:03:48,270
Jadi apa kes runtime paling teruk, maka?

77
00:03:48,270 --> 00:03:51,854
Ingat, jika kita perlu beralih setiap
n elemen mungkin n jawatan,

78
00:03:51,854 --> 00:03:54,020
mudah-mudahan yang memberikan anda
idea bahawa kes yang paling teruk

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

80
00:03:57,770 --> 00:04:00,220
>> Jika array adalah sempurna
disusun, semua yang perlu 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 kes ini, ia omega n.

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

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

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