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] [Harvard Universiteti]

3
00:00:04,240 --> 00:00:07,290
[Bu CS50.TV edir]

4
00:00:07,290 --> 00:00:13,060
Nin durub sırala nəzər, nömrə bir siyahısı alaraq və onları çeşidlənməsi üçün alqoritm edək.

5
00:00:13,060 --> 00:00:18,300
Alqoritmi, xatırlayıram, sadəcə bir vəzifə yerinə bir addım-addım prosedurdur.

6
00:00:18,300 --> 00:00:23,640
Durub sırala əsas ideyası, iki hissəni bizim siyahı bölmək üçün

7
00:00:23,640 --> 00:00:26,580
bir sıralanır hissəsi və çeşidlənməmiş hissəsi.

8
00:00:26,580 --> 00:00:29,290
>> Alqoritmi hər addım da, bir sıra köçürülüb

9
00:00:29,290 --> 00:00:32,439
bu çeşidlənməmiş hissəsi olan sıralanır hissəsini

10
00:00:32,439 --> 00:00:35,680
nəhayət qədər tam siyahısı çeşidlənir.

11
00:00:35,680 --> 00:00:43,340
23, 42, 4, 16, 8, 15 - Burada altı çeşidlənməmiş nömrələri siyahısı.

12
00:00:43,340 --> 00:00:47,680
Bu nömrələri üçün artan bütün deyil olduğundan, onlar çeşidlənməmiş edirik.

13
00:00:47,680 --> 00:00:53,890
Biz hələ çeşidlənməsi açılmış deyil ildən, biz bütün altı elementləri bizim çeşidlənməmiş hissəsi hesab edəcəyik.

14
00:00:53,890 --> 00:00:59,270
>> Sonra biz çeşidlənməsi başlamaq, bu solunda Bu sıralanır nömrələri qoymaq lazımdır.

15
00:00:59,270 --> 00:01:03,600
Belə ki, 23 bizim siyahıda ilk element ilə başlamaq imkan verir.

16
00:01:03,600 --> 00:01:06,930
Biz, hələ bizim sıralanır hissəsi hər hansı elementləri yoxdur

17
00:01:06,930 --> 00:01:12,460
belə-nin sadəcə bizim sıralanır hissəsinin başlanğıc və son 23 nəzər salaq.

18
00:01:12,460 --> 00:01:16,510
İndi bizim sıralanır hissəsi bir sıra, 23, var

19
00:01:16,510 --> 00:01:20,260
və çeşidlənməmiş hissəsi bu beş ədəd var.

20
00:01:20,260 --> 00:01:27,320
Indi də sıralanır hissəsi bizim çeşidlənməmiş hissəsi, 42, növbəti sayı daxil edək.

21
00:01:27,320 --> 00:01:35,930
>> Bunu etmək üçün, biz 23-42 müqayisə etmək lazımdır - bizim sıralanır hissəsi yalnız element günə qədər.

22
00:01:35,930 --> 00:01:41,980
Qırx iki 23 böyükdür, belə ki, biz sadəcə sonuna 42 əlavə edə bilərsiniz

23
00:01:41,980 --> 00:01:45,420
siyahının ən sıralanır hissəsi. Böyük!

24
00:01:45,420 --> 00:01:51,850
İndi sıralanır hissəsi iki elementlər vardır və bizim çeşidlənməmiş hissəsi dörd elementlər vardır.

25
00:01:51,850 --> 00:01:57,200
Belə ki, çeşidlənməmiş hissəsi növbəti element, indi isə 4 hərəkət edək.

26
00:01:57,200 --> 00:02:00,230
Belə ki, bu sıralanır hissəsində yerləşir qoyulmalıdır?

27
00:02:00,230 --> 00:02:04,220
>> Unutmayın, biz sıralanır üçün bu sayı yerləşdirmək istəyirəm

28
00:02:04,220 --> 00:02:08,680
bizim sıralanır hissəsi düzgün dəfə sıralanır qalır.

29
00:02:08,680 --> 00:02:14,380
Biz 42 sağ üçün 4 yer, onda bizim siyahı üçün həyata olacaq.

30
00:02:14,380 --> 00:02:18,380
Belə ki, bizim sort hissəsi sağ-sola hərəkət davam edək.

31
00:02:18,380 --> 00:02:23,260
Biz hərəkət olaraq, yeni sayı otaq etmək üçün bir yer aşağı hər bir nömrə keçmək bildirin.

32
00:02:25,440 --> 00:02:31,740
Okay, 4 də az 23, belə ki, biz burada yerləşdirmək mümkün deyil.

33
00:02:31,740 --> 00:02:34,480
Nin 23 doğru bir yerdə hərəkət edək.

34
00:02:36,500 --> 00:02:43,120
>> Biz sıralanır hissəsi ilk yuvasına 4 yerləşdirmək istəyirsinizsə deməkdir.

35
00:02:43,120 --> 00:02:46,300
Siyahıda bu məkan artıq boş necə edək,

36
00:02:46,300 --> 00:02:51,120
biz onlara karşılaştıysanız kimi sıralanır elementləri aşağı hərəkət etdik çünki.

