1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Bubble დასალაგებლად]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP ჰარვარდის უნივერსიტეტი]

3
00:00:04,560 --> 00:00:07,500
[ეს არის CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble დალაგების არის მაგალითი დახარისხება ალგორითმი -

5
00:00:11,730 --> 00:00:14,460
რომ არის, პროცედურა დახარისხება კომპლექტი ელემენტების

6
00:00:14,460 --> 00:00:15,840
აღმავალი ან დაღმავალი შეკვეთ.

7
00:00:15,840 --> 00:00:18,710
მაგალითად, თუ თქვენ სურდა დასალაგებლად მასივი შემდგარი ნომრები

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], სწორი განხორციელება Bubble დალაგების დაბრუნდნენ

9
00:00:23,060 --> 00:00:26,260
დახარისხებული array [2, 3, 5, 9] აღმავალი შეკვეთა.

10
00:00:26,260 --> 00:00:28,850
ახლა, მე ვაპირებ ახსნას წელს pseudocode როგორ ალგორითმი მუშაობს.

11
00:00:28,850 --> 00:00:34,000
>> ვთქვათ ჩვენ დახარისხება სიაში 5 რიცხვებით - 3, 2, 9, 6, და 5.

12
00:00:34,000 --> 00:00:37,650
ალგორითმი იწყებს მიერ ეძებს პირველი ორი ელემენტები, 3 და 2,

13
00:00:37,650 --> 00:00:40,850
და შემოწმების თუ ისინი მწყობრიდან ნათესავი ერთმანეთს.

14
00:00:40,850 --> 00:00:43,150
ისინი - 3 მეტია 2.

15
00:00:43,150 --> 00:00:45,190
უნდა იყოს აღმავალი შეკვეთა, ისინი უნდა იყოს პირიქით.

16
00:00:45,190 --> 00:00:46,610
ასე რომ, ჩვენ სვოპ მათ.

17
00:00:46,610 --> 00:00:49,760
ახლა სია ასე გამოიყურება: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> შემდეგი, ჩვენ შევხედოთ მეორე და მესამე ელემენტები, 3 და 9.

19
00:00:52,450 --> 00:00:55,770
ისინი ს სწორი მიმდევრობით ნათესავი ერთმანეთს.

20
00:00:55,770 --> 00:00:58,800
ანუ, 3 ნაკლებია, ვიდრე 9 ასე ალგორითმი არ სვოპ მათ.

21
00:00:58,800 --> 00:01:01,900
შემდეგი, ჩვენ შევხედოთ 9 და 6. ისინი მწყობრიდან გამოვიდა.

22
00:01:01,900 --> 00:01:04,260
>> ამიტომ, ჩვენ უნდა სვოპ მათ, რადგან 9 მეტია 6.

23
00:01:04,260 --> 00:01:08,840
და ბოლოს, ჩვენ შევხედოთ ბოლო ორი რიცხვებით, 9 და 5.

24
00:01:08,840 --> 00:01:10,850
ისინი მწყობრიდან გამოვიდა, ასე რომ მათ უნდა swapped.

25
00:01:10,850 --> 00:01:13,360
შემდეგ პირველი სრულ გადის სია,

26
00:01:13,360 --> 00:01:17,140
იგი ასე გამოიყურება: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
ნორმალური. თითქმის დახარისხებული.

28
00:01:19,690 --> 00:01:22,450
მაგრამ ჩვენ გვჭირდება აწარმოებს მეშვეობით სიაში კვლავ მიიღოს იგი მთლიანად დახარისხებული.

29
00:01:22,450 --> 00:01:29,250
ორი ნაკლებია, ვიდრე 3, ასე რომ ჩვენ არ სვოპ მათ.

30
00:01:29,250 --> 00:01:31,700
>> სამი ნაკლებია, ვიდრე 6, ამიტომ ჩვენ არ სვოპ მათ.

31
00:01:31,700 --> 00:01:35,500
ექვსი მეტია 5. ჩვენ swapped.

