1
00:00:00,000 --> 00:00:03,360
>> [সঙ্গীত বাজাচ্ছি]

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

3
00:00:04,522 --> 00:00:06,730
ডগ লয়েড: ঠিক আছে, তাই
বাবল সাজান একটি অ্যালগরিদম হয়

4
00:00:06,730 --> 00:00:08,730
আপনি উপাদানের একটি সেট সাজাতে ব্যবহার করতে পারেন.

5
00:00:08,730 --> 00:00:10,850
এর কিভাবে এটি কাজ করে কটাক্ষপাত করা যাক.

6
00:00:10,850 --> 00:00:13,240
>> সুতরাং মৌলিক ধারণা পিছনে
বাবল সাজান এই হল.

7
00:00:13,240 --> 00:00:17,340
আমরা সাধারণত উচ্চ স্থানান্তর করতে চান
সাধারণত ডান মূল্যবান উপাদান,

8
00:00:17,340 --> 00:00:20,340
এবং সাধারণত মূল্যবান উপাদান কম
বাম, আমরা আশা করতে পারি.

9
00:00:20,340 --> 00:00:23,256
আমরা কম কিছু হতে চাই
শুরুতে, এবং উচ্চ জিনিষ

10
00:00:23,256 --> 00:00:24,970
শেষে হতে.

11
00:00:24,970 --> 00:00:26,130
>> আমরা এটা কিভাবে করব?

12
00:00:26,130 --> 00:00:28,040
ওয়েল pseudocode কোড,
আমরা আসুন, বলতে পারে

13
00:00:28,040 --> 00:00:30,320
একটি নন-জিরো মান অদল-বদলের কাজটি কাউন্টার সেট.

14
00:00:30,320 --> 00:00:32,570
আমরা একটি দ্বিতীয় যে কেন আমরা দেখতে পাবেন.

15
00:00:32,570 --> 00:00:36,090
এবং তারপর আমরা নিম্নলিখিত পুনরাবৃত্তি
অদল-বদল কাউন্টার 0 হয় না হওয়া পর্যন্ত প্রক্রিয়া,

16
00:00:36,090 --> 00:00:39,910
বা আমরা সব সময়ে কোন অদলবদল করা পর্যন্ত.

17
00:00:39,910 --> 00:00:43,170
>> করতে swap 'কাউন্টার রিসেট
0 এটি ইতিমধ্যেই 0 না হয় তাহলে.

18
00:00:43,170 --> 00:00:46,420
তারপর এ ভাষার চেহারা
উপাদানের সন্নিহিত যুগল.

19
00:00:46,420 --> 00:00:49,550
ঐ দুটি উপাদানের হন
না, যাতে তাদের অদলবদল,

20
00:00:49,550 --> 00:00:51,620
এবং swap 'পাল্টা 1 যোগ করুন.

21
00:00:51,620 --> 00:00:53,870
আপনি সম্পর্কে চিন্তা করছি
এই কমান্ডের সাহায্যে আপনি তা ঠাহর আগে

22
00:00:53,870 --> 00:00:57,471
এই কম সরানো হবে যে লক্ষ্য
বাঁদিকে মূল্যবান উপাদান

23
00:00:57,471 --> 00:01:00,720
এবং উচ্চ, ডান উপাদানের মূল্যবান
কার্যকরভাবে আমরা কি করতে চান করছেন,

24
00:01:00,720 --> 00:01:03,940
যা ঐ গ্রুপ সরানো হয়
যে ভাবে উপাদানের.

25
00:01:03,940 --> 00:01:07,035
এর কিভাবে এই ঠাহর করা যাক
আমাদের অ্যারে ব্যবহার চেহারা হতে পারে

26
00:01:07,035 --> 00:01:10,504
আমরা পরীক্ষা করতে ব্যবহৃত যে
এই আলগোরিদিম আউট.

27
00:01:10,504 --> 00:01:13,420
আমরা আবার এখানে একটি পাঁচমিশালী অ্যারে আছে
উপাদানের সমস্ত দ্বারা নির্দেশিত

