[Powered by Google Translate] [اضافے کے ترتیب دیں] [ٹومی MacWilliam] [ہارورڈ یونیورسٹی] [یہ CS50.TV ہے] اندراج کی طرح میں دیکھو، اعداد کی ایک فہرست لے اور انہیں حل کرنے کے لئے ایک الگورتھم ہے. ایک الگورتھم، یاد صرف کام کی تکمیل کے لئے ایک ضابطے کی قدم بہ قدم ہے. اندراج طرح کے پیچھے بنیادی خیال، دو حصے میں اپنی فہرست میں تقسیم ہے، کے مطابق حصہ اور ایک ناچھانٹا ہوا حصہ. 

الگورتھم میں سے ہر ایک قدم پر، ایک بڑی تعداد کو منتقل کر دیا گیا ہے ناچھانٹا ہوا حصہ کے مطابق حصہ آخر میں جب تک مکمل فہرست کے مطابق ہے. 23، 42، 4، 16، 8، اور 15 - یہاں چھ ناچھانٹا ہوا تعداد کی فہرست ہے. چونکہ ان کی تعداد سب صعودی میں نہیں ہیں، وہ ناچھانٹا ہوا رہے ہیں. چونکہ ہم نے شروع ابھی تک حل کرنے نہیں کیا ہے، ہم سب کو چھ عناصر ہماری ناچھانٹا ہوا حصہ پر غور کریں گے. 

ایک بار جب ہم چھانٹ رہا ہے شروع ہو جائیں، ہم ان میں سے بائیں کرنے کے لئے ان کے مطابق نمبر ڈال دیتا ہوں. تو، 23، ہماری فہرست میں پہلے عنصر کے ساتھ شروع. ہم نے ہمارے مطابق حصہ میں کسی بھی عناصر کی ضرورت نہیں ہے ابھی تک، تو صرف 23 ہمارے کے مطابق حصہ کے آغاز اور اختتام کے پر غور کریں. اب، ہمارے مطابق حصہ نمبر ایک، 23 ہے، اور ہمارے ناچھانٹا ہوا حصہ ان پانچ تعداد میں موجود ہیں. چلو اب کے مطابق حصہ میں ہماری ناچھانٹا ہوا حصہ، 42، میں اگلے نمبر داخل کریں. 

ایسا کرنے کے لئے، ہم 23 42 موازنہ کرنے کی ضرورت ہو گی - ہماری مطابق حصہ میں صرف عنصر بہت دور ہے. چالیس دو 23 سے بڑا ہے، تو ہم صرف 42 آخر تک شامل کر سکتے ہیں فہرست کے مطابق حصہ. بہت اچھا ہے! اب ہماری مطابق حصہ دو عناصر ہیں، اور ہمارے ناچھانٹا ہوا حصہ چار عناصر ہیں. تو، اب 4 میں منتقل، ناچھانٹا ہوا حصہ میں اگلے عنصر ہے. تو، جہاں اس کے مطابق حصہ میں رکھا جائے چاہئے؟ 

یاد رکھیں، ہم کے مطابق ترتیب میں اس نمبر پر رکھنے کرنا چاہتے ہیں تاکہ ہمارے کے مطابق حصہ درست طریقے سے ہر وقت کے مطابق رہتا ہے. اگر ہم 42 کے حق میں 4 جگہ ہے، تو ہماری فہرست کے لئے باہر ہو جائے گا. تو، ہماری طرح کے حصہ میں دائیں سے بائیں منتقل کریں. ہم کے طور پر چلتے ہیں، ایک جگہ کے نیچے ہر تعداد میں نیا نمبر کے لئے جگہ بنانے میں منتقل کریں. ٹھیک ہے، بھی 4 سے کم 23 ہے، تو ہم یہ جگہ نہیں یہاں یا تو کر سکتے ہیں. 23 صحیح ایک جگہ منتقل کرنے دو 

