فرز الدمج والإدراج

في علم الحاسوب ، تُعدّ خوارزمية فرز الدمج والإدراج، أو خوارزمية فورد-جونسون، خوارزمية فرز مقارنة نُشرت عام 1959 على يد إل آر فورد الابن وسيلمر إم جونسون . ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} تستخدم هذه الخوارزمية عددًا أقل من المقارنات في أسوأ الحالات مقارنةً بأفضل الخوارزميات المعروفة سابقًا، وهما فرز الإدراج الثنائي وفرز الدمج . ^{[ 1 ]} ولعشرين عامًا، كانت خوارزمية الفرز الأقل استخدامًا للمقارنات. ^{[ 5 ]} وعلى الرغم من عدم أهميتها العملية، إلا أنها لا تزال ذات أهمية نظرية فيما يتعلق بمشكلة الفرز بأقل عدد ممكن من المقارنات. ^{[ 3 ]} ويُحتمل أن يكون ستانيسواف تريبولا وتشين بينغ قد اكتشفا هذه الخوارزمية بشكل مستقل . ^{[ 4 ]}

تُنفّذ خوارزمية فرز الدمج والإدراج الخطوات التالية على المدخلات${\displaystyle X}$ل${\displaystyle n}$العناصر: ^{[ 6 ]}

1. قم بتجميع عناصر${\displaystyle X}$داخل${\displaystyle \lfloor n/2\rfloor }$أزواج من العناصر، بشكل عشوائي، مع ترك عنصر واحد غير مقترن إذا كان هناك عدد فردي من العناصر.
2. يؤدي${\displaystyle \lfloor n/2\rfloor }$إجراء مقارنات، واحدة لكل زوج، لتحديد العنصر الأكبر من بين العنصرين في كل زوج.
3. فرز بشكل متكرر${\displaystyle \lfloor n/2\rfloor }$العناصر الأكبر من كل زوج، مما يؤدي إلى إنشاء تسلسل مُرتب${\displaystyle S}$ل${\displaystyle \lfloor n/2\rfloor }$من عناصر الإدخال، بترتيب تصاعدي، باستخدام فرز الدمج والإدراج.
4. أدرج في بداية${\displaystyle S}$العنصر الذي تم إقرانه بالعنصر الأول والأصغر من${\displaystyle S}$.
5. أدخل المتبقي${\displaystyle \lceil n/2\rceil -1}$عناصر من${\displaystyle X\setminus S}$داخل${\displaystyle S}$، واحدة تلو الأخرى، مع ترتيب إدخال مُختار خصيصًا وموصوف أدناه. استخدم البحث الثنائي في التسلسلات الفرعية من${\displaystyle S}$(كما هو موضح أدناه) لتحديد الموضع الذي يجب إدخال كل عنصر فيه.

تم تصميم الخوارزمية للاستفادة من حقيقة أن عمليات البحث الثنائي المستخدمة لإدراج العناصر في${\displaystyle S}$تكون هذه الطريقة أكثر كفاءة (من منظور تحليل أسوأ الحالات) عندما يكون طول التسلسل الفرعي الذي يتم البحث فيه أقل بواحد من قوة العدد اثنين . وذلك لأنه، بالنسبة لهذه الأطوال، تستخدم جميع نتائج البحث نفس عدد المقارنات. ^{[ 1 ]} لاختيار ترتيب إدخال يُنتج هذه الأطوال، ضع في اعتبارك التسلسل المُرتب.${\displaystyle S}$بعد الخطوة الرابعة من المخطط أعلاه (قبل إدراج العناصر المتبقية)، ودع${\displaystyle x_{i}}$يشير إلى${\displaystyle i}$العنصر رقم n من هذه المتسلسلة المرتبة. وبالتالي،

${\displaystyle S=(x_{1},x_{2},x_{3},\dots ),}$

حيث كل عنصر${\displaystyle x_{i}}$مع${\displaystyle i\geq 3}$يقترن بعنصر${\displaystyle y_{i}<x_{i}}$لم يتم إدراجها بعد. (لا توجد عناصر)${\displaystyle y_{1}}$أو${\displaystyle y_{2}}$لأن${\displaystyle x_{1}}$و${\displaystyle x_{2}}$(تم إقرانهم مع بعضهم البعض.) إذا${\displaystyle n}$إذا كان العدد فرديًا، فيجب ترقيم العنصر المتبقي غير المزدوج أيضًا على النحو التالي:${\displaystyle y_{i}}$مع${\displaystyle i}$أكبر من مؤشرات العناصر المزدوجة. بعد ذلك، يمكن توسيع الخطوة الأخيرة من المخطط أعلاه إلى الخطوات التالية: ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}

• قسّم العناصر غير المدرجة${\displaystyle y_{i}}$إلى مجموعات ذات مؤشرات متجاورة. هناك عنصران${\displaystyle y_{3}}$و${\displaystyle y_{4}}$في المجموعة الأولى، ومجموع أحجام كل مجموعتين متجاورتين يُشكّل متتالية من قوى العدد اثنين. وبالتالي، فإن أحجام المجموعات هي: ٢، ٢، ٦، ١٠، ٢٢، ٤٢، ...
• رتب العناصر غير المُدرجة حسب مجموعاتها (من الفهارس الأصغر إلى الفهارس الأكبر)، ولكن داخل كل مجموعة، رتبها من الفهارس الأكبر إلى الفهارس الأصغر. وهكذا، يصبح الترتيب

${\displaystyle y_{4},y_{3},y_{6},y_{5},y_{12},y_{11},y_{10},y_{9},y_{8},y_{7},y_{22},y_{21}\dots }$

• استخدم هذا الترتيب لإدراج العناصر${\displaystyle y_{i}}$داخل${\displaystyle S}$لكل عنصر${\displaystyle y_{i}}$استخدم البحث الثنائي منذ البداية${\displaystyle S}$حتى (ولكن ليس شاملاً)${\displaystyle x_{i}}$لتحديد مكان الإدخال${\displaystyle y_{i}}$.

يترك${\displaystyle C(n)}$يشير إلى عدد المقارنات التي يجريها فرز الدمج والإدراج، في أسوأ الحالات، عند الفرز.${\displaystyle n}$العناصر. يمكن تقسيم هذا العدد من المقارنات إلى مجموع ثلاثة حدود:

• ${\displaystyle \lfloor n/2\rfloor }$المقارنات بين أزواج العناصر،
• ${\displaystyle C(\lfloor n/2\rfloor )}$المقارنات الخاصة بالاستدعاء التكراري، و
• عدد من المقارنات لعمليات الإدخال الثنائية المستخدمة لإدخال العناصر المتبقية.

في الحد الثالث، يكون أسوأ عدد للمقارنات لعناصر المجموعة الأولى هو اثنان، لأن كل عنصر يُدرج في سلسلة فرعية من${\displaystyle S}$بطول لا يتجاوز ثلاثة. أولاً،${\displaystyle y_{4}}$يتم إدراجها في التسلسل الفرعي المكون من ثلاثة عناصر${\displaystyle (x_{1},x_{2},x_{3})}$. ثم،${\displaystyle y_{3}}$يتم إدخالها في أحد التبديلات لتسلسل العناصر الثلاثة${\displaystyle (x_{1},x_{2},y_{4})}$أو في بعض الحالات إلى التسلسل الفرعي المكون من عنصرين${\displaystyle (x_{1},x_{2})}$وبالمثل، العناصر${\displaystyle y_{6}}$و${\displaystyle y_{5}}$يتم إدخال كل عنصر من المجموعة الثانية في سلسلة فرعية لا يزيد طولها عن سبعة، باستخدام ثلاث مقارنات. وبشكل عام، فإن أسوأ عدد للمقارنات للعناصر في${\displaystyle i}$المجموعة هي${\displaystyle i+1}$لأن كل منها يُدرج في سلسلة فرعية طولها على الأكثر${\displaystyle 2^{i+1}-1}$[ ^{1 ] [ 2 ] [ 3 ] [ 4 ]} من خلال جمع عدد المقارنات المستخدمة لجميع العناصر وحل علاقة التكرار الناتجة ^، يمكن استخدام هذا التحليل لحساب قيم${\displaystyle C(n)}$، مما يعطي الصيغة ^{[ 7 ]}

${\displaystyle C(n)=\sum _{i=1}^{n}\left\lceil \log _{2}{\frac {3i}{4}}\right\rceil \approx n\log _{2}n-1.415n}$

أو، بصيغة مغلقة ، ^{[ 8 ]}

${\displaystyle C(n)=n{\biggl \lceil }\log _{2}{\frac {3n}{4}}{\biggr \rceil }-{\biggl \lfloor }{\frac {2^{\lfloor \log _{2}6n\rfloor }}{3}}{\biggr \rfloor }+{\biggl \lfloor }{\frac {\log _{2}6n}{2}}{\biggr \rfloor }.}$

ل${\displaystyle n=1,2,\dots }$عدد المقارنات هو ^{[ 1 ]}

0، 1، 3، 5، 7، 10، 13، 16، 19، 22، 26، 30، 34، ... (التسلسل A001768 في OEIS )

تُسمى هذه الخوارزمية فرز الدمج والإدراج لأن المقارنات الأولية التي تُجريها قبل استدعائها التكراري (مُزاوجة العناصر العشوائية ومقارنة كل زوج) تُشابه المقارنات الأولية لفرز الدمج ، بينما تتبع المقارنات التي تُجريها بعد الاستدعاء التكراري (باستخدام البحث الثنائي لإدراج العناصر واحدًا تلو الآخر في قائمة مُرتبة) نفس مبدأ فرز الإدراج . وبهذا المعنى، فهي خوارزمية هجينة تجمع بين فرز الدمج وفرز الإدراج. ^{[ 9 ]}

للمدخلات الصغيرة (حتى${\displaystyle n=11}$) عدد مقارناتها يساوي الحد الأدنى لترتيب المقارنة لـ${\displaystyle \lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n}$مع ذلك، بالنسبة للمدخلات الأكبر حجمًا، يكون عدد المقارنات التي تُجريها خوارزمية الدمج والإدراج أكبر من هذا الحد الأدنى. كما أن فرز الدمج والإدراج يُجري عددًا أقل من المقارنات مقارنةً بأعداد الفرز ، التي تحسب المقارنات التي يُجريها فرز الإدراج الثنائي أو فرز الدمج في أسوأ الحالات. وتتراوح أعداد الفرز بين${\displaystyle n\log _{2}n-0.915n}$و${\displaystyle n\log _{2}nn}$، مع نفس الحد الرئيسي ولكن بمعامل ثابت أسوأ في الحد الخطي ذي الرتبة الأدنى. ^{[ 1 ]}

فرز الدمج والإدراج هو خوارزمية الفرز التي تحتوي على أقل عدد ممكن من المقارنات لـ${\displaystyle n}$العناصر كلما${\displaystyle n\leq 22}$وهي الأقل مقارنة بـ${\displaystyle n\leq 46}$[ ^{10 ] [ 11 ]} على مدى عشرين عامًا، كانت خوارزمية فرز الدمج والإدراج هي خوارزمية الفرز الأقل عددًا من المقارنات المعروفة لجميع أطوال المدخلات. ومع ذلك، في عام 1979، نشر جلين ماناشر خوارزمية فرز أخرى تستخدم عددًا أقل من المقارنات، وذلك للمدخلات الكبيرة بما يكفي. ^{[ 3 ] [ 5 ] لا} يزال من غير المعروف بالضبط عدد المقارنات اللازمة للفرز، لجميع${\displaystyle n}$لكن خوارزمية ماناشر وخوارزميات الفرز اللاحقة التي حطمت الأرقام القياسية استخدمت جميعها تعديلات على أفكار فرز الدمج والإدراج. ^{[ 3 ]}