28
00:01:13,420 --> 00:01:14,840
লাল হচ্ছে.

29
00:01:14,840 --> 00:01:17,970
আর আমি আমার অদল-বদল কাউন্টার সেট
একটি অশূন্য মান.

30
00:01:17,970 --> 00:01:20,610
আমি ইচ্ছামত বেছে নেওয়া হয়েছে
নেতিবাচক 1 টি এটি 0 না.

31
00:01:20,610 --> 00:01:23,840
আমরা এই প্রক্রিয়া পুনরাবৃত্তি করতে চান
অদল-বদল কাউন্টার পর্যন্ত 0 হয়.

32
00:01:23,840 --> 00:01:26,540
আমি আমার অদল-বদল সেট কেন হয়
কিছু নন-জিরো মান পাল্টা,

33
00:01:26,540 --> 00:01:29,400
কারণ অন্যথায়
অদল-বদল কাউন্টার 0 হবে.

34
00:01:29,400 --> 00:01:31,610
আমরা এমনকি শুরু না
অ্যালগরিদম প্রক্রিয়া.

35
00:01:31,610 --> 00:01:33,610
তাই আবার, ধাপ are--
অদল-বদল কাউন্টার রিসেট

36
00:01:33,610 --> 00:01:37,900
0 যাও, তারপর প্রতি সন্নিহিত তাকান
জুড়ি, এবং তারা যাতে আউট হন,

37
00:01:37,900 --> 00:01:40,514
তাদের অদলবদল, এবং 1 যোগ
অদল-বদল পাল্টা.

38
00:01:40,514 --> 00:01:41,680
তাই আসুন এই প্রক্রিয়া শুরু করা যাক.

39
00:01:41,680 --> 00:01:44,430
তাই আমরা কি প্রথম জিনিস
আমরা 0 থেকে swap 'কাউন্টার সেট

40
00:01:44,430 --> 00:01:46,660
এবং তারপর আমরা খুঁজছি শুরু
প্রতিটি সংলগ্ন জুড়ি.

41
00:01:46,660 --> 00:01:49,140
>> তাই আমরা প্রথম 5 এবং 2 এ খুঁজছেন শুরু.

42
00:01:49,140 --> 00:01:52,410
আমরা তারা বাইরে দেখতে
অর্ডার এবং তাই আমরা তাদের অদলবদল.

43
00:01:52,410 --> 00:01:53,830
আর আমরা swap 'পাল্টা 1 যোগ করুন.

44
00:01:53,830 --> 00:01:57,860
তাই এখন আমাদের অদল-বদলের কাজটি কাউন্টার 1,
এবং 2 এবং 5 জাগ্রত হয়েছে.

45
00:01:57,860 --> 00:01:59,370
এখন আমরা আবার প্রক্রিয়ার পুনরাবৃত্তি.

46
00:01:59,370 --> 00:02:03,540
>> আমরা পরের সন্নিহিত জুড়ি তাকান,
5 এবং তারা যাতে ফুরিয়েছে 1 টি,

47
00:02:03,540 --> 00:02:06,960
তাই আমরা তাদের অদলবদল এবং যোগ
অদল-বদল কাউন্টার থেকে 1.

48
00:02:06,960 --> 00:02:08,900
তারপর আমরা 5 এবং 3 তাকান.

49
00:02:08,900 --> 00:02:13,830
তারা যাতে সীমার বাইরে, তাই আমরা অদলবদল
তাদের এবং আমরা swap 'পাল্টা 1 যোগ করুন.

50
00:02:13,830 --> 00:02:15,550
তারপর আমরা 5 এবং 6 তাকান.

51
00:02:15,550 --> 00:02:18,630
তারা যাতে করছি, যাতে আমরা আসলে না
কিছু এই সময় অদলবদল করতে হবে.

52
00:02:18,630 --> 00:02:20,250
তারপর আমরা 6 এবং 4 তাকান.