37
00:02:51,120 --> 00:02:52,740
Bütün hüquqlar. Belə ki, biz orada ortasında istəyirik.

38
00:02:52,740 --> 00:02:57,990
Nin sıralanır hissəsi daxil 16 daxil bizim alqoritm davam edək.

39
00:02:59,260 --> 00:03:03,820
On altı az 42-dən, belə ki, bu və sağ üçün 42 keçmək qoy edir.

40
00:03:05,700 --> 00:03:10,190
On altı az 23-dən, belə nin də element keçmək qoy edir.

41
00:03:11,790 --> 00:03:20,820
>> İndi, 16 4-dən çoxdur. Biz 4 və 23 arasında 16 əlavə etmək istədiyiniz kimi Belə ki, görünür.

42
00:03:20,820 --> 00:03:24,620
Sağ sol siyahısı sıralanır hissəsi ilə hərəkət edərkən,

43
00:03:24,620 --> 00:03:29,160
4 Nömrəni daha kiçik olduğunu biz gördük ilk sayı

44
00:03:29,160 --> 00:03:31,540
biz daxil çalışdığınız.

45
00:03:31,540 --> 00:03:35,820
Belə ki, indi biz bu boş yuvasına 16 əlavə edə bilərsiniz

46
00:03:35,820 --> 00:03:40,520
ki, unutmayın, biz artıq sort hissəsində hərəkət elementləri ilə yaratdıq

47
00:03:40,520 --> 00:03:43,340
biz onlara karşılaştıysanız kimi.

48
00:03:43,340 --> 00:03:47,900
>> Bütün hüquqlar. İndi dörd sıralanır elementlər və iki çeşidlənməmiş elementləri var.

49
00:03:47,900 --> 00:03:51,600
Belə ki, ən sıralanır hissəsi daxil 8 hərəkət edək.

50
00:03:51,600 --> 00:03:55,010
Səkkiz az 42 edir.

51
00:03:55,010 --> 00:03:56,940
Səkkiz az 23.

52
00:03:56,940 --> 00:04:00,230
Və 8-dən az 16.

53
00:04:00,230 --> 00:04:03,110
Amma 8 4 çoxdur.

54
00:04:03,110 --> 00:04:07,280
Beləliklə, biz 4 və 16 arasında 8 daxil etmək istərdim.

55
00:04:09,070 --> 00:04:13,650
15 - Və indi biz yalnız sort tərk daha bir element var.

56
00:04:13,950 --> 00:04:16,589
On beş az 42 edir

57
00:04:16,589 --> 00:04:19,130
On beş az 23.

58
00:04:19,130 --> 00:04:21,750
Və 15-dən az 16.

59
00:04:21,750 --> 00:04:24,810
Amma 15 8 çoxdur.

60
00:04:24,810 --> 00:04:27,440
>> Bizim son daxil etmək istədiyiniz Belə ki, burada.

61
00:04:28,770 --> 00:04:30,330
Və biz tamamlayın.

62
00:04:30,330 --> 00:04:33,540
Biz, çeşidlənməmiş hissəsi artıq elementləri var

63
00:04:33,540 --> 00:04:36,670
və bizim sıralanır hissəsi doğru üçün deyil.

64
00:04:36,670 --> 00:04:40,270
Ədədlər kiçik olan ən böyük əmr edir.

65
00:04:40,270 --> 00:04:44,330
Belə ki, biz yalnız ifa addımlar təsvir bəzi pseudocode nəzər salaq.

66
00:04:46,760 --> 00:04:51,740
>> Line 1, biz siyahıda hər element üzərində təkrarlamaq lazımdır görə bilərsiniz

67
00:04:51,740 --> 00:04:57,060
ilk istisna olmaqla, çeşidlənməmiş hissəsi ilk element bəri sadəcə olacaq

68
00:04:57,060 --> 00:05:00,220
bu sıralanır hissəsi ilk element.

69
00:05:00,220 --> 00:05:06,320
Xətləri, 2 və 3-biz çeşidlənməmiş hissəsi bizim cari yer takip saxlanılması edirik.

70
00:05:06,320 --> 00:05:10,450
Element, hazırda sıralaması hissəsi daxil hərəkət sayını

71
00:05:10,450 --> 00:05:15,600
və j də çeşidlənməmiş hissəsi bizim index təmsil edir.

72
00:05:15,600 --> 00:05:20,980
>> Line 4, biz sağ sol sıralanır hissəsi vasitəsilə iterating edirik.

73
00:05:20,980 --> 00:05:26,010
Biz cari vəziyyəti sol element dəfə iterating dayandırmaq istəyirəm

74
00:05:26,010 --> 00:05:30,050
biz daxil çalışdığınız element azdır.

75
00:05:30,050 --> 00:05:35,600
5 satırında, biz doğru bir yer qarşılaşa hər element dəyişkən edirik.

76
00:05:35,600 --> 00:05:40,950
Biz ilk element tapmaq zaman Beləliklə, biz daxil aydın kosmik olacaq

