1
00:00:00,000 --> 00:00:03,360
>> [MÜZİK OYUN]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
Doug LLOYD: Pekala,
Kabarcık sıralama bir algoritma

4
00:00:06,730 --> 00:00:08,730
Eğer elemanlarının bir dizi sıralamak için kullanabilirsiniz.

5
00:00:08,730 --> 00:00:10,850
Nasıl çalıştığına bir göz atalım.

6
00:00:10,850 --> 00:00:13,240
>> Yani temel fikir arkasında
kabarcık sıralama budur.

7
00:00:13,240 --> 00:00:17,340
Biz genellikle daha yükseklere taşımak istiyoruz
Genellikle sağa doğru değerli elemanları,

8
00:00:17,340 --> 00:00:20,340
ve genellikle değerli elemanları alt
sola, biz beklediğiniz gibi.

9
00:00:20,340 --> 00:00:23,256
Biz düşük şeyler olmak istiyorum
başlangıç ​​ve daha yüksek şeyler

10
00:00:23,256 --> 00:00:24,970
sonunda olmak.

11
00:00:24,970 --> 00:00:26,130
>> Bunu nasıl yapacağız?

12
00:00:26,130 --> 00:00:28,040
Peki pseudocode kodunda,
Biz diyelim, söyleyebiliriz

13
00:00:28,040 --> 00:00:30,320
sıfır olmayan bir değere bir takas sayacı ayarlayın.

14
00:00:30,320 --> 00:00:32,570
Biz ikinci bunu neden biz göreceğiz.

15
00:00:32,570 --> 00:00:36,090
Ve sonra biz şu tekrarlayın
swap sayacı 0 olana kadar süreç,

16
00:00:36,090 --> 00:00:39,910
ya da hiç swapları yapana kadar.

17
00:00:39,910 --> 00:00:43,170
>> Takas sayacını sıfırlayın
0 Zaten 0 değilse.

18
00:00:43,170 --> 00:00:46,420
Sonra her bakmak
elemanların bitişik çifti.

19
00:00:46,420 --> 00:00:49,550
Bu iki unsur ise
değil sırayla, takas,

20
00:00:49,550 --> 00:00:51,620
ve takas sayacına 1 eklenir.

21
00:00:51,620 --> 00:00:53,870
Hakkında düşünüyorsanız
Bu onu görselleştirmek önce,

22
00:00:53,870 --> 00:00:57,471
Bu alt hareket edeceğini fark
sola değerli elemanlar

23
00:00:57,471 --> 00:01:00,720
ve daha yüksek, sağ unsurları değerli
etkili biz ne yapmak istediğinizi yapıyor,

24
00:01:00,720 --> 00:01:03,940
olanlar grupları taşımak olduğunu
bu şekilde elemanların.

25
00:01:03,940 --> 00:01:07,035
En bu nasıl görselleştirmek edelim
Bizim dizi kullanarak görünebilir

26
00:01:07,035 --> 00:01:10,504
Biz sınamak için kullanılan bu
Bu algoritmalar dışarı.

27
00:01:10,504 --> 00:01:13,420
Biz burada tekrar bir sıralanmamış dizi var
tüm elemanları ile gösterilen

28
00:01:13,420 --> 00:01:14,840
kırmızı olmak.

29
00:01:14,840 --> 00:01:17,970
Ve ben takas sayacı ayarlamak
sıfır olmayan bir değere.

30
00:01:17,970 --> 00:01:20,610
Ben keyfi seçti
Negatif 1-- 0 değil.

31
00:01:20,610 --> 00:01:23,840
Biz bu işlemi tekrarlamak istiyorum
swap sayacı kadar 0'dır.

32
00:01:23,840 --> 00:01:26,540
Benim takas set Bu yüzden
Bazı sıfır olmayan bir değere karşı,

33
00:01:26,540 --> 00:01:29,400
çünkü aksi takdirde
swap sayacı 0 olacaktır.

34
00:01:29,400 --> 00:01:31,610
Biz bile başlamak olmaz
algoritmanın bir işlem.