53
00:02:20,250 --> 00:02:24,920
তারা যাতে বাইরে এসেছি, তাই আমরা অদলবদল
তাদের এবং আমরা swap 'পাল্টা 1 যোগ করুন.

54
00:02:24,920 --> 00:02:26,230
>> এখন ঘটেছে কি লক্ষ্য.

55
00:02:26,230 --> 00:02:29,514
আমরা শেষ পর্যন্ত 6 সব পথ ফেলে এসেছি.

56
00:02:29,514 --> 00:02:32,180
নির্বাচন সাজানোর মধ্যে সুতরাং, আপনি করেছি তাহলে
যে ভিডিও দেখা, কি আমরা করেছিলাম

57
00:02:32,180 --> 00:02:35,290
আমরা চলন্ত শেষ পর্যন্ত
দালান ক্ষুদ্রতম উপাদান

58
00:02:35,290 --> 00:02:39,640
থেকে মূলত সাজানো অ্যারের
বৃহত্তম, ক্ষুদ্রতম ডানে বামে.

59
00:02:39,640 --> 00:02:43,200
বাবল সাজানোর ক্ষেত্রে আমরা হন তাহলে
এই বিশেষ অ্যালগরিদম অনুসরণ,

60
00:02:43,200 --> 00:02:46,720
আমরা আসলে নির্মাণের হতে যাচ্ছেন
ডান থেকে সাজানো অ্যারের

61
00:02:46,720 --> 00:02:49,100
ক্ষুদ্রতম থেকে বৃহত্তম বাম.

62
00:02:49,100 --> 00:02:53,840
আমরা কার্যকরভাবে 6, bubbled আছে
বৃহত্তম মান, শেষ সব পথ.

63
00:02:53,840 --> 00:02:56,165
>> তাই আমরা এখন ঘোষণা করতে পারেন
যে সাজানো হয় যে,

64
00:02:56,165 --> 00:02:59,130
এবং ভবিষ্যতে iterations--
অ্যারের মধ্যে দিয়ে যাচ্ছিলেন again--

65
00:02:59,130 --> 00:03:01,280
আমরা আর 6 বিবেচনা করতে হবে না.

66
00:03:01,280 --> 00:03:03,850
আমরা শুধুমাত্র বিবেচনা আছে
পাঁচমিশালী উপাদান

67
00:03:03,850 --> 00:03:06,299
যখন আমরা সংলগ্ন জোড়া এ খুঁজছেন.

68
00:03:06,299 --> 00:03:08,340
সুতরাং আমরা একটি সমাপ্ত হয়েছে
বাবল সাজান মাধ্যমে পাস.

69
00:03:08,340 --> 00:03:11,941
তাই এখন আমরা প্রশ্ন ফিরে যান,
অদল-বদল কাউন্টার 0 হয় না হওয়া পর্যন্ত পুনরাবৃত্তি.

70
00:03:11,941 --> 00:03:13,690
ওয়েল অদল-বদলের কাজটি কাউন্টার
4 হয়, তাই আমরা চলুন

71
00:03:13,690 --> 00:03:15,410
আবার এই প্রক্রিয়া পুনরায় রাখা.

72
00:03:15,410 --> 00:03:19,180
>> আমরা swap 'কাউন্টার রিসেট করতে যাচ্ছেন
0 যাও, এবং প্রতিটি সংলগ্ন জুড়ি তাকান.

73
00:03:19,180 --> 00:03:21,890
তাই আমরা তারা 1 টি 2 দিয়ে শুরু এবং
যাতে বাইরে, তাই আমরা তাদের অদলবদল

74
00:03:21,890 --> 00:03:23,620
এবং আমরা swap 'পাল্টা 1 যোগ করুন.

75
00:03:23,620 --> 00:03:25,490
2 এবং 3, তারা যাতে করছি.

76
00:03:25,490 --> 00:03:27,060
আমরা কিছু করতে হবে না.

77
00:03:27,060 --> 00:03:28,420
3 ও 5 আদেশ হয়.

