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
ایک الگورتھم، یاد صرف کام کی تکمیل کے لئے ایک ضابطے کی قدم بہ قدم ہے.

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
ٹھیک ہے. لہذا، ہم نے نصف وہاں ہیں.

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 پر ہم دیکھتے ہیں، کہ ہم فہرست میں ہر عنصر iterate کی ضرورت ہو گی کر سکتے ہیں

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
اور J ناچھانٹا ہوا حصہ میں ہماری انڈیکس کی نمائندگی کرتا ہے.

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
>> ہم جانتے ہیں کہ یہ پوزیشن J میں شامل کرنے کے لئے ٹھیک ہے،

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
کو یاد ہوگا کہ ہم بگ O سنکیتن کے ساتھ اس رننگ ٹائم کی نمائندگی کرتے ہیں.

87
00:06:32,530 --> 00:06:38,500
تاکہ ہماری فہرست میں ترتیب کرنے کے لئے، ہم ناچھانٹا ہوا حصہ میں عناصر iterate تھا،

88
00:06:38,500 --> 00:06:43,430
اور ان عناصر کے ممکنہ طور پر کے مطابق حصہ میں تمام عناصر ہر کے لئے.

89
00:06:43,430 --> 00:06:47,950
Intuitively، O آپریشن (ن ^ 2) کی طرح اس تصوراتی، بہترین.

90
00:06:47,950 --> 00:06:51,840
>> کی تلاش میں ہمارے pseudocode میں، ہم نے ایک دوسرے لوپ کے اندر اندر در اندر لوپ ہے،

91
00:06:51,840 --> 00:06:55,290
جس میں، یقینا، O آپریشن (ن ^ 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
الگورتھم کے ہر iteration

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
تو، integers کے اقدامات کی کل تعداد 1 سے 1 منفی فہرست کی طوالت رقم ہے.

99
00:07:32,480 --> 00:07:35,240
ہم ایک summation کے ساتھ اس کی نمائندگی کر سکتے ہیں.

100
00:07:41,170 --> 00:07:47,270
>> ہم summations میں جانا نہیں یہاں گا لیکن یہ پتہ چلا ہے کہ یہ summation کے برابر ہے

101
00:07:47,270 --> 00:07:57,900
2، جو برابر N ^ 2/2 - ن (1 ن) - ن 2 /.

102
00:07:57,900 --> 00:08:00,800
asymptotic رن ٹائم کے بارے میں میں بات کر رہے جب

103
00:08:00,800 --> 00:08:05,170
اس ن ^ 2 مدت اس ن مدت غلبہ حاصل کرنے کی جا رہی ہے.

104
00:08:05,170 --> 00:08:11,430
لہذا، اندراج کی طرح بگ O (ن ^ 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
لہذا، ہم صرف (ن) کے اقدامات کے حکم پر کی ضرورت ہو گی.

108
00:08:25,050 --> 00:08:29,740
>> اس کا مطلب یہ ہے کہ ہے کہ اندراج کی طرح (ن) کی کارکردگی سب سے بہتر صورت ہے،

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
اوہ، ہم نے یہ کر دکھایا - >> بوم!