35
00:01:31,610 --> 00:01:33,610
Yani yine adımlar mudur
takas sayacını sıfırlamak

36
00:01:33,610 --> 00:01:37,900
0, daha sonra her bitişik bakmak
çifti, onlar sıra dışı iseniz,

37
00:01:37,900 --> 00:01:40,514
Bunları takas ve 1 ekleyin
takas sayaç.

38
00:01:40,514 --> 00:01:41,680
Yani bu süreci başlasın.

39
00:01:41,680 --> 00:01:44,430
Yani biz bunu ilk şey
Biz 0 takas sayacı ayarlayın

40
00:01:44,430 --> 00:01:46,660
ve sonra aramaya başlamak
Her bitişik çifti.

41
00:01:46,660 --> 00:01:49,140
>> Bu yüzden ilk 5 ve 2 bakarak başlayın.

42
00:01:49,140 --> 00:01:52,410
Biz onlar dışarı görüyoruz
sipariş ve bu yüzden onları takas.

43
00:01:52,410 --> 00:01:53,830
Ve biz takas sayacına 1 eklenir.

44
00:01:53,830 --> 00:01:57,860
Yani şimdi bizim takas sayacı 1,
2 ve 5 anahtarlamalı oylandı.

45
00:01:57,860 --> 00:01:59,370
Şimdi tekrar işlemi yineleyin.

46
00:01:59,370 --> 00:02:03,540
>> Önümüzdeki bitişik çifti bakmak,
5 ve onlar da sipariş bitti 1--,

47
00:02:03,540 --> 00:02:06,960
bu yüzden onları takas ve ekleme
Swap sayacına 1.

48
00:02:06,960 --> 00:02:08,900
Sonra 5 ve 3 bak.

49
00:02:08,900 --> 00:02:13,830
Bunlar bozuk, bu yüzden takas
Onları biz swap sayacına 1 eklenir.

50
00:02:13,830 --> 00:02:15,550
Sonra 5 ve 6 bakmak.

51
00:02:15,550 --> 00:02:18,630
Bunlar sırayla konum, bu yüzden aslında yok
için herşeyi bu kez takas gerekir.

52
00:02:18,630 --> 00:02:20,250
Sonra 6 ve 4 bakmak.

53
00:02:20,250 --> 00:02:24,920
Bunlar bozuk da, o yüzden biz takas
Onları biz swap sayacına 1 eklenir.

54
00:02:24,920 --> 00:02:26,230
>> Şimdi ne olduğunu fark.

55
00:02:26,230 --> 00:02:29,514
Biz sonuna kadar 6 Bütün yol taşındım.

56
00:02:29,514 --> 00:02:32,180
Seçim tür Yani, yasiyorsaniz
o video görüldü ne yaptığımız oldu

57
00:02:32,180 --> 00:02:35,290
Biz hareket sona erdi
bina küçük elemanları

58
00:02:35,290 --> 00:02:39,640
esasen Sıralı dizi
büyük için en küçük sağa sola.

59
00:02:39,640 --> 00:02:43,200
Kabarcık tür durumda, eğer
Bu, özel bir algoritma sonra,

60
00:02:43,200 --> 00:02:46,720
biz aslında bina için gidiyoruz
Sağ taraftan sıralanan dizi

61
00:02:46,720 --> 00:02:49,100
küçüğüne, en büyük sola.

62
00:02:49,100 --> 00:02:53,840
Biz etkili bir şekilde 6, kabarmış var
en büyük değer, sonuna kadar tüm yol.

63
00:02:53,840 --> 00:02:56,165
>> Ve böylece biz şimdi bildirebilirsiniz
Bu sıralanır olduğunu,

64
00:02:56,165 --> 00:02:59,130
ve gelecekteki iterations--
dizinin geçiyor vasıtasıyla yine

65
00:02:59,130 --> 00:03:01,280
artık 6 düşünmek zorunda değilsiniz.