32
00:01:35,500 --> 00:01:38,460
ექვსი ნაკლებია, ვიდრე 9. ჩვენ არ სვოპ.

33
00:01:38,460 --> 00:01:42,170
შემდეგ მეორე გადის, ის ასე გამოიყურება: [2, 3, 5, 6, 9]. Perfect.

34
00:01:42,170 --> 00:01:44,680
ახლა, მოდით, დაწერეთ ის pseudocode.

35
00:01:44,680 --> 00:01:48,450
ძირითადად, თითოეული ელემენტი სია, ჩვენ უნდა შევხედოთ ამას

36
00:01:48,450 --> 00:01:50,060
და ელემენტს პირდაპირ თავისი უფლება.

37
00:01:50,060 --> 00:01:53,420
თუ ისინი მწყობრიდან ნათესავი ერთმანეთს - ეს არის, თუ ელემენტს მარცხენა

38
00:01:53,420 --> 00:01:56,810
მეტია ერთი მარჯვენა - ჩვენ უნდა სვოპ ორი ელემენტები.

39
00:01:56,810 --> 00:02:01,270
>> ჩვენ ამას ვაკეთებთ, ყოველ ელემენტს სია, და ჩვენ კიდევ ერთი გადის.

40
00:02:01,270 --> 00:02:05,160
ახლა ჩვენ უბრალოდ უნდა გავაკეთოთ უღელტეხილზე გზით საკმარისი ჯერ რათა უზრუნველყოს სია

41
00:02:05,160 --> 00:02:06,480
სრულად, ჯეროვნად დახარისხებული.

42
00:02:06,480 --> 00:02:08,889
მაგრამ რამდენჯერ გვაქვს შემოვლითი გზით სია

43
00:02:08,889 --> 00:02:10,400
გარანტიას, რომ ჩვენ გავაკეთეთ?

44
00:02:10,400 --> 00:02:14,730
ისე, უარესი სცენარით არის თუ გვაქვს სრულიად უკან სიაში.

45
00:02:14,730 --> 00:02:17,840
მაშინ სჭირდება ხმების გაივლის-throughs ტოლი რაოდენობის

46
00:02:17,840 --> 00:02:19,730
ელემენტების N-1.