77
00:05:40,950 --> 00:05:44,080
biz hərəkət etdiyiniz element azdır.

78
00:05:44,080 --> 00:05:50,800
Line 6, biz sıralanır hissəsi ilə sol hərəkət davam üçün counter təzələyirik,.

79
00:05:50,800 --> 00:05:56,860
Nəhayət, line 7-də, biz siyahısı sıralanır hissəsi daxil element daxil edirik.

80
00:05:56,860 --> 00:06:00,020
>> Biz, bu mövqe j daxil etmək üçün OK bilirik ki,

81
00:06:00,020 --> 00:06:05,360
biz artıq sağ orada bir yer olmaq üçün istifadə ki element taşıdıktan çünki.

82
00:06:05,360 --> 00:06:09,460
Unutmayın, biz sol sağdan sıralanır hissəsi ilə hərəkət edirik

83
00:06:09,460 --> 00:06:13,960
ancaq sol sağ çeşidlənməmiş hissəsi ilə hərəkət edirik.

84
00:06:13,960 --> 00:06:19,090
Bütün hüquqlar. Indi alqoritm etdi ki, çalışan nə qədər nəzər salaq.

85
00:06:19,090 --> 00:06:25,300
Biz ilk bu alqoritm pis halda çalıştırmak üçün necə sürer sual edəcəyik.

86
00:06:25,300 --> 00:06:29,040
Biz Big O notation ilə çalışan zaman təmsil Xatırladaq ki,.

87
00:06:32,530 --> 00:06:38,500
Bizim siyahısı düzmək üçün, biz, çeşidlənməmiş hissəsi elementləri üzərində təkrarlamaq idi

88
00:06:38,500 --> 00:06:43,430
və potensial sıralanır hissəsi bütün elementləri üzərində həmin elementlərin hər biri üçün.

89
00:06:43,430 --> 00:06:47,950
Daxilən, bir O (n ^ 2) əməliyyat kimi bu səslər.

90
00:06:47,950 --> 00:06:51,840
>> Bizim pseudocode baxanda, biz başqa loop daxili iç içə bir loop var

91
00:06:51,840 --> 00:06:55,290
olan, həqiqətən, bir O (n ^ 2) əməliyyat kimi səslənir.

92
00:06:55,290 --> 00:07:01,590
Lakin siyahı sıralanır hissəsi çox sonuna qədər bütün siyahısı vermədi.

93
00:07:01,590 --> 00:07:06,920
Hələ ki, biz potensial sıralanır hissəsinin başında yeni element daxil edə bilər

94
00:07:06,920 --> 00:07:09,320
alqoritmi hər iteration haqqında

95
00:07:09,320 --> 00:07:14,500
olan biz sıralanır hissəsi hazırda hər element baxmaq istədiyiniz deməkdir.

96
00:07:14,500 --> 00:07:20,090
Belə ki, biz potensial, ikinci element üçün bir müqayisə edə bilər deməkdir

97
00:07:20,090 --> 00:07:24,660
Üçüncü element üçün iki müqayisə, və s.

98
00:07:24,660 --> 00:07:32,480
Belə ki, addımlar ümumi sayı 1-dən siyahı minus 1 uzunluğu integers cəmidir.

99
00:07:32,480 --> 00:07:35,240
Biz bir toplama ilə təmsil edə bilər.

100
00:07:41,170 --> 00:07:47,270
>> Biz burada summations daxil deyil, lakin bu toplama bərabər çıxır ki,

101
00:07:47,270 --> 00:07:57,900
n / 2 - ekvivalent n ^ 2/2 olan 2-dən çox, - n (1 n).

102
00:07:57,900 --> 00:08:00,800
Asimptotik iş haqqında danışarkən,

103
00:08:00,800 --> 00:08:05,170
bu n ^ 2 termini n müddət hakim gedir.

104
00:08:05,170 --> 00:08:11,430
Belə ki, durub sırala Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Biz artıq sıralaması siyahısına daxil sort qaçdı əgər.

106
00:08:16,150 --> 00:08:20,960
Bu halda, biz sadəcə soldan sağa sıralanır hissəsi qurmaq istiyorum.

107
00:08:20,960 --> 00:08:25,050
Belə ki, biz yalnız n addımlar qaydada lazımdır.

108
00:08:25,050 --> 00:08:29,740
>> Yəni, durub sırala n ən yaxşı halda performans o deməkdir ki,

109
00:08:29,740 --> 00:08:34,130
olan biz Ω (n) ilə təmsil edir.

110
00:08:34,130 --> 00:08:36,190
Və ki, durub sırala üçün bu

111
00:08:36,190 --> 00:08:40,429
yalnız çox alqoritmlər biri siyahısını düzmək üçün istifadə edə bilərsiniz.

112
00:08:40,429 --> 00:08:43,210
My name Tommy və bu CS50 edir.

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

114
00:08:46,110 --> 00:08:49,230
Oh, siz yalnız bir dəfə başlayır ki, dayandırmaq bilməz.

115
00:09:01,620 --> 00:09:04,760
Oh, biz etdi - >> Boom!