1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Bubble SIRALAMA]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP HARVARD UNİVERSİTETİNİN]

3
00:00:04,560 --> 00:00:07,500
[BU CS50 edir. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble Sort bir çeşidlənməsi alqoritm bir nümunəsidir -

5
00:00:11,730 --> 00:00:14,460
ki, elementlərin müəyyən çeşidlənməsi üçün bir prosedurdur

6
00:00:14,460 --> 00:00:15,840
artan və ya azalan.

7
00:00:15,840 --> 00:00:18,710
Bir sıra sort istəyirdi Məsələn, əgər nömrələri ibarət

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], Bubble Sort düzgün həyata qaytarmaq olardı

9
00:00:23,060 --> 00:00:26,260
sıralanır array [2, 3, 5, 9] üçün artan.

10
00:00:26,260 --> 00:00:28,850
İndi alqoritmi çalışır pseudocode izah arkasýndayým.

11
00:00:28,850 --> 00:00:34,000
>> 3, 2, 9, 6 və 5 - Gəlin biz 5 integers bir siyahısı çeşidlənməsi edirik deyirlər.

12
00:00:34,000 --> 00:00:37,650
Bu alqoritm, ilk iki elementləri, 3 və 2 baxaraq başlayır

13
00:00:37,650 --> 00:00:40,850
onlar bir-birinə nisbətən üçün həyata edirsinizsə və yoxlanılması.

14
00:00:40,850 --> 00:00:43,150
Onlar - 3 2-dən böyükdür.

15
00:00:43,150 --> 00:00:45,190
Artan qaydada olmaq üçün, onlar ətrafında digər yol olmalıdır.

16
00:00:45,190 --> 00:00:46,610
Belə ki, biz onları dəyişdirmək.

17
00:00:46,610 --> 00:00:49,760
[2, 3, 9, 6, 5]: İndi siyahısı kimi görünür.

18
00:00:49,760 --> 00:00:52,450
>> Sonra, biz ikinci və üçüncü elementləri, 3 və 9 baxın.

19
00:00:52,450 --> 00:00:55,770
Onlar bir-birinə nisbətən düzgün qaydada edirik.

20
00:00:55,770 --> 00:00:58,800
Alqoritmi onları dəyişdirmək deyil 9 az belə ki, 3 edir.

21
00:00:58,800 --> 00:01:01,900
Sonra, biz 9 və 6 oldu. Onlar üçün bitti.

22
00:01:01,900 --> 00:01:04,260
>> Belə ki, biz 9 6 böyükdür, çünki onların dəyişdirmək lazımdır.

23
00:01:04,260 --> 00:01:08,840
Nəhayət, biz son iki integers, 9 və 5 oldu.

24
00:01:08,840 --> 00:01:10,850
Onlar üçün bitti, onlar dəyişdirildikdə olmalıdır.

25
00:01:10,850 --> 00:01:13,360
Siyahısını ilk tam ötürməsindən sonra,

26
00:01:13,360 --> 00:01:17,140
[2, 3, 6, 5, 9]: Bu kimi görünür.

27
00:01:17,140 --> 00:01:19,690
Pis deyil. Demək olar ki, sıralanır edir.

28
00:01:19,690 --> 00:01:22,450
Amma biz tamamilə sıralanır almaq üçün yenidən siyahısını axır lazımdır.

29
00:01:22,450 --> 00:01:29,250
İki 3-dən az, belə ki, biz onları dəyişdirmək deyil.

30
00:01:29,250 --> 00:01:31,700
>> Three 6 azdır, belə ki, biz onları dəyişdirmək deyil.

31
00:01:31,700 --> 00:01:35,500
Altı 5-dən böyükdür. Biz dəyişdirildikdə.

32
00:01:35,500 --> 00:01:38,460
Altı 9 azdır. Biz dəyişdirmək deyil.

33
00:01:38,460 --> 00:01:42,170
Vasitəsilə ikinci ötürməsindən sonra, bu kimi görünür: [2, 3, 5, 6, 9]. Mükəmməldir.

34
00:01:42,170 --> 00:01:44,680
İndi pseudocode yazmaq edək.

35
00:01:44,680 --> 00:01:48,450
Ümumiyyətlə, siyahıda hər element üçün, biz baxmaq lazımdır

36
00:01:48,450 --> 00:01:50,060
və bilavasitə onun sağ üçün element.

37
00:01:50,060 --> 00:01:53,420
Onlar üçün bir-birinə nisbətən həyata varsa - ki, əgər sol element

38
00:01:53,420 --> 00:01:56,810
hüququ bir daha böyükdür - biz iki elementləri dəyişdirmək lazımdır.

39
00:01:56,810 --> 00:02:01,270
>> Biz siyahısı hər element üçün bunu və biz vasitəsilə bir keçid etdik.

