ترتيب المشط
{{بطاقة خوارزمية}}
'''ترتيب المشط''' [[خوارزمية ترتيب]] بسيطةً نسبياً، صممها في البداية Włodzimierz Dobosiewicz في عام 1980.<ref name=BB>[https://www.sciencedirect.com/science/article/abs/pii/S0020019000002234 Brejová, Bronislava. "Analyzing variants of Shellsort"] {{Webarchive|url=https://web.archive.org/web/20150924153415/http://www.sciencedirect.com/science/article/pii/S0020019000002234 |date=24 سبتمبر 2015}}</ref> ثم أعاد اكتشافها Stephen Lacey و Richard Box في عام 1991.<ref>[http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm "A Fast Easy Sort"], ''[[بايت (مجلة)|بايت]]'', April 1991 {{Webarchive|url=https://web.archive.org/web/20160303204009/http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm |date=03 مارس 2016}}</ref> وتعد تحسيناً لخوارزمية [[فرز فقاعي|ترتيب الفقاعات]].
== الخوارزمية ==
الفكرة الأساسية هي إزالة ''السلاحف'', أو القيم الصغيرة الفريبة من نهاية القائمة، فهي سبب رئيسي في تبطيء خوارزمية ترتيب الفقاعات، في حين لا تسبب ''الأرانب'', القيم الكبيرة في بداية القائمة، أي مشكلة في ترتيب الفقاعات.

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

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

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

=== شبه الكود ===
 '''تابع''' ترتيب_المشط ('''مصفوفة''' الدخل)<br/>
  الفجوة:= الدخل.الحجم <span style="color:green">\\تهيئة حجم الفجوة </span><br/>
  الانكماش:= 1.3 <span style="color:green">\\تعيين قيمة عامل الانكماش</span><br/>
<br/>
  '''كرر حتى تصبح''' الفجوة = 1 '''و''' المبادَل = غيرصحيح<br/>
   <span style="color:green">\\تحديث قيمة الفجوة لمشط جديد. ما يلي مجرد مثال</span><br/>
   الفجوة:= عددصحيح (الفجوة \ الانكماش)\\قسمة صحيحة<br/>
   '''إذا كانت''' الفجوة <1<br/>
   <span style="color:green">\\أصغر قيمة للفجوة هي 1</span><br/>
   الفجوة:= 1<br/>
   '''نهاية جملة الشرط'''

   س:= 0<br/>
   المبادَل:= غيرصحيح<span style="color:green">\\انظر [[فرز فقاعي|ترتيب الفقاعات]] للتوضيح </span>

   <span style="color:green">\\«مشطٌ» واحد على قائمة الدخل</span><br/>
   '''كرر حتى تصبح''' س + الفجوة>= الدخل.الحجم<span style="color:green"> \\انظر [[ترتيب شل]] <br/>لفكرة مماثلة</span>
    '''إذا كانت''' الدخل[س]> الدخل[س+الفجوة]<br/>
     [[بادل(علوم الحاسي)|مبادلة]](الدخل[س], الدخل[س+الفجوة])<br/>
     المبادَل:= صحيح <span style="color:green">\\ ضع علامة بأن عملية تبادل قد تمّت مما <br/>يعني</span>
         <span style="color:green">\\ أن القائمة ليست مرتبة بالضرورة <br/></span>
    '''نهاية جملة الشرط'''<br/>
       س:= س + 1<br/>
     '''نهاية حلقة التكرار'''

   '''نهاية حلقة التكرار'''<br/>
 '''نهاية التابع'''

== انظر أيضاً ==
* [[فرز فقاعي|ترتيب الفقاعات]]، خوارزمية أبطأ بشكل عام، وهي أساس ترتيب المشط.
== المراجع ==
{{مراجع}}

{{ترتيب}}
{{خوارزميات الترتيب}}
{{شريط بوابات|تقنية المعلومات|خوارزميات|علم الحاسوب}}

[[تصنيف:خوارزميات ترتيب]]
ترتيب المشط خوارزمية ترتيب بسيطةً نسبياً، صممها في البداية Włodzimierz Dobosiewicz في عام 1980.Brejová, Bronislava. "Analyzing variants of Shellsort"  ثم أعاد اكتشافها Stephen Lacey و Richard Box في عام 1991."A Fast Easy Sort", بايت, April 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
     نهاية حلقة التكرار

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

 انظر أيضاً 
 ترتيب الفقاعات، خوارزمية أبطأ بشكل عام، وهي أساس ترتيب المشط.
 المراجع 

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