ترتيب المشط

ترتيب المشط

بيانات عامّة

الصنف	خوارزمية ترتيب
بنية البيانات	مصفوفة

الأداء

أسوء حالة	$O(n^{2})$
الحالة المُثلى	$O(n\log n)$
أسوأ حالة تعقيد مكاني	$O(1)$

ترتيب المشط خوارزمية ترتيب بسيطةً نسبياً، صممها في البداية Włodzimierz Dobosiewicz في عام 1980. ثم أعاد اكتشافها Stephen Lacey و Richard Box في عام 1991. وتعد تحسيناً لخوارزمية ترتيب الفقاعات.

الخوارزمية

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

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

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

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

شبه الكود

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

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

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

 كرر حتى تصبح الفجوة = 1 و المبادَل = غيرصحيح

  \\تحديث قيمة الفجوة لمشط جديد. ما يلي مجرد مثال

  الفجوة:= عددصحيح (الفجوة \ الانكماش)\\قسمة صحيحة

  إذا كانت الفجوة <1

  \\أصغر قيمة للفجوة هي 1

  الفجوة:= 1

  نهاية جملة الشرط

  س:= 0

  المبادَل:= غيرصحيح\\انظر ترتيب الفقاعات للتوضيح 

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

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

    مبادلة(الدخل[س], الدخل[س+الفجوة])

    المبادَل:= صحيح \\ ضع علامة بأن عملية تبادل قد تمّت مما 
يعني
        \\ أن القائمة ليست مرتبة بالضرورة 

   نهاية جملة الشرط

      س:= س + 1

    نهاية حلقة التكرار

  نهاية حلقة التكرار

نهاية التابع

انظر أيضاً

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

المراجع

 !