فرز مشطي

الخوارزمية

في هذا الإطار، بكلام أكثر تخصصاً، تم تعديل الحلقة الداخلية في ترتيب الفقاعات، حيث تتم عملية الـتبديل الفعلية، بحيث تتناقص قيمة الفجوة بين العناصر التي تتم مقارنتها (خلال كل دورة للحقة الخارجية) بخطوات يحددها عامل الانكماش. يتم ذلك كما يلي. [ حجم الدخل\عامل الانكماش، حجم الدخل\عامل الانكماش^2, حجم الدخل\عامل الانكماش^3, ...., 1 ]. وذلك على عكس ترتيب الفقاعات، حيث تكون قيمة الفجوة ثابتة أي 1.

علاوةً على ذلك، تبدأ قيمة الفجوة من حجم القائمة التي يتم ترتيبها مقسوماً على عامل الانكماش (عادةً 1.3; انظر أدناه), ويتم ترتيب القائمة بهذه القيمة للفجوة (بعد تقريبها لأقرب عدد صحيح أصغر منها إن لزم الأمر). ثم يتم تقسيم قيمة الفجوة على عامل الانكماش مرة أخرى، ثم إعادة ترتيب المقائمة بقيمة الفجوة الجديدة، وهكذا يتم تكرار العملية حتى وصول قيمة الفجوة إلى 1. عند هذه المرحلة، تتابع خوارزمية ترتيب المشط بقيمة الفجوة 1 حتى إتمام عملية الترتيب كلّيّاً. بالتالي فهي مكافئة لترتيب الفقاعات خلال هذه المرحلة، ولكن أغلب السلاحف الموجودة يكون قد تم التعامل معها، ولذلك سيكون ترتيب الفقاعات فعالاً خلال هذه المرحلة.

وفي السياق ذاته، يؤثّر معامل الانكماش إلى حدّ كبير على ترتيب المشط. وقد اقترح المؤلف في مقاله الأصلي عن الخوارزمية قيمة 1.3 للهذا العامل.فالقيمة الصغيرة للمعامل تسبب بطء الخوارزمية لاحتياجها للمزيد من المقارنات، بينما تسبب القيمة الكبيرة للمعامل عدم حدوث أي مقارنة.وقد وجد Lacey و Box بالتجربة (عبر اختبار ترتيب المشط على أكثر من 200,000 قائمة عشوائية)أن القيمة 1.3 هي الأفضل لعامل الانكماش.

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

كذلك، عند مقارنة أي عنصرين في ترتيب الفقاعات يكون بينهما فجوة (مسافة بين العنصرين) قيمتها 1. الفكرة الأساسية في ترتيب المشط هي إمكانية جعل هذه الفجوة أكبر من 1(ترتيب شل يعتمد هو كذلك على هذه الخوارزمية، ولكنه يعتبر تعديلاً على الترتيب بالإدراج أكثر من كونه تعديلاً على ترتيب الفقاعات).

انظر أيضاً

علاوةً على ذلك، ترتيب الفقاعات، خوارزمية أبطأ بشكل عام، وهي أساس ترتيب المشط.

شبه الكود

تابع ترتيب_المشط (مصفوفة الدخل)

الفجوة:= الدخل.الحجم \\تهيئة حجم الفجوة

إذا كانت الدخل[س]> الدخل[س+الفجوة]

• مبادلة(الدخل[س], الدخل[س+الفجوة])
• المبادَل:= صحيح \\ ضع علامة بأن عملية تبادل قد تمّت مما يعني
• \\ أن القائمة ليست مرتبة بالضرورة
• نهاية جملة الشرط
• س:= س + 1
• نهاية حلقة التكرار
• نهاية حلقة التكرار
• نهاية التابع

الانكماش:= 1.3 \\تعيين قيمة عامل الانكماش

• كرر حتى تصبح الفجوة = 1 و المبادَل = غيرصحيح
• \\تحديث قيمة الفجوة لمشط جديد. ما يلي مجرد مثال
• الفجوة:= عددصحيح (الفجوة \ الانكماش)\\قسمة صحيحة
• إذا كانت الفجوة <1
• \\أصغر قيمة للفجوة هي 1
• الفجوة:= 1
• نهاية جملة الشرط
• س:= 0
• المبادَل:= غيرصحيح\\انظر ترتيب الفقاعات للتوضيح

\\«مشطٌ» واحد على قائمة الدخل

علاوةً على ذلك، كرر حتى تصبح س + الفجوة>= الدخل.الحجم \\انظر ترتيب شل لفكرة مماثلة