[عزف الموسيقى] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

إذا كان الصفيف هي تماما مرتبة، كل ما عليك القيام به هو أن ننظر في كل عنصر واحد مرة واحدة، ثم ننتهي. حتى في أفضل الأحوال، فإنه من أوميغا ن. 

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