[Powered by Google Translate] [دمج فرز] [روب بودين - جامعة هارفارد] [هذا CS50. - CS50.TV] دعونا نتحدث عن نوع الدمج. حتى الآن كنت قد رأيت نوع فقاعة، نوع الإدراج، ونوع الاختيار. على الرغم من أنني سوف نوع من موجة يدي إلى ما أعنيه أفضل، دمج النوع يؤدي عموما أفضل من أي من هذه الأنواع 3. 

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

في حين أن هذا يعمل، انها هناك الكثير من العمل لا لزوم لها. يمكننا القيام بذلك بشكل أسرع من الفرز فقط. لاحظت أن فكرة واحدة المشكلة تكمن في أخذ كوب فقط من كل قائمة بالتناوب. في حين أن ذلك قد يبدو أن يعمل في البداية، فعل ذلك نحن في نهاية المطاف مع 4، 8، 15، 23، 16 - لاحظ أن 16 و 23 هي خارج المكان. هذا هو لأن 2 العناصر التي يجب أن تظهر على التوالي في القائمة المدمجة في قائمة الأولية نفسها. كلا 15 و 16 في القائمة على اليسار. هو خدعة للاستفادة من حقيقة أن يتم تصنيف بالفعل كلا القائمتين. هذا يعني أنه إذا نظرنا إلى العناصر الأولى من كلتا القائمتين - هنا و 4 و 8 - يجب أن يكون واحد منهم أيضا العنصر الأول من القائمة المدمجة. حسنا، لماذا؟ يتم تصنيف بالفعل كل من هذه القوائم، ولذا يجب إما 4 أو 8 يكون أصغر عنصر عند الجمع بين القوائم 2. في هذه الحالة، هو أصغر 4، حتى نتمكن من إخراج 4 و جعله العنصر الأول من قائمتنا المدمجة. الآن نحن نواصل دمج ما تبقى من 3 عناصر القائمة الأولى و 4 عناصر من القائمة الثانية. 

مرة أخرى، نحن بحاجة فقط للنظر في العنصر الأول من كلتا القائمتين. يجب أصغر من 2 يكون العنصر الثاني من قائمتنا المدمجة. هذه المرة، ما بين 8 و 15 أصغر هو 8، وإدراج ذلك نحن أن باعتبارها العنصر الثاني من قائمتنا فرزها. يمكننا أن نواصل مقارنة العناصر الأولى من كلتا القائمتين وإزالة أصغر من 2. مقارنة 15 و 23 15، وأصغر بحيث لدينا العنصر الثالث. مقارنة الآن 16 و 23 و 16 هو أصغر. لذلك هذا هو العنصر الرابع. 

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

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

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

حتى نتمكن من بدء دمج أزواج من القوائم مرة أخرى. دمج 15 و 108 و 4 و 50 - تأخذ أولا 4، ثم 15، ثم 50، ثم 108. دمج 8 و 42 و 16 و 23، نأخذ أولا 8، ثم 16، ثم 23، ثم 42. حتى الآن لدينا فقط 2 قوائم حجم 4، يتم فرز كل منها. حتى الآن نحن دمج هذه القوائم 2. أولا نأخذ 4. ثم أخذنا 8. ثم نأخذ 15 و 16، ثم 23، ثم 42، ثم 50، ثم 108. وننتهي. لدينا الآن قائمة فرزها. فكيف كان هذا بسرعة، بالضبط؟ من الناحية التقنية، دمج النوع هو O (N سجل ن)، في حين أن كل من نوع فقاعة، نوع الإدراج، واختيار نوع O هي (ن ²). في الواقع، وكما ستعرف قريبا، فلن تكون قادرة على الخروج مع نوع التي تنفذ أفضل من O (ن سجل ن) في الحالة العامة. مرة أخرى، لا تقلق بشأن هذا التدوين O كبيرة إذا كنت لم أر حتى الآن. 

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

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

اسمي روب بودين، وهذا هو CS50. [CS50.TV] - واختيار نوع. [يضحك] أوه، حصلت على اتخاذ أنه من اللازم لأنني تحولت كيف كنت عرضه. القائمة على اليسار. كان ذلك خطأ مطبعي. [اخطأ] I ثمل - [يضحك] أنا لا أعرف ما -