1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [সন্নিবেশন সাজান]

2
00:00:02,290 --> 00:00:04,240
[টমি MacWilliam] [হার্ভার্ড বিশ্ববিদ্যালয়]

3
00:00:04,240 --> 00:00:07,290
[এটি CS50.TV]

4
00:00:07,290 --> 00:00:13,060
যাক এর সন্নিবেশ সাজানোর কটাক্ষপাত, সংখ্যার একটি তালিকা গ্রহণ এবং তাদের বাছাই করার জন্য একটি অ্যালগরিদম নিতে.

5
00:00:13,060 --> 00:00:18,300
একটি অ্যালগরিদম,, মনে রাখবেন শুধু একটি টাস্ক accomplishing জন্য ধাপে ধাপে পদ্ধতি.

6
00:00:18,300 --> 00:00:23,640
সন্নিবেশ সাজানোর পিছনে মৌলিক দুটি অংশ মধ্যে আমাদের তালিকা বিভক্ত করা হয়,

7
00:00:23,640 --> 00:00:26,580
একটি সাজানো অংশ এবং একটি পাঁচমিশালী অংশ.

8
00:00:26,580 --> 00:00:29,290
>> আলগোরিদিম প্রতিটি ধাপ অনুযায়ী, একজন নম্বর পাঠানো হয়

9
00:00:29,290 --> 00:00:32,439
থেকে পাঁচমিশালী অংশ যাও অনুসারে বাছাই করা অংশ

10
00:00:32,439 --> 00:00:35,680
অবশেষে পর্যন্ত সম্পূর্ণ তালিকা অনুসারে বাছাই করা হয়.

11
00:00:35,680 --> 00:00:43,340
এখানে ছয় পাঁচমিশালী সংখ্যার তালিকা - 23, 42, 4, 16, 8, এবং 15.

12
00:00:43,340 --> 00:00:47,680
যেহেতু এই সব সংখ্যার মধ্যে না হয় ক্রম আরোহী, তারা পাঁচমিশালী করছি.

13
00:00:47,680 --> 00:00:53,890
যেহেতু আমরা এখনো বাছাই শুরু করেছে না, আমরা আমাদের পাঁচমিশালী অংশ ছয়টি উপাদান বিবেচনা করব.

14
00:00:53,890 --> 00:00:59,270
>> একবার আমরা শুরু বাছাই, আমরা এই সংখ্যা অনুসারে সাজানো এই বাঁদিকে রেখে দেব.

15
00:00:59,270 --> 00:01:03,600
সুতরাং, আসুন 23, আমাদের তালিকায় প্রথম উপাদান দিয়ে শুরু.

16
00:01:03,600 --> 00:01:06,930
আমরা এখনও আমাদের অনুসারে বাছাই করা অংশ কোন উপাদান না,

17
00:01:06,930 --> 00:01:12,460
তাই আসুন সহজভাবে 23 আমাদের অনুসারে বাছাই করা অংশ শুরু এবং শেষের বিবেচনা.

18
00:01:12,460 --> 00:01:16,510
এখন, আমাদের অনুসারে বাছাই করা অংশ এক নম্বর, 23 আছে,

19
00:01:16,510 --> 00:01:20,260
এবং আমাদের পাঁচমিশালী অংশ এই পাঁচটি সংখ্যা আছে.

20
00:01:20,260 --> 00:01:27,320
চলুন এখন আমাদের পাঁচমিশালী অংশ, 42, মধ্যে সাজানো অংশ মধ্যে পরবর্তী সংখ্যা ঢোকান.

21
00:01:27,320 --> 00:01:35,930
>> আমাদের অনুসারে বাছাই করা অংশ একমাত্র উপাদান এতদূর - তাই না, আমরা 23 তে 42 তুলনা করতে হবে.

22
00:01:35,930 --> 00:01:41,980
চল্লিশ দুটি হয় 23 থেকে বড়, তাই আমরা শুধু শেষে 42 সংযুক্ত করতে পারেন

23
00:01:41,980 --> 00:01:45,420
তালিকায় অনুসারে বাছাই করা অংশ. গ্রেট!

24
00:01:45,420 --> 00:01:51,850
এখন আমাদের অনুসারে বাছাই করা অংশ দুটি উপাদান রয়েছে, এবং আমাদের পাঁচমিশালী অংশ চারটি উপাদান রয়েছে.

25
00:01:51,850 --> 00:01:57,200
সুতরাং, এখন এর 4 সরানো যাক, পাঁচমিশালী অংশ পরবর্তী উপাদান.

26
00:01:57,200 --> 00:02:00,230
সুতরাং, যেখানে সাজানো এই অংশে স্থাপন করা উচিত?

27
00:02:00,230 --> 00:02:04,220
>> মনে রাখবেন, আমরা ক্রম অনুসারে সাজানো এই সংখ্যাটি লিখুন চান

28
00:02:04,220 --> 00:02:08,680
তাই আমাদের অনুসারে বাছাই করা অংশ অবশেষ সব সময়ে সঠিকভাবে সাজানো.

29
00:02:08,680 --> 00:02:14,380
যদি আমরা 42 ডানদিকে 4 লিখুন তারপর, আমাদের তালিকা আদেশ করা হবে.

30
00:02:14,380 --> 00:02:18,380
সুতরাং, আসুন আমাদের সাজানোর অংশ যাচ্ছেন ডান বাম অবিরত.

31
00:02:18,380 --> 00:02:23,260
হিসাবে আমরা সরাতে, যাক এর একটি জায়গা নিচে প্রতিটি নম্বরে একটি নতুন নম্বর জন্য জায়গা নামান.

32
00:02:25,440 --> 00:02:31,740
ঠিক আছে, 4 এ কম 23, যাতে আমরা এখানে রাখুন না হয় পারেন.

33
00:02:31,740 --> 00:02:34,480
যাক 23 এর ডান এক জায়গায় সরাতে.

34
00:02:36,500 --> 00:02:43,120
>> তার মানে আমরা অনুসারে বাছাই করা অংশ প্রথম স্লটে মধ্যে 4 দিতে চাই.

35
00:02:43,120 --> 00:02:46,300
কিভাবে এই তালিকায় স্থান ইতিমধ্যে খালি বিজ্ঞপ্তি,

36
00:02:46,300 --> 00:02:51,120
কারণ আমরা করছি সাজানো উপাদান চলন্ত নিচে হিসাবে আমরা তাদের সম্মুখীন হয়েছি.

37
00:02:51,120 --> 00:02:52,740
ঠিক আছে. সুতরাং, আমরা halfway আছে.

38
00:02:52,740 --> 00:02:57,990
চলুন অনুসারে বাছাই করা অংশ মধ্যে 16 ড্রাইভে ঢোকাতে আমাদের এলগরিদম অবিরত.

39
00:02:59,260 --> 00:03:03,820
ষোল কম 42, তাই এর ডান 42 নামান যাক.

40
00:03:05,700 --> 00:03:10,190
ষোল এছাড়াও কম 23, তাই এর যে উপাদান নামান যাক.

41
00:03:11,790 --> 00:03:20,820
>> এখন, 16 4 হয় তার চেয়ে অনেক বেশী. সুতরাং, এটা দেখে মনে হচ্ছে আমরা 4 এবং 23 এর মধ্যে 16 সন্নিবেশ চাই.

42
00:03:20,820 --> 00:03:24,620
তালিকা অনুসারে সাজানো অংশের মাধ্যমে যদিও চলন্ত ডান থেকে বাম যাও,

43
00:03:24,620 --> 00:03:29,160
4 প্রথমের সংখ্যাটি হল আমরা পাচ্ছি যে সংখ্যার চেয়ে কম

44
00:03:29,160 --> 00:03:31,540
আমরা ঢোকানোর চেষ্টা করছেন.

45
00:03:31,540 --> 00:03:35,820
সুতরাং এখন, আমরা এই স্লট ফাঁকা 16 মধ্যে সন্নিবেশ করা যাবে,

46
00:03:35,820 --> 00:03:40,520
যা মনে রাখবেন,, আমরা চলমান উপাদান দ্বারা সাজানোর অংশ সালে নির্মিত উপর করেছি

47
00:03:40,520 --> 00:03:43,340
হিসাবে আমরা তাদের সম্মুখীন হয়েছি.

48
00:03:43,340 --> 00:03:47,900
>> ঠিক আছে. এখন, আমরা চার সাজানো উপাদান এবং দুই পাঁচমিশালী উপাদান আছে.

49
00:03:47,900 --> 00:03:51,600
সুতরাং, আসুন অনুসারে বাছাই করা অংশ মধ্যে 8 সরাতে.

50
00:03:51,600 --> 00:03:55,010
আট কম 42.

51
00:03:55,010 --> 00:03:56,940
আট কম 23.

52
00:03:56,940 --> 00:04:00,230
এবং 8 কম 16.

53
00:04:00,230 --> 00:04:03,110
কিন্তু 8 4 হয় তার চেয়ে অনেক বেশী.

54
00:04:03,110 --> 00:04:07,280
সুতরাং, আমরা 4 এবং 16 এর মধ্যে 8 সন্নিবেশ চাই.

55
00:04:09,070 --> 00:04:13,650
15 - এবং এখন আমরা আরও একটি উপাদান বাছাই যাও বাকি আছে.

56
00:04:13,950 --> 00:04:16,589
পঞ্চদশ কম 42,

57
00:04:16,589 --> 00:04:19,130
পঞ্চদশ কম 23.

58
00:04:19,130 --> 00:04:21,750
এবং 15 কম 16.

59
00:04:21,750 --> 00:04:24,810
কিন্তু 15 8 হয় তার চেয়ে অনেক বেশী.

60
00:04:24,810 --> 00:04:27,440
>> তাই এখানে, যেখানে আমরা আমাদের চূড়ান্ত সন্নিবেশ করতে চাই.

61
00:04:28,770 --> 00:04:30,330
এবং আমরা কাজ সম্পন্ন হয়.

62
00:04:30,330 --> 00:04:33,540
আমরা কোন পাঁচমিশালী অংশে আরো উপাদান আছে,

63
00:04:33,540 --> 00:04:36,670
এবং আমাদের অনুসারে বাছাই করা অংশ সঠিক অনুক্রমে হয়.

64
00:04:36,670 --> 00:04:40,270
সংখ্যা থেকে ক্ষুদ্রতম বৃহত্তম যাও আদেশ হয়.

65
00:04:40,270 --> 00:04:44,330
সুতরাং, আসুন কিছু pseudocode যে পদক্ষেপগুলো আমরা শুধু সঞ্চালিত বর্ণনা কটাক্ষপাত করা.

66
00:04:46,760 --> 00:04:51,740
>> লাইন 1 অন, আমরা যে আমরা তালিকায় পুনরুক্তি করা প্রতিটি উপাদান বেশী প্রয়োজন হবে দেখতে পারেন

67
00:04:51,740 --> 00:04:57,060
পাঁচমিশালী অংশে প্রথম উপাদান থেকে প্রথম ছাড়া সহজভাবে, হয়ে যাবে

68
00:04:57,060 --> 00:05:00,220
অনুসারে বাছাই করা অংশ প্রথম উপাদান.

69
00:05:00,220 --> 00:05:06,320
লাইন 2 এবং 3, আমরা আমাদের পাঁচমিশালী অংশে বর্তমান স্থান সম্পর্কে অবগত করছি পালন.

70
00:05:06,320 --> 00:05:10,450
আমরা উপাদান সংখ্যা অনুসারে সাজানো অংশ বর্তমানে চলন্ত প্রতিনিধিত্ব করে,

71
00:05:10,450 --> 00:05:15,600
এবং ঞ পাঁচমিশালী অংশ মধ্যে আমাদের সূচক প্রতিনিধিত্ব করে.

72
00:05:15,600 --> 00:05:20,980
>> লাইন 4, আমরা ডান থেকে বাম যাও সাজানো অংশের মাধ্যমে iterating করছি.

73
00:05:20,980 --> 00:05:26,010
আমরা আমাদের বর্তমান অবস্থা বাঁদিকে উপাদান একবার iterating থামাতে চান

74
00:05:26,010 --> 00:05:30,050
হল উপাদান আমরা ঢোকানোর চেষ্টা করছেন তুলনায় কম.

75
00:05:30,050 --> 00:05:35,600
লাইন 5 তারিখে, আমরা প্রতিটি উপাদান আমরা ডান এক স্থান সম্মুখীন নাড়াচাড়া করছি.

76
00:05:35,600 --> 00:05:40,950
এই ভাবে, আমরা একটি মধ্যে সন্নিবেশ পরিষ্কার জায়গা আছে আমরা যখন প্রথম উপাদান খুঁজে পাবেন

77
00:05:40,950 --> 00:05:44,080
উপাদান আমরা চলন্ত করছি কম.

78
00:05:44,080 --> 00:05:50,800
লাইন 6 তারিখে, আমরা আমাদের পাল্টা যাও যাও সাজানো অংশের মাধ্যমে বামে সরানো অবিরত আপডেট করছি.

79
00:05:50,800 --> 00:05:56,860
লাইন 7 পরিশেষে, আমরা উপাদান তালিকা অনুসারে বাছাই করা অংশ মধ্যে ঢোকাতে করছি.

80
00:05:56,860 --> 00:06:00,020
>> আমরা জানি যে এর অবস্থান ঞ মধ্যে সন্নিবেশ ঠিক আছে যাও,

81
00:06:00,020 --> 00:06:05,360
কারণ ইতিমধ্যে আমরা উপাদান যে অধিকার আছে এক স্থান ব্যবহার করেছি সরানো.

82
00:06:05,360 --> 00:06:09,460
মনে রাখবেন, আমরা ডান থেকে বাম অংশের মাধ্যমে সাজানো যাও চলন্ত করছি,

83
00:06:09,460 --> 00:06:13,960
কিন্তু আমরা বাম থেকে ডান পাঁচমিশালী অংশের মাধ্যমে চলন্ত করছি.

84
00:06:13,960 --> 00:06:19,090
ঠিক আছে. চলুন এখন কতদিন চলমান যে অ্যালগরিদম গ্রহণ কটাক্ষপাত করা.

85
00:06:19,090 --> 00:06:25,300
আমরা প্রথম প্রশ্ন কতদিন এটা জন্য এই অ্যালগরিদম লক চালানোর নিতে বলব.

86
00:06:25,300 --> 00:06:29,040
পুনরাহ্বান যে আমরা বিগ হে স্বরলিপি সঙ্গে এই চলমান সময় প্রতিনিধিত্বকারী.

87
00:06:32,530 --> 00:06:38,500
আমাদের তালিকা বাছাই, আমরা পাঁচমিশালী অংশ উপাদান পুনরুক্তি করা ছিল,

88
00:06:38,500 --> 00:06:43,430
এবং এর জন্য প্রতিটি সম্ভাব্য সাজানো অংশে সব উপাদানের উপরে যারা উপাদানের,.

89
00:06:43,430 --> 00:06:47,950
Intuitively, একটি হে (ঢ ^ 2) অপারেশন মত এই শব্দ.

90
00:06:47,950 --> 00:06:51,840
>> আমাদের pseudocode সময়ে খুঁজছি, আমরা একটি লুপ অন্য লুপ ভিতরে নেস্টেড আছে,

91
00:06:51,840 --> 00:06:55,290
যা প্রকৃতপক্ষে, একটি হে (ঢ ^ 2) অপারেশন, যেমন শোনাচ্ছে.

92
00:06:55,290 --> 00:07:01,590
যাইহোক, তালিকা অনুসারে সাজানো অংশ খুব শেষ পর্যন্ত সম্পূর্ণ তালিকা ধারন করে না.

93
00:07:01,590 --> 00:07:06,920
এখনো আমরা সম্ভাব্য অনুসারে বাছাই করা অংশ খুব প্রারম্ভে একটি নতুন উপাদান প্রবেশ করাতে পারে

94
00:07:06,920 --> 00:07:09,320
উপর আলগোরিদিম প্রতি পুনরাবৃত্তির,

95
00:07:09,320 --> 00:07:14,500
যার মানে আমরা প্রতিটি উপাদান এ সাজানো অংশে বর্তমানে নজর চাই.

96
00:07:14,500 --> 00:07:20,090
তাই, মানে আমরা সম্ভাব্য দ্বিতীয় উপাদান জন্য এক তুলনা করতে পারে,

97
00:07:20,090 --> 00:07:24,660
তৃতীয় উপাদান জন্য দুটি তুলনা, এবং তাই.

98
00:07:24,660 --> 00:07:32,480
সুতরাং, পদক্ষেপ মোট সংখ্যা পূর্ণসংখ্যার থেকে 1 বিয়োগ তালিকা 1 দৈর্ঘ্যের সমষ্টি.

99
00:07:32,480 --> 00:07:35,240
আমরা একটি সঙ্কলন সঙ্গে এই উপস্থাপন করতে পারেন.

100
00:07:41,170 --> 00:07:47,270
>> আমরা summations ঢোকা এখানে হবে না, কিন্তু এটি সক্রিয় আউট যে এই সঙ্কলন সমান যাও

101
00:07:47,270 --> 00:07:57,900
n (n - 1) 2 উপর, যা সম n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Asymptotic রানটাইম সম্পর্কে যখন কথা বলা,

103
00:08:00,800 --> 00:08:05,170
এই n ^ 2 শব্দ থেকে এই শব্দটি n আয়ত্তে আনা যাচ্ছে না.

104
00:08:05,170 --> 00:08:11,430
সুতরাং, সন্নিবেশ সাজানোর হয় বিগ O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
. যদি আমরা একটি ইতিমধ্যে অনুসারে সাজানো তালিকা সন্নিবেশ সাজানোর দৌড়ে

106
00:08:16,150 --> 00:08:20,960
সেই ক্ষেত্রে, কেবলমাত্র আমরা নির্মাণ বাঁ দিক থেকে ডানদিকে অনুসারে বাছাই করা অংশ আপ চাই.

107
00:08:20,960 --> 00:08:25,050
সুতরাং, আমরা কেবল n ধাপ অনুক্রম করতে হবে.

108
00:08:25,050 --> 00:08:29,740
>> তার মানে যে সন্নিবেশ সাজানোর একটি n শ্রেষ্ঠ ক্ষেত্রে কর্মক্ষমতা রয়েছে,

109
00:08:29,740 --> 00:08:34,130
যা আমরা Ω (ঢ) সঙ্গে চিত্রিত করা.

110
00:08:34,130 --> 00:08:36,190
এবং যে সন্নিবেশ সাজানোর জন্য এটি,

111
00:08:36,190 --> 00:08:40,429
শুধু অনেক আলগোরিদিম একটি তালিকা বাছাই আমরা ব্যবহার করতে পারেন.

112
00:08:40,429 --> 00:08:43,210
আমার নাম টমি, এবং এই CS50.

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

114
00:08:46,110 --> 00:08:49,230
ওহ, আপনি যে একবার এটি আরম্ভ করা থামাতে পারে না.

115
00:09:01,620 --> 00:09:04,760
ওহ, আমরা যে কি - >> পরিস্ফুটন!