>> [موسیقی بجانے]
>> ڈوگ لایڈ تو اندراج کی طرح ایک اور مثال ہے الگورتھم ہم ایک صف ترتیب کرنے کے لئے استعمال کر سکتے ہیں.
اس الگورتھم کے پیچھے خیال آپ کے مطابق صف تعمیر کے لئے ہے
جگہ میں، سے باہر عناصر منتقل تم جا کے طور طریقہ، کمرے بنانے کے لئے.
یہ تھوڑا سا مختلف ہے انتخاب طرح یا بلبلا سے
قسم، مثال کے طور پر، جہاں ہم مقامات ایڈجسٹ کر رہے ہیں،
ہم کہاں سویپ کر رہے ہیں.
>> اس صورت میں کیا ہم اصل میں ہیں کر سلائڈنگ عناصر ہے
زیادہ، راستے سے باہر.
اس الگورتھم کیسے pseudocode میں کام کرتے ہیں؟
ویسے صرف منمانے کا کہنا ہے کہ چلو صف کے پہلے عنصر کے مطابق ہے.
ہم اس جگہ میں تعمیر کر رہے ہیں.
>> ہم ایک وقت میں ایک عنصر جانے رہے ہیں اور اس کی تعمیر، اور تو سب سے پہلی چیز ہم دیکھیں
ایک عنصر صف ہے.
اور تعریف کی طرف سے، ایک عنصر سرنی کے مطابق ہے.
>> پھر ہم اس عمل کو دہرائیں گے until-- ہم نے مندرجہ ذیل عمل کو دہرائیں گے
عناصر کے تمام حل کر رہے ہیں جب تک.
اگلے ناچھانٹا ہوا عنصر دیکھو اور مطابق حصہ میں داخل،
مطلوبہ تعداد منتقل کی طرف سے راستے سے باہر عناصر کی.
امید ہے کہ اس تصور تم بالکل وہی جو دیکھنے میں مدد ملے گی
اندراج کی طرح کے ساتھ چل رہا.
>> تو ایک بار پھر، ہمارے یہاں ہے پورے ناچھانٹا ہوا سرنی،
عناصر کے تمام سرخ رنگ میں اشارہ.
اور کی پیروی کرتے ہیں ہمارے pseudocode کے اقدامات.
ہم کرتے ہیں سب سے پہلی چیز، ہم کہتے ہے صف کے پہلے عنصر، حل.
تو ہم صرف کا کہنا ہے کہ ہو جا پانچ، اب آپ کے مطابق کر رہے ہیں.
>> اس کے بعد ہم اگلے دیکھو صف کے ناچھانٹا ہوا عنصر
اور ہم اس داخل کرنا چاہتے ہیں مطابق حصہ میں،
عناصر پر منتقل کی طرف سے.
تو دو اگلے ناچھانٹا ہوا ہے صف کے عنصر.
واضح طور پر اس سے پہلے تعلق رکھتا ہے پانچ، تو ہم والا کیا ہو
قسم کی ایک دوسرے کے لئے ایک طرف دو منعقد کیا جاتا ہے، پانچ منتقل، اور پھر دو داخل
پانچ سے پہلے، کہاں جانا چاہئے.
اور اب ہم دونوں کے مطابق ہے کہ کہہ سکتے ہیں.
>> آپ دیکھ سکتے ہیں کے طور پر تو، ہم نے اب تک صرف ہے صف کے دو عناصر پر دیکھا.
ہم نے دیکھا نہیں ہے بالکل آرام، لیکن ہم نے
ان دو عناصر کی طرف سے حل کر لی منتقلی کے طریقہ کار کی راہ.
>> تو ہم پھر عمل کو دہرائیں.
اگلے ناچھانٹا ہوا دیکھو عنصر، کہ ایک ہے.
، ایک دوسرے کے لئے ایک طرف پکڑ ہر چیز منتقل، اور ایک ڈال
یہ کہاں جانا چاہئے.
>> ایک بار پھر، اب بھی، ہم صرف کبھی ہے ایک، دو، اور پانچ میں دیکھا.
ہم آ رہا ہے اور کیا نہیں جانتے، لیکن ہم ان تین عناصر حل ہے.
>> اگلے ناچھانٹا ہوا عنصر ہے تین، تو ہم اسے ایک طرف مقرر کریں گے.
ہم سے زیادہ منتقل کریں گے جو ہم جو اس وقت کی ضرورت
گزشتہ میں کے طور پر سب کچھ نہیں ہے دو مقدمات، یہ صرف پانچ ہے.
اور پھر ہم میں تین رہنا گے، دو اور پانچ کے درمیان.
>> چھ ناچھانٹا ہوا اگلے ہے سرنی عنصر.
اور حقیقت میں چھ تو، پانچ سے زیادہ ہے ہم کسی بھی گماگمن ایسا کرنے کی ضرورت نہیں.
ہم صرف صحیح پر چھ سمت کر سکتے ہیں مطابق حصہ کے آخر.
>> آخر میں، چار ہے آخری ناچھانٹا ہوا عنصر.
تو ہم اسے ایک طرف مقرر کریں گے، زیادہ منتقل عناصر ہم سے زیادہ منتقل کرنے کے لئے کی ضرورت ہے
یہ تعلق رکھتا ہے جہاں اور پھر چار رکھ.
اور اب دیکھو، ہم قسم ہے تمام عناصر کے.
اندراج کے ساتھ نوٹس قسم، ہم نے نہیں کیا
آگے اور پیچھے صف میں جانے کے لئے.
ہم صرف صف کے پار چلا گیا ایک وقت، اور ہم چیزوں کو منتقل کر دیا گیا
ہم نے پہلے ہی ترتیب میں، کا سامنا کرنا پڑا تھا کہ نئے عناصر کے لئے کمرے بنانے کے لئے.
>> تو کیا بدترین صورت ہے اندراج طرح سے منظر نامے؟
بدترین صورت میں، سرنی معکوس ترتیب میں ہے.
تم (ن) کے عناصر میں سے ہر ایک میں منتقل کرنا پڑے (ن) کے عہدوں تک، ہر ایک وقت ہے کہ ہم
ایک اندراج بنانے.
یہ منتقل کی ایک بہت ہے.
>> بہترین صورت میں، سرنی بالکل مطابق ہے.
اور اس طرح سے ہوا ہے کی طرح مثال میں پانچ اور چھ کے ساتھ،
ہم صرف اس پر سمت کر سکتے ہیں جہاں کسی منتقلی کرنے کے لئے بغیر،
ہم بنیادی طور پر کروں گا.
>> آپ یہ تصور کریں کہ تو ہماری سرنی، چھ کے ذریعے ایک تھا
ہم کی طرف سے شروع کروں گا ایک اعلان کے مطابق ہے.
دو تو ہم صرف کر سکتے ہیں ایک کے بعد آتا ہے ایک اور دو حل کر رہے ہیں اچھی طرح سے، ٹھیک ہے، کا کہنا ہے کہ.
تین ٹھیک ہے، تو بعد دو آتا، ایک اور دو اور تین حل کر رہے ہیں.
>> ہم ہیں، کوئی سویپ نہیں بنا رہے ہیں صرف اس صوابدیدی لائن آگے بڑھ رہے ہیں
ہم جا کے طور درمیان حل اور ناچھانٹا ہوا.
کے طور پر مؤثر طریقے سے ہم مثال میں کیا تھا کے طور پر، ہم آگے بڑھنے کے طور پر، نیلے عناصر تبدیل.
تو بدترین صورت رن ٹائم تو، کیا ہے؟
ہم میں سے ہر ایک میں منتقل کرنا پڑے تو یاد رکھیں ن عناصر ممکنہ N عہدوں،
امید ہے کہ آپ کو دیتا ہے بدترین صورت ہے کہ ایک خیال
رن ٹائم بڑا این اے مربع ہے.
>> سرنی بالکل ہے تو حل، ہم سب کرنا ہے
ہر ایک عنصر پر دیکھو ایک بار، اور پھر ہم کیا کر رہے ہیں.
تو سب سے بہتر صورت میں، یہ (ن) کے ومیگا ہے.
>> میں ڈوگ لایڈ ہوں.
یہ CS50 ہے.