66
00:03:01,280 --> 00:03:03,850
Biz sadece düşünmek zorundayız
sıralanmamış elemanlar

67
00:03:03,850 --> 00:03:06,299
ne zaman bitişik çiftler bakıyoruz.

68
00:03:06,299 --> 00:03:08,340
Yani biz bir bitirdikten
kabarcık sıralama geçer.

69
00:03:08,340 --> 00:03:11,941
Yani şimdi biz soruya geri dönmek,
swap sayacı 0 olana kadar tekrarlayın.

70
00:03:11,941 --> 00:03:13,690
Peki takas sayacı
4, bu yüzden gidiyoruz

71
00:03:13,690 --> 00:03:15,410
Yine bu işlemi tekrar tutmak için.

72
00:03:15,410 --> 00:03:19,180
>> Biz takas sayacını sıfırlamak için gidiyoruz
0 ve her komşu çifti bak.

73
00:03:19,180 --> 00:03:21,890
Bu yüzden onlar konum 1-- 2 ile başlar ve
sıra dışı, bu yüzden onları takas

74
00:03:21,890 --> 00:03:23,620
ve biz takas sayacına 1 eklenir.

75
00:03:23,620 --> 00:03:25,490
2 ve 3, onlar sırayla konum.

76
00:03:25,490 --> 00:03:27,060
Biz bir şey yapmanız gerekmez.

77
00:03:27,060 --> 00:03:28,420
3 ve 5 olarak sıralanmıştır.

78
00:03:28,420 --> 00:03:30,150
Biz orada bir şey yapmanıza gerek yok.

79
00:03:30,150 --> 00:03:32,515
>> 5 ve 4, onlar dışarı
düzen, ve bu yüzden biz

80
00:03:32,515 --> 00:03:35,130
Bunları takas ve eklemeniz gerekir
Swap sayacına 1.

81
00:03:35,130 --> 00:03:38,880
Ve şimdi biz 5 hareket ettik
sonraki en büyük unsur,

82
00:03:38,880 --> 00:03:40,920
sıralanmamış kısmının ucuna.

83
00:03:40,920 --> 00:03:44,360
Yani biz şimdi çağırabilirsiniz
sıralanmış kısmının bir parçası.

84
00:03:44,360 --> 00:03:47,180
>> Şimdi bakıyoruz
Ekran ve muhtemelen söyleyebilirim,

85
00:03:47,180 --> 00:03:50,130
, I can dizisi bu kadar
Şu anda sıralanır.

86
00:03:50,130 --> 00:03:51,820
Ama biz henüz ispat edemez.

87
00:03:51,820 --> 00:03:54,359
Biz bir garanti yok
o sıralanmış oluyor.

88
00:03:54,359 --> 00:03:56,900
Ama bu nereye takas olduğunu
sayaç devreye girer gidiyor.

89
00:03:56,900 --> 00:03:59,060
>> Bu yüzden bir geçiş tamamladık.

90
00:03:59,060 --> 00:04:00,357
Takas sayacı 2 'dir.

91
00:04:00,357 --> 00:04:02,190
Bu yüzden tekrar gidiyoruz
Yine bu proses,

92
00:04:02,190 --> 00:04:04,290
swap sayacı 0 olana kadar tekrarlayın.

93
00:04:04,290 --> 00:04:05,550
0 takas sayacını sıfırlayın.

94
00:04:05,550 --> 00:04:06,820
Yani biz sıfırlamak gerekir.

95
00:04:06,820 --> 00:04:09,810
>> Şimdi her bitişik çifti bak.

96
00:04:09,810 --> 00:04:11,880
Bu, sırayla, 1 ve 2 bu.

97
00:04:11,880 --> 00:04:13,590
2 ve 3 olarak sıralanmıştır.

98
00:04:13,590 --> 00:04:15,010
3 ve 4 olarak sıralanmıştır.

99
00:04:15,010 --> 00:04:19,250
Yani bu noktada, biz tamamladık fark
Her komşu çifti bakarak,