اس کا مطلب یہ ہے کہ ہم کے مطابق حصہ میں پہلی سلاٹ میں 4 رکھنا چاہوں گا. نوٹس کس طرح فہرست میں اس جگہ پہلے ہی خالی تھا، کیونکہ ہم کے مطابق عناصر منتقل نیچے کے طور پر ہم ان کا سامنا کرنا پڑا ہے. ٹھیک ہے. لہذا، ہم نے نصف وہاں ہیں. کے مطابق حصہ میں 16 شامل کرتے ہوئے ہماری الگورتھم میں جاری ہے. سولہ کم 42 سے زائد، تو حق پر 42 منتقل. سولہ یہ بھی ہے کہ کم سے کم 23، تو بھی اس عنصر کو منتقل. 

اب، 16 4 سے بڑھ کر ہے. تو، ایسا لگتا ہے جیسے ہم نے 4 اور 23 کے درمیان 16 سے داخل کرنا چاہتے ہیں. جبکہ فہرست کے مطابق حصہ کے ذریعے دائیں سے بائیں منتقل 4 پہلے نمبر ہم نے دیکھا ہے جو تعداد سے کم ہے ہم ڈالنے کی کوشش کر رہے ہیں. تو، اب ہم اس خالی سلاٹ میں 16 داخل کر سکتے ہیں، جو، یاد رکھنا، ہم طرح حصہ میں متحرک عناصر کی طرف سے زائد تشکیل دے دیا ہے کے طور پر ہم ان کا سامنا ہوا ہے. 

ٹھیک ہے. اب، ہم چار کے مطابق عناصر اور دو ناچھانٹا ہوا عناصر ہے. تو، کے مطابق حصہ میں 8 منتقل. آٹھ سے کم 42 ہے. آٹھ 23 سے بھی کم ہے. اور 8 سے کم 16 ہے. لیکن 8 4 سے بڑھ کر ہے. لہذا، ہم نے 4 اور 16 کے درمیان 8 داخل کرنا چاہتے ہیں. 15 - اور اب ہم صرف ایک اور چھوڑ عنصر ترتیب ہے. پندرہ سے کم 42 ہے، پندرہ 23 سے بھی کم ہے. اور 15 سے کم 16 ہے. لیکن 15 8 سے بڑھ کر ہے. 

تو، یہاں وہ جگہ ہے جہاں ہم ہماری آخری اندراج کرنا چاہتے ہیں. اور ہم کیا کر رہے ہیں. ہم ناچھانٹا ہوا حصہ میں نہیں عناصر ہیں، اور ہمارے مطابق حصہ صحیح ترتیب میں ہے. نمبر سے سب سے چھوٹی سب سے بڑا کرنے کا حکم دیا ہے. تو، کچھ pseudocode جو اقدامات ہم صرف کارکردگی کا مظاہرہ کو بیان کرتا ہے ایک نظر ڈالیں. 

سطر 1 پر ہم دیکھتے ہیں، کہ ہم فہرست میں ہر عنصر iterate کی ضرورت ہو گی کر سکتے ہیں پہلے علاوہ ناچھانٹا ہوا حصہ میں پہلی عنصر کے بعد صرف ہو جائے گا کے مطابق حصہ میں پہلی عنصر. 2 لائنوں اور 3 پر، ہم نے ہمارے ناچھانٹا ہوا حصہ میں موجودہ جگہ کے ٹریک رکھ رہے ہیں. عنصر نمبر پر ہم وقت کے مطابق حصہ میں منتقل کر رہے ہیں کی نمائندگی کرتا ہے، اور J ناچھانٹا ہوا حصہ میں ہماری انڈیکس کی نمائندگی کرتا ہے. 

4 آن لائن، ہم دائیں سے بائیں کے مطابق حصہ کے ذریعے iterating کر رہے ہیں. ہم عنصر ایک بار ہماری موجودہ پوزیشن کے بائیں iterating کو روکنے کے لئے چاہتے ہیں عنصر ہم داخل کرنے کی کوشش کر رہے ہیں کے مقابلے میں کم ہے. آن لائن 5، ہم ہر عنصر ہم حق پر ایک خلا کا سامنا منتقل کر رہے ہیں. اس طرح، ہم نے ایک واضح میں داخل کرنے کی جگہ ہے جب ہم پہلی عنصر کو تلاش کریں گے عنصر ہم جا رہے ہیں سے بھی کم ہے. 6 آن لائن، ہم ہمارے انسداد کو اپ ڈیٹ منتقل کے مطابق حصہ کے ذریعے چھوڑ رہے ہیں. آخر میں، 7 لائن پر، کی فہرست کے مطابق حصہ میں ہم عنصر داخل کر رہے ہیں. 

ہم جانتے ہیں کہ یہ پوزیشن J میں شامل کرنے کے لئے ٹھیک ہے، کیونکہ ہم نے پہلے سے ہی عنصر ہے کہ ابھی وہاں ایک خلا کا استعمال کیا منتقل کر دیا گیا ہے. یاد رکھیں، ہم حق سے کے مطابق حصہ کے ذریعے بائیں طرف جا رہے ہیں، لیکن ہم ناچھانٹا ہوا حصہ کے ذریعے بائیں سے دائیں جانب جا رہے ہیں. ٹھیک ہے. چلو، اب کتنی دیر تک چل رہا ہے کہ الگورتھم لیا پر ایک نظر لے. ہم نے سوال سے پہلے کتنی دیر تک اسے لینے کے لئے اس الگورتھم کو بدترین صورت میں چلانے کے لئے پوچھیں گے. کو یاد ہوگا کہ ہم بگ O سنکیتن کے ساتھ اس رننگ ٹائم کی نمائندگی کرتے ہیں. تاکہ ہماری فہرست میں ترتیب کرنے کے لئے، ہم ناچھانٹا ہوا حصہ میں عناصر iterate تھا، اور ان عناصر کے ممکنہ طور پر کے مطابق حصہ میں تمام عناصر ہر کے لئے. Intuitively، O آپریشن (ن ^ 2) کی طرح اس تصوراتی، بہترین. 

کی تلاش میں ہمارے pseudocode میں، ہم نے ایک دوسرے لوپ کے اندر اندر در اندر لوپ ہے، جس میں، یقینا، O آپریشن (ن ^ 2) کی طرح لگتا ہے. تاہم، کی فہرست کے مطابق حصہ بہت آخر تک مکمل فہرست پر مشتمل نہیں تھی. پھر بھی، ہم کے مطابق حصہ کے شروع میں ایک نئے عنصر ممکنہ طور پر داخل کر سکتے ہیں الگورتھم کے ہر iteration جس کا مطلب یہ ہے کہ ہم ہر عنصر کے مطابق حصہ میں اس وقت دیکھنے کی ضرورت ہے. ہے. تو، اس کا مطلب ہے کہ ہم دوسرے عنصر کے لئے ممکنہ طور پر ایک کے مقابلے بنا سکتے ہیں، تیسرا عنصر کے لئے دو موازنہ، وغیرہ. تو، integers کے اقدامات کی کل تعداد 1 سے 1 منفی فہرست کی طوالت رقم ہے. ہم ایک summation کے ساتھ اس کی نمائندگی کر سکتے ہیں. 

ہم summations میں جانا نہیں یہاں گا لیکن یہ پتہ چلا ہے کہ یہ summation کے برابر ہے 2، جو برابر N ^ 2/2 - ن (1 ن) - ن 2 /. asymptotic رن ٹائم کے بارے میں میں بات کر رہے جب اس ن ^ 2 مدت اس ن مدت غلبہ حاصل کرنے کی جا رہی ہے. لہذا، اندراج کی طرح بگ O (ن ^ 2) ہے. کیا اگر ہم ایک نے پہلے ہی کے مطابق فہرست میں اندراج کی طرح بھاگ گیا. اس صورت میں، ہم صرف کے مطابق بائیں سے دائیں حصہ کی تعمیر تھا. لہذا، ہم صرف (ن) کے اقدامات کے حکم پر کی ضرورت ہو گی. 

اس کا مطلب یہ ہے کہ ہے کہ اندراج کی طرح (ن) کی کارکردگی سب سے بہتر صورت ہے، جو ہم Ω (ن) کے ساتھ کی نمائندگی کرتے ہیں. اور یہ کہ اس اندراج کی طرح کے لئے ہے، صرف کئی الگورتھم میں سے ایک ہم ایک فہرست ترتیب کرنے کے لئے استعمال کر سکتے ہیں. میرا نام ٹومی ہے، اور اس CS50 ہے. [CS50.TV] اوہ، تم نہیں روک کر سکتے ہیں کہ ایک بار یہ شروع ہوتا ہے. اوہ، ہم نے یہ کر دکھایا - >> بوم!