[Powered by Google Translate] [ترتيب الإدراج] [تومي MacWilliam] [جامعة هارفارد] [هذا CS50.TV] دعونا نلقي نظرة على نوع الإدراج، خوارزمية لاتخاذ قائمة الأرقام والفرز لهم. خوارزمية، تذكر، هو مجرد إجراء خطوة بخطوة لإنجاز المهمة. الفكرة الأساسية وراء نوع الإدراج، هو تقسيم قائمتنا إلى جزئين، جزء مصنفة وجزء لم يتم فرزها. 

في كل خطوة من خطوات الخوارزمية، يتم نقل عدد لم يتم فرزها من الجزء إلى الجزء مصنفة حتى في نهاية المطاف يتم فرز القائمة بأكملها. ستجد هنا لائحة من ستة أرقام لم يتم فرزها - 23، 42، 4، 16، 8، و 15. وبما أن هذه الأرقام ليست كل شيء في ترتيب تصاعدي، لم يتم فرزها كنت فيها. لأننا لم نبدأ بعد الفرز، نحن سنعتبر جميع العناصر الستة لدينا جزء لم يتم فرزها. 

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

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

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

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

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

حسنا. الآن، لدينا أربعة عناصر فرزها والتي لم يتم فرزها عنصرين. لذلك، دعنا ننتقل ال 8 في الجزء فرزها. ثمانية أقل من 42. ثمانية أقل من 23. و8 هو أقل من 16. لكن 8 هو أكبر من 4. لذلك، نود أن إدراج ال 8 بين 4 و 16 في. والآن لدينا واحد فقط أكثر عنصر غادر لفرز - ال 15. أقل من خمسة عشر (42 عاما) خمسة عشر أقل من 23. و 15 أقل من 16. ولكن 15 أكبر من 8. 

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

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

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

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

أبحث في شبة الكود، لدينا حلقة متداخلة داخل حلقة أخرى، التي، في الواقع، يبدو وكأنه عملية (ن ^ 2) O. ومع ذلك، فإن جزء من قائمة مصنفة لا يحتوي على القائمة بأكملها حتى النهاية. ومع ذلك، يمكن أن يحتمل إدراج عنصر جديد في بداية الجزء مصنفة على كل التكرار من الخوارزمية، وهو ما يعني أن كنا أن ننظر إلى كل عنصر من عناصر حاليا في الجزء فرزها. لذلك، وهذا يعني أننا يمكن أن تجعل المقارنة 1 للعنصر الثاني، 2 المقارنات للعنصر الثالث، وهلم جرا. لذا، فإن العدد الإجمالي للخطوات هو مجموع الأعداد الصحيحة من 1 إلى طول قائمة ناقص 1. يمكننا تمثيل هذا مع الجمع. 

ونحن لن نذهب إلى summations هنا، ولكن تبين أن هذا الجمع يساوي ن (ن - 1) أكثر من 2، وهو ما يعادل ن ^ 2/2 - ن / 2. عندما نتحدث عن وقت مقارب، هذا المصطلح ^ N 2 سوف تهيمن على هذا المصطلح ن. لذلك، النوع الكبير الإدراج O (N ^ 2). ماذا لو ركضنا نوع الإدراج على قائمة تم فرزها بالفعل. في هذه الحالة، كنا ببساطة بناء الجزء مصنفة من اليسار إلى اليمين. لذلك، سنحتاج فقط بناء على أمر من الخطوات ن. 

وهذا يعني أن لديه نوع الإدراج أداء أفضل حالة ن، التي نمثلها مع Ω (ن). وهذا كل شيء عن نوع الإدراج، مجرد واحدة من العديد من الخوارزميات يمكننا استخدامها لفرز قائمة. اسمي تومي، وهذا هو CS50. [CS50.TV] أوه، لا يمكنك أن تتوقف أنه بمجرد بدء تشغيله. أوه، فعلنا ذلك - بوم >>!