100
00:04:19,250 --> 00:04:22,530
ancak takas sayacı hala 0'dır.

101
00:04:22,530 --> 00:04:25,520
>> Biz geçmek yoksa
Herhangi elemanları, daha sonra

102
00:04:25,520 --> 00:04:28,340
tarafından sırayla olmalıdır
Bu sürecin erdem.

103
00:04:28,340 --> 00:04:32,000
Ve böylece tür bir etkinlik,
biz bilgisayar bilim seviyorum,

104
00:04:32,000 --> 00:04:35,560
Şimdi bildirebilirsiniz edilir
Tüm dizi gerekir

105
00:04:35,560 --> 00:04:38,160
we did not, çünkü sıralanabilir
Herhangi elemanları takas etmek zorunda.

106
00:04:38,160 --> 00:04:40,380
Bu oldukça güzel.

107
00:04:40,380 --> 00:04:43,260
>> Peki kötü durumda bulunuyor
kabarcık sıralama ile senaryo?

108
00:04:43,260 --> 00:04:46,240
En kötü durumda dizidir
Tamamen tersten,

109
00:04:46,240 --> 00:04:49,870
ve bu yüzden her kabarcık var
Büyük bütün elemanları

110
00:04:49,870 --> 00:04:51,780
dizi boyunca yol.

111
00:04:51,780 --> 00:04:55,350
Ve biz etkili bir de var
kabarcık küçük elemanların hepsi geri

112
00:04:55,350 --> 00:04:57,050
Çok dizi boyunca tüm yol.

113
00:04:57,050 --> 00:05:01,950
Yani n elemanlarının her hareket etmek zorundadır
Diğer n elemanlarının tamamında.

114
00:05:01,950 --> 00:05:04,102
Yani en kötü senaryo.

115
00:05:04,102 --> 00:05:05,810
En iyi durumda
senaryo olsa da, bu

116
00:05:05,810 --> 00:05:07,880
Seçim sıralama biraz farklı.

117
00:05:07,880 --> 00:05:10,040
Dizi zaten
Biz giderken sıralanır.

118
00:05:10,040 --> 00:05:12,550
Biz herhangi bir yapmak zorunda değilsiniz
ilk geçişte swapları.

119
00:05:12,550 --> 00:05:14,940
Yani biz bakmak zorunda kalabilirsiniz
Daha az unsurları, değil mi?

120
00:05:14,940 --> 00:05:18,580
Biz bu tekrarlamak zorunda değilsiniz
üzerinde birkaç kez işlemek.

121
00:05:18,580 --> 00:05:19,540
>> Peki bu ne anlama geliyor?

122
00:05:19,540 --> 00:05:22,390
Peki en kötü senaryo var
kabarcık sıralama için, ve ne

123
00:05:22,390 --> 00:05:25,330
kabarcık sıralama için en iyi senaryo?

124
00:05:25,330 --> 00:05:27,770
Bunu tahmin mü?

125
00:05:27,770 --> 00:05:32,420
En kötü durumda, yineleme var
Bütün n elemanlı n kere arasında.

126
00:05:32,420 --> 00:05:34,220
Yani en kötü durum n karesi edilir.

127
00:05:34,220 --> 00:05:36,550
>> Dizi mükemmel değilse
Sıralanan olsa da, sadece

128
00:05:36,550 --> 00:05:38,580
Her bakmak zorunda
Bir kez elemanları.

129
00:05:38,580 --> 00:05:42,670
Ve takas sayacı hala 0 ise,
Bu dizi sıralanır söyleyebiliriz.

130
00:05:42,670 --> 00:05:45,780
Böylece en iyi durumda, bu
seçim daha aslında daha iyi

131
00:05:45,780 --> 00:05:49,230
sort-- o n omega var.

132
00:05:49,230 --> 00:05:50,270
>> Ben Doug Lloyd değilim.

133
00:05:50,270 --> 00:05:52,140
Bu CS50 olduğunu.

134
00:05:52,140 --> 00:05:54,382