78
00:03:28,420 --> 00:03:30,150
আমরা সেখানে কিছু করতে হবে না.

79
00:03:30,150 --> 00:03:32,515
>> 5 এবং 4, তারা বাইরে
আদেশের, এবং তাই আমরা

80
00:03:32,515 --> 00:03:35,130
তাদের অদলবদল এবং যুক্ত করতে হবে
অদল-বদল কাউন্টার থেকে 1.

81
00:03:35,130 --> 00:03:38,880
আর এখন আমরা 5 সরিয়েছেন
পরবর্তী বৃহত্তম উপাদান,

82
00:03:38,880 --> 00:03:40,920
পাঁচমিশালী অংশ শেষে.

83
00:03:40,920 --> 00:03:44,360
সুতরাং আমরা এখন যে কল করতে পারেন
সাজানো অংশ অংশ.

84
00:03:44,360 --> 00:03:47,180
>> এখন আপনি এ খুঁজছেন
পর্দা এবং সম্ভবত আপনি বলতে পারেন,

85
00:03:47,180 --> 00:03:50,130
আমি যা করতে পারেন অ্যারের যে
এই মুহূর্তে সাজানো হয়.

86
00:03:50,130 --> 00:03:51,820
কিন্তু আমরা এখনও যে প্রমাণ করতে পারবে না.

87
00:03:51,820 --> 00:03:54,359
আমরা গ্যারান্টি আছে না
যে এটা সাজানো.

88
00:03:54,359 --> 00:03:56,900
কিন্তু এই যেখানে অদলবদল হয়
কাউন্টার করে আসা যাচ্ছে.

89
00:03:56,900 --> 00:03:59,060
>> সুতরাং আমরা একটি পাস সম্পন্ন করেছেন.

90
00:03:59,060 --> 00:04:00,357
অদল-বদল কাউন্টার 2 হয়.

91
00:04:00,357 --> 00:04:02,190
সুতরাং আমরা পুনরাবৃত্তি করতে যাচ্ছেন
আবার এই প্রক্রিয়া,

92
00:04:02,190 --> 00:04:04,290
অদল-বদল কাউন্টার 0 হয় না হওয়া পর্যন্ত পুনরাবৃত্তি.

93
00:04:04,290 --> 00:04:05,550
0 থেকে swap 'কাউন্টার রিসেট করুন.

94
00:04:05,550 --> 00:04:06,820
তাই আমরা এটি পুনরায় সেট করব.

95
00:04:06,820 --> 00:04:09,810
>> এখন প্রতিটি সংলগ্ন জুড়ি তাকান.

96
00:04:09,810 --> 00:04:11,880
যে, যাতে 1 এবং 2 এর.

97
00:04:11,880 --> 00:04:13,590
2 এবং 3 আদেশ হয়.

98
00:04:13,590 --> 00:04:15,010
3 ও 4, যাতে আছে.

99
00:04:15,010 --> 00:04:19,250
সুতরাং এই সময়ে, আমরা সম্পন্ন করেছি বিজ্ঞপ্তি
প্রতি সন্নিহিত একজোড়া এ খুঁজছেন,

100
00:04:19,250 --> 00:04:22,530
কিন্তু অদল-বদলের কাজটি কাউন্টার এখনও 0 হয়.

101
00:04:22,530 --> 00:04:25,520
>> আমরা সুইচ না থাকে
কোন উপাদান, তারপর তারা

102
00:04:25,520 --> 00:04:28,340
দ্বারা ক্রম হবে
এই প্রক্রিয়ার পুণ্য.

103
00:04:28,340 --> 00:04:32,000
আর তাই প্রকারের একটি দক্ষতা,
যে আমরা কম্পিউটার বিজ্ঞানীরা ভালবাসেন,

104
00:04:32,000 --> 00:04:35,560
আমরা এখন ঘোষণা করতে পারেন হয়
সম্পূর্ণ অ্যারে অবশ্যই

105
00:04:35,560 --> 00:04:38,160
আমরা না, কারণ, সাজানো করা
কোন উপাদান বিনিময় করা আছে.