40
00:02:01,270 --> 00:02:05,160
İndi biz yalnız siyahısını təmin etmək ötürmə kifayət dəfə var

41
00:02:05,160 --> 00:02:06,480
tam, düzgün çeşidlənir.

42
00:02:06,480 --> 00:02:08,889
Amma biz siyahısına keçmək neçə dəfə var

43
00:02:08,889 --> 00:02:10,400
biz Bitirdiğinizde garanti?

44
00:02:10,400 --> 00:02:14,730
Biz tamamilə geri siyahısı varsa Yaxşı, ən pis ssenari deyil.

45
00:02:14,730 --> 00:02:17,840
Sonra sayına bərabər keçmək-throughs bir sıra edir

46
00:02:17,840 --> 00:02:19,730
elementlər n-1.

47
00:02:19,730 --> 00:02:24,720
Bu daxilən mənada deyil, sadə bir halda hesab edirəm ki, - siyahısı [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Bu düzgün düzmək üçün bir ötürmə etmək niyyətindədir.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Ən pis halda, 3 elementləri ilə geri sıralanır ki,

50
00:02:33,060 --> 00:02:34,830
bu sort üçün 2 tekrarlamalar etmək olacaq.

51
00:02:34,830 --> 00:02:37,980
Bir iteration sonra, [3 1 2] var.

52
00:02:37,980 --> 00:02:39,550
İkinci verir the sıralanır array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Belə ki, siz ümumiyyətlə, array vasitəsilə getmək heç vaxt bilmək

54
00:02:43,350 --> 00:02:46,790
n sıra elementlərin sayı yerləşir n-1 dəfə çoxdur.

55
00:02:47,090 --> 00:02:50,470
Ən böyük elementlərin bubble-up 'meyli çünki Bubble Sort deyirlər

56
00:02:50,470 --> 00:02:51,950
olduqca sürətlə sağa.

57
00:02:51,950 --> 00:02:53,980
Əslində, bu alqoritm çox maraqlı davranış var.

58
00:02:53,980 --> 00:02:57,410
>> Bütün array vasitəsilə m tekrarlamalar sonra,

59
00:02:57,410 --> 00:02:59,000
bu rightmost m elementləri təmin edilir

60
00:02:59,000 --> 00:03:01,000
onların düzgün yer ayrılır bilər.

61
00:03:01,000 --> 00:03:02,280
Siz özünüz üçün bu görmək istəyirsinizsə

62
00:03:02,280 --> 00:03:05,500
biz tamamilə geri siyahısı [9, 6, 5, 3, 2] haqqında cəhd edə bilərsiniz.

63
00:03:05,500 --> 00:03:08,220
Bütün siyahısını bir keçid sonra,

64
00:03:08,220 --> 00:03:09,220
[Yazılı səs]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
bu rightmost element 9 onun düzgün yerdədir.

67
00:03:21,250 --> 00:03:24,760
Ötürmə ikinci sonra 6 'bubbled-up' da olacaq

68
00:03:24,760 --> 00:03:26,220
ikinci rightmost yer.

69
00:03:26,220 --> 00:03:28,840
6 və 9 - - hüququ üzrə iki elementləri onların düzgün yerlərdə olacaq

70
00:03:28,840 --> 00:03:30,580
ilk iki pass-throughs sonra.

71
00:03:30,580 --> 00:03:32,590
>> Belə ki, necə biz alqoritm optimize istifadə edə bilərsiniz?

72
00:03:32,590 --> 00:03:34,850
Yaxşı, array vasitəsilə bir iteration sonra

73
00:03:34,850 --> 00:03:37,690
biz əslində rightmost element yoxlamaq lazım deyil

74
00:03:37,690 --> 00:03:39,200
biz bilirik çünki sıralanır edir.

75
00:03:39,200 --> 00:03:43,050
Iki tekrarlamalar sonra biz rightmost iki element mövcuddur əmin bilirik.

76
00:03:43,050 --> 00:03:48,260
Belə ki, ümumiyyətlə, tam array vasitəsilə k tekrarlamalar sonra,

77
00:03:48,260 --> 00:03:51,550
Bildiyimiz ildən keçən k elementləri yoxlanılması lazımsız edir

78
00:03:51,550 --> 00:03:52,360
onlar artıq doğru yerdə istəyirik.

79
00:03:52,360 --> 00:03:54,870
>> Siz n elementlərin bir sıra çeşidlənməsi etdiyiniz əgər,

80
00:03:54,870 --> 00:03:57,870
ilk iteration üzrə - you'll bütün öğeleri sıralama var - ilk n-0.

81
00:03:57,870 --> 00:04:04,170
Ikinci iteration, siz bütün öğeleri lakin son baxmaq lazımdır -

82
00:04:04,170 --> 00:04:07,090
n-1 ilk.

83
00:04:07,090 --> 00:04:10,520
Digər optimallaşdırma siyahısı artıq çeşidlənir yoxlamaq ola bilər

84
00:04:10,520 --> 00:04:11,710
hər iteration sonra.

85
00:04:11,710 --> 00:04:13,900
Artıq sıralaması var, biz bir daha tekrarlamalar etmək lazım deyil

86
00:04:13,900 --> 00:04:15,310
siyahısı ilə.

87
00:04:15,310 --> 00:04:16,220
Biz bunu edə bilər?

88
00:04:16,220 --> 00:04:19,360
Bəli, biz bir siyahısı ötürmə hər hansı mübadiləsi etmək yoxsa,

89
00:04:19,360 --> 00:04:22,350
biz bir şey dəyişdirmək deyil, çünki siyahısını artıq sıralanır ki, aydın deyil.

90
00:04:22,350 --> 00:04:24,160
Belə ki, biz mütləq yenidən sıralama yoxdur.

91
00:04:24,160 --> 00:04:27,960
>> Bəlkə üçün 'sıralanır deyil' adlı bir bayrağı dəyişən başlamaq bilər

92
00:04:27,960 --> 00:04:30,990
siz hər hansı elementləri dəyişdirmək üçün, əgər yalan və doğru dəyişdirmək

93
00:04:30,990 --> 00:04:32,290
serialın vasitəsilə bir iteration.

94
00:04:32,290 --> 00:04:35,350
Və ya eyni, siz neçə svopları saymaq üçün counter etmək

95
00:04:35,350 --> 00:04:37,040
hər hansı iteration haqqında.

96
00:04:37,040 --> 00:04:40,040
Bir iteration sonunda, siz elementləri hər hansı dəyişdirmək olmasaydı,

97
00:04:40,040 --> 00:04:41,780
siz siyahısına artıq çeşidlənir və Bitirdiğinizde bilirik.

98
00:04:41,780 --> 00:04:44,090
Bubble Sort digər çeşidlənməsi alqoritmlərin kimi ola bilər

99
00:04:44,090 --> 00:04:46,960
bir sifariş metodu hər hansı elementləri üçün işləmək tweaked.

100
00:04:46,960 --> 00:04:50,610
>> Bu, demək üçün bir yol var iki elementləri verilmiş, əgər birinci

101
00:04:50,610 --> 00:04:53,770
bərabər və ya ikinci az daha böyükdür.

102
00:04:53,770 --> 00:04:56,870
Məsələn, deyərək əlifbasının hərfləri düzmək bilər

103
00:04:56,870 --> 00:05:00,520
a <b, b <c, s ki,

104
00:05:00,520 --> 00:05:03,830
Bazar ertəsi az olduğu və ya həftə gün sort bilər

105
00:05:03,830 --> 00:05:05,110
olan çərşənbə axşamı azdır.

106
00:05:05,110 --> 00:05:09,630
>> Heç bir çox səmərəli və sürətli çeşidlənməsi alqoritm vasitəsilə Bubble Sort edir.

107
00:05:09,630 --> 00:05:12,370
Onun ən pis halda uzunluğu n Big O ²

108
00:05:12,370 --> 00:05:14,810
bir siyahısını n tekrarlamalar etmək lazımdır, çünki

109
00:05:14,810 --> 00:05:18,430
hər ötürmə bütün n elementləri nəzarət, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Bu axır zaman elementlərinin sayı kimi, artır çeşidlənməsi edirik o deməkdir ki,

111
00:05:22,730 --> 00:05:24,330
run zaman quadratically artırır.

112
00:05:24,330 --> 00:05:27,330
>> Lakin səmərəlilik proqram böyük bir narahatlıq olmadığını

113
00:05:27,330 --> 00:05:29,550
və ya yalnız elementləri kiçik çeşidlənməsi edirsinizsə,

114
00:05:29,550 --> 00:05:31,660
siz Bubble Sort faydalı ola bilər, çünki

115
00:05:31,660 --> 00:05:33,360
bunu anlamaq asan çeşidlənməsi alqoritmlərin biri

116
00:05:33,360 --> 00:05:34,250
və kod üçün.

117
00:05:34,250 --> 00:05:37,270
Bu da nəzəri tərcümə ilə təcrübə almaq üçün bir böyük yol

118
00:05:37,270 --> 00:05:40,220
faktiki fəaliyyət kodu daxil alqoritmi.

119
00:05:40,220 --> 00:05:43,000
Yaxşı, sizin üçün Bubble Sort var. Izləmək üçün təşəkkür edirik.

120
00:05:43,000 --> 00:05:44,000
CS50.TV