[عزف الموسيقى] DOUG لويد: اختيار النوع هو الخوارزمية التي، كما قد تتوقع، يفرز مجموعة من العناصر. وأذكر خوارزمية هو عبارة عن مجموعة خطوة بخطوة من تعليمات لإكمال المهمة. 

في اختيار فرز الفكرة الأساسية هي هذه، العثور على أصغر عنصر لم يتم فرزها و إضافته إلى نهاية القائمة فرزها. على نحو فعال ما يفعل ذلك هو بناء قائمة تم فرزها، عنصر واحد في وقت واحد. تقسمها إلى شبة الكود يمكننا أن أذكر هذه الخوارزمية على النحو التالي، كرر هذا حتى تبقى أية عناصر غير مصنفة. البحث عن طريق فرزها البيانات للعثور على أصغر قيمة، ثم مبادلة أصغر قيمة مع العنصر الأول من الجزء فرزها. 

قد تساعد على تصور هذا، لذلك دعونا نلقي نظرة على هذا. لذلك هذا، وأنا أزعم، هو مجموعة فرزها ولدي يشار إليه بالإشارة إلى أن جميع من العناصر الملونة الحمراء، لا يتم فرز ومع ذلك. هذا هو كامل جزء لم يتم فرزها من مجموعة. 

لذلك دعونا نذهب من خلال خطوات اختيار لفرز هذه المجموعة. ذلك مرة أخرى، ونحن تكرار ستعمل حتى لا تظل العناصر التي لم يتم فرزها. نحن ستعمل من خلال بحث البيانات للعثور على أصغر قيمة، ثم مبادلة تلك القيمة مع العنصر الأول من الجزء فرزها. 

الآن، مرة أخرى، كامل مجموعة هي جزء لم يتم فرزها. جميع العناصر الحمراء هي التي لم يتم فرزها. لذلك نحن من خلال البحث عن و نجد أصغر قيمة. نبدأ في البداية، نذهب إلى النهاية، نجد أصغر قيمة هي، واحدة. لذلك هذا جزء واحد. ثم الجزء الثاني، مبادلة تلك القيمة مع العنصر الأول من الجزء فرزها، أو أول عنصر الأحمر. 

في هذه الحالة من شأنه أن يكون خمسة، لذلك نحن مبادلة واحدة وخمس سنوات. عندما نفعل هذا، يمكننا ترى بالعين المجردة التي كانت لدينا انتقل أصغر عنصر قيمة في المصفوفة، إلى البداية. فرز نحو فعال ذلك العنصر. 

وحتى نتمكن من تأكيد الواقع والدولة التي واحدة، يتم فرز. ولذا فإننا سوف تشير إلى جزء فرز من مجموعة لدينا، من خلال تلوين أنها الأزرق. 

ونحن الآن مجرد تكرار العملية مرة أخرى. نحن نبحث من خلال الجزء فرزها من مجموعة للعثور على أصغر عنصر. في هذه الحالة، فإنه من اثنين. 

نحن مبادلة مع أول عنصر الجزء فرزها. في هذه الحالة اثنين يحدث أيضا أن تكون العنصر الأول من الجزء فرزها. لذلك نحن مبادلة اثنين مع نفسه، والتي في الواقع يترك اثنين فقط أين هو، وانها فرزها. استمرار جرا، ونحن من خلال البحث عن العثور على أصغر عنصر. انها الثلاث. نحن مبادلة مع أول عنصر، وهو خمسة. والآن يتم فرز ثلاثة. 

نحن نبحث عن طريق مرة أخرى، ونحن العثور على أصغر عنصر هو أربعة. نحن مبادلة مع العنصر الأول لل جزء لم يتم فرزها، والآن يتم فرز الأربعة. 

نجد أن خمسة من أصغر عنصر. نحن مبادلة مع أول عنصر الجزء فرزها. والآن يتم فرز الخمسة. 

ثم أخيرا، لدينا جزء لم يتم فرزها يتألف من مجرد عنصر واحد، لذلك نحن من خلال البحث عن ونجد أن ستة هو أصغر، في واقع الأمر، العنصر فقط. وبعد ذلك يمكننا أن نقول أن يتم فرز عليه. ونحن الآن قد تحولت مجموعة لدينا من يجري فرزها تماما باللون الأحمر، إلى مرتبة تماما في الزرقاء، وذلك باستخدام اختيار نوع. 

إذن ما هو أسوأ سيناريو هنا؟ حسنا في أسوأ المطلق الحالة، يتعين علينا أن ننظر أكثر جميع عناصر المصفوفة ل العثور على أصغر عنصر لم يتم فرزها، وعلينا أن نكرر هذه العملية n مرة. مرة واحدة لكل عنصر من المصفوفة لأننا فقط، في هذه الخوارزمية، عنصر واحد في وقت ونوع. 

ما هو أفضل سيناريو؟ حسنا انها بالضبط نفس الشيء، أليس كذلك؟ لدينا في الواقع إلى ما زالت الخطوة من خلال كل عنصر واحد من مجموعة من أجل التأكد من أنه هو، في الواقع، أصغر عنصر. 

وبالتالي فإن أسوأ حالة وقت، ونحن لديك لتكرار عملية ن مرات، مرة واحدة لكل من العناصر ن. وفي أحسن الأحوال، علينا أن تفعل الشيء نفسه. 

حتى التفكير في العودة إلى موقعنا الحسابية الأدوات التعقيد، ما رأيك هو أسوأ وقت الحال بالنسبة لاختيار نوع؟ ما رأيك هو الأفضل وقت الحال بالنسبة لاختيار نوع؟ 

هل تخمين الكبير O ن تربيع، والكبير أوميغا ن المربعة؟ كنت على حق. تلك هي، في الواقع، أسوأ الحالات وأفضل حالة تشغيل مرات، لاختيار نوع. 

أنا دوغ ويد. هذا هو CS50.