47
00:02:19,730 --> 00:02:24,720
თუ ეს არ აქვს აზრი ინტუიციურად, ვფიქრობ მარტივი შემთხვევაში - სია [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> ეს აპირებს მიიღოს ერთი უღელტეხილის გზით დასალაგებლად სწორად.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - უარეს შემთხვევაში არის, რომ 3 ელემენტები დალაგებულია უკან,

50
00:02:33,060 --> 00:02:34,830
ის აპირებს 2 iterations დასალაგებლად.

51
00:02:34,830 --> 00:02:37,980
შემდეგ ერთი iteration, ეს [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
მეორე შემოსავალი დახარისხებული array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
ასე რომ თქვენ იცით, თქვენ არასოდეს არ გავლა მასივი, ზოგადად,

54
00:02:43,350 --> 00:02:46,790
ზე მეტი N-1 ჯერ, სადაც n რაოდენობის ელემენტების მასივი.

55
00:02:47,090 --> 00:02:50,470
ეს მოუწოდა Bubble დალაგების რადგან უმსხვილესი ელემენტები ტენდენცია 'ბუშტი-up'

56
00:02:50,470 --> 00:02:51,950
მარჯვნივ საკმაოდ სწრაფად.

57
00:02:51,950 --> 00:02:53,980
ფაქტობრივად, ეს ალგორითმი აქვს ძალიან საინტერესო ქცევა.

58
00:02:53,980 --> 00:02:57,410
>> შემდეგ მ iterations მთელი მასივი,

59
00:02:57,410 --> 00:02:59,000
rightmost m ელემენტები გარანტირებული

60
00:02:59,000 --> 00:03:01,000
უნდა იყოს დახარისხებული მათ სწორი ადგილი.

61
00:03:01,000 --> 00:03:02,280
თუ გვინდა, რომ ამ თავს,

62
00:03:02,280 --> 00:03:05,500
ჩვენ შეგვიძლია ვცდილობთ იგი მთლიანად უკან სიაში [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
შემდეგ ერთი გადის მთელი სია,

64
00:03:08,220 --> 00:03:09,220
[ხმა წერის]

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
rightmost ელემენტს 9 მის სათანადო ადგილი.

67
00:03:21,250 --> 00:03:24,760
შემდეგ მეორედ შემოჭრის გზით, 6 ექნება "bubbled-up 'to

68
00:03:24,760 --> 00:03:26,220
მეორე rightmost ადგილი.

69
00:03:26,220 --> 00:03:28,840
ორი ელემენტები, მარჯვნივ - 6 და 9 - იქნება მათი სწორი ადგილებში

70
00:03:28,840 --> 00:03:30,580
შემდეგ პირველ ორ უღელტეხილზე-throughs.

71
00:03:30,580 --> 00:03:32,590
>> ასე რომ, როგორ შეგვიძლია გამოვიყენოთ ეს ოპტიმიზაციის ალგორითმი?

72
00:03:32,590 --> 00:03:34,850
ისე, ერთი iteration მეშვეობით მასივი

73
00:03:34,850 --> 00:03:37,690
ჩვენ არ რეალურად უნდა შეამოწმოთ rightmost ელემენტს

74
00:03:37,690 --> 00:03:39,200
რადგან ჩვენ ვიცით, ეს დახარისხებული.

75
00:03:39,200 --> 00:03:43,050
შემდეგ ორი iterations, ჩვენ ვიცით, rightmost ორი ელემენტია ადგილზე.

76
00:03:43,050 --> 00:03:48,260
ასე რომ, ზოგადად, შემდეგ K iterations მეშვეობით სრული მასივი,

77
00:03:48,260 --> 00:03:51,550
შემოწმების ბოლო K ელემენტები არის გადაჭარბებული, რადგან ჩვენ ვიცით,

78
00:03:51,550 --> 00:03:52,360
ისინი სწორი საიდან უკვე.

79
00:03:52,360 --> 00:03:54,870
>> ასე რომ, თუ თქვენ დახარისხება მასივი N ელემენტები,

80
00:03:54,870 --> 00:03:57,870
პირველ iteration - you'll უნდა დასალაგებლად ყველა ელემენტი - პირველ N-0.

81
00:03:57,870 --> 00:04:04,170
მეორე iteration, თქვენ უნდა შევხედოთ ყველა ელემენტები, მაგრამ ბოლო -

82
00:04:04,170 --> 00:04:07,090
პირველი n-1.

83
00:04:07,090 --> 00:04:10,520
კიდევ ერთი ოპტიმიზაცია შეიძლება იყოს, რათა შეამოწმოთ, თუ სიაში უკვე დახარისხებული

84
00:04:10,520 --> 00:04:11,710
ყოველი iteration.

85
00:04:11,710 --> 00:04:13,900
თუ ეს უკვე დახარისხებული, ჩვენ არ გვჭირდება რაიმე უფრო iterations

86
00:04:13,900 --> 00:04:15,310
მეშვეობით სიაში.

87
00:04:15,310 --> 00:04:16,220
როგორ შეგვიძლია ამის გაკეთება?

88
00:04:16,220 --> 00:04:19,360
ისე, თუ ჩვენ არ მიიღოს ნებისმიერი სვოპების on უღელტეხილზე გზით სიის,

89
00:04:19,360 --> 00:04:22,350
ნათელია, რომ სიაში უკვე დახარისხებული რადგან ჩვენ ვერ სვოპ არაფერი.

90
00:04:22,350 --> 00:04:24,160
ამიტომ, ჩვენ ნამდვილად არ უნდა დასალაგებლად ერთხელ.

91
00:04:24,160 --> 00:04:27,960
>> ალბათ თქვენ ვერ ვრთავ დროშა ცვლადში "არ დახარისხებული 'to

92
00:04:27,960 --> 00:04:30,990
ცრუ და შეცვალოს იგი ჭეშმარიტია თუ თქვენ უნდა სვოპ ნებისმიერი ელემენტების

93
00:04:30,990 --> 00:04:32,290
ერთი iteration მეშვეობით მასივი.

94
00:04:32,290 --> 00:04:35,350
ან მსგავსი, მიიღოს counter დათვლა რამდენი სვოპების თქვენ გააკეთებთ

95
00:04:35,350 --> 00:04:37,040
ნებისმიერ მოცემულ iteration.

96
00:04:37,040 --> 00:04:40,040
დასასრულს iteration, თუ თქვენ არ სვოპ ნებისმიერი ელემენტები,

97
00:04:40,040 --> 00:04:41,780
თქვენ იცით სიაში უკვე დახარისხებული და თქვენ კეთდება.

98
00:04:41,780 --> 00:04:44,090
Bubble დალაგების, ისევე როგორც სხვა დახარისხება ალგორითმები, შეიძლება იყოს

99
00:04:44,090 --> 00:04:46,960
tweaked მუშაობა ნებისმიერი ელემენტი, რომლებსაც აქვთ შეკვეთით მეთოდი.

100
00:04:46,960 --> 00:04:50,610
>> ანუ, მოცემული ორი ელემენტები გაქვთ გზა ვთქვა, თუ პირველი

101
00:04:50,610 --> 00:04:53,770
მეტია, ტოლი ან ნაკლები მეორე.

102
00:04:53,770 --> 00:04:56,870
მაგალითად, თქვენ შეიძლება დასალაგებლად წერილები ანბანი განაცხადა

103
00:04:56,870 --> 00:05:00,520
რომ <ბ, ბ <გ და ა.შ.

104
00:05:00,520 --> 00:05:03,830
ან შეგიძლიათ დაალაგოთ დღეებში კვირაში, სადაც კვირა ნაკლებია, ვიდრე ორშაბათი

105
00:05:03,830 --> 00:05:05,110
ნაკლებია სამშაბათი.

106
00:05:05,110 --> 00:05:09,630
>> Bubble დალაგების არის არ ნიშნავს ძალიან ეფექტური ან სწრაფი დახარისხება ალგორითმი.

107
00:05:09,630 --> 00:05:12,370
მისი უარესი Runtime არის დიდი O of n ²

108
00:05:12,370 --> 00:05:14,810
იმიტომ, რომ თქვენ უნდა გააკეთოთ N iterations მეშვეობით სია

109
00:05:14,810 --> 00:05:18,430
შემოწმების ყველა N ელემენტების ყოველ უღელტეხილზე გზით, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
ეს გაუშვათ დროის იმას ნიშნავს, რომ, როგორც რაოდენობის ელემენტები თქვენ დახარისხება იზრდება,

111
00:05:22,730 --> 00:05:24,330
პერსპექტივაში დრო იზრდება quadratically.

112
00:05:24,330 --> 00:05:27,330
>> მაგრამ თუ ეფექტურობის არ არის შეშფოთების მთავარ საგანს წარმოადგენს თქვენი პროგრამა

113
00:05:27,330 --> 00:05:29,550
ან თუ თქვენ მხოლოდ დახარისხება მცირე რაოდენობის ელემენტები,

114
00:05:29,550 --> 00:05:31,660
თქვენ შეიძლება Bubble დალაგების სასარგებლო რადგან

115
00:05:31,660 --> 00:05:33,360
ეს არის ერთ ერთი უმარტივესი დახარისხება ალგორითმები უნდა გვესმოდეს

116
00:05:33,360 --> 00:05:34,250
და კოდი.

117
00:05:34,250 --> 00:05:37,270
ასევე დიდი გზა მიიღოს გამოცდილება თარგმნის თეორიული

118
00:05:37,270 --> 00:05:40,220
ალგორითმი შევიდა ფაქტობრივი ფუნქციონირების კოდი.

119
00:05:40,220 --> 00:05:43,000
ისე, რომ Bubble დალაგების თქვენთვის. მადლობა თვალს.

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