106
00:04:38,160 --> 00:04:40,380
যে বেশ চমৎকার.

107
00:04:40,380 --> 00:04:43,260
>> তাই কি খারাপ কেস
বাবল সাজান সঙ্গে পরিস্থিতি?

108
00:04:43,260 --> 00:04:46,240
এতকিছুর পরও যদি আপনি অ্যারে
সম্পূর্ণ বিপরীত ক্রম,

109
00:04:46,240 --> 00:04:49,870
এবং তাই আমরা প্রতিটি বুদ্বুদ আছে
বড় উপাদান সব

110
00:04:49,870 --> 00:04:51,780
অ্যারে জুড়ে উপায়.

111
00:04:51,780 --> 00:04:55,350
আর আমরা কার্যকরভাবে এছাড়াও আছে
বাবল ছোট উপাদানের সব ফিরে

112
00:04:55,350 --> 00:04:57,050
খুব অ্যারে জুড়ে সব পথ.

113
00:04:57,050 --> 00:05:01,950
তাই এন উপাদানের প্রতিটি সরানো হয়েছে
অন্যান্য n উপাদানের সমস্ত জুড়ে.

114
00:05:01,950 --> 00:05:04,102
সুতরাং যে লক দৃশ্যকল্প এর.

115
00:05:04,102 --> 00:05:05,810
ভাল যদি
দৃশ্যকল্প যদিও, এই হল

116
00:05:05,810 --> 00:05:07,880
নির্বাচন সাজানোর থেকে কিছুটা ভিন্ন.

117
00:05:07,880 --> 00:05:10,040
অ্যারে ইতিমধ্যে
আমরা যেতে যখন সাজানো.

118
00:05:10,040 --> 00:05:12,550
আমরা কোনো না করতে হবে না
প্রথম পাস উপর অদলবদল.

119
00:05:12,550 --> 00:05:14,940
সুতরাং আমরা পর্যবেক্ষণ থাকতে পারে
কম উপাদান এ, ডান?

120
00:05:14,940 --> 00:05:18,580
আমরা এই পুনরাবৃত্তি করতে হবে না
ওভার বার নম্বর প্রক্রিয়া.

121
00:05:18,580 --> 00:05:19,540
>> সুতরাং যে কি মানে?

122
00:05:19,540 --> 00:05:22,390
তাই কি লক দৃশ্যকল্প এর
বুদ্বুদ সাজানোর জন্য, এবং কি

123
00:05:22,390 --> 00:05:25,330
বুদ্বুদ সাজানোর জন্য সেরা ক্ষেত্রে দৃশ্যকল্প?

124
00:05:25,330 --> 00:05:27,770
আপনি এই অনুমান করেছেন?

125
00:05:27,770 --> 00:05:32,420
খারাপ যদি আপনি বারবার আছে
সব n উপাদান এন বার জুড়ে.

126
00:05:32,420 --> 00:05:34,220
তাই সবচেয়ে খারাপ ক্ষেত্রে n ছক.

127
00:05:34,220 --> 00:05:36,550
>> অ্যারে পুরোপুরি হয় তাহলে
সাজানো যদিও, আপনি শুধুমাত্র

128
00:05:36,550 --> 00:05:38,580
প্রতিটি তাকান আছে
একবার উপাদানের.

129
00:05:38,580 --> 00:05:42,670
এবং swap 'কাউন্টার এখনও 0 হয়,
আপনি এই অ্যারে সাজানো হয় বলতে পারেন.

130
00:05:42,670 --> 00:05:45,780
তাই সবচেয়ে ভালো ক্ষেত্রে, এই হল
নির্বাচন বেশী আসলে ভালো

131
00:05:45,780 --> 00:05:49,230
sort-- এটি এন এর Omega.

132
00:05:49,230 --> 00:05:50,270
>> আমি ডগ লয়েড আছি.

133
00:05:50,270 --> 00:05:52,140
এটি CS50.

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