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