الترتيب

طرق الترتيب البسيطة

مهمتنا هي ترتيب العناصر التالية:

لا شك أنك إذا ألقيت نظرةً على المهمة، فستجدها تافهةً للغاية؛ إنها الأعداد من واحد إلى عشرة. ولكن تبسيط الأمور سيتيح لنا التركيز على المنطق الذي تُقام عليه مهمة الترتيب.

أولًا: نطَّلع على جميع العناصر ونبحث عن العدد الأصغر. نأخذه من مكانه حيث وجدناه ونضعه في المقدمة. العدد الأصغر هنا هو العدد ١، ولذا ينبغي أن يوضع في الموضع الأول. وبما أن هذا الموضع يشغله عنصر آخر، لا بد أن نفعل شيئًا مع العدد ٤ الذي يقع في الموضع الأول حاليًّا، ولا يمكن أن نكتفي بحذفه. ما يمكننا فعله هو تبديله مع العدد الأصغر؛ أي ننقل العدد الأصغر إلى الموضع الأول وننقل العدد الذي كان في الموضع الأول سابقًا إلى الموضع الذي تُرك شاغرًا عند نقل العدد الأصغر. وهكذا ننتقل من هذا الموضع حيث العدد الأصغر مظلَّل باللون الأسود،

وننقله إلى هذا الموضع،

حيث العدد الأصغر مظلَّل باللون الأبيض كي نشير إلى أنه في موضعه الصحيح حسب الترتيب.

نفعل الأمر نفسه مع جميع الأعداد باستثناء العدد الأصغر الذي وجدناه؛ أي مع جميع الأعداد من الموضع الثاني بترتيب تصاعدي (الأعداد المظللة باللون الرمادي). نبحث عن العدد الأصغر بينها، وهو ٢، ونبدله مرة أخرى مع أول عدد من الأعداد التي «لم تُرتَّب» وهو العدد ٦:

نكرِّر الأمر نفسه مرة أخرى. نتعامل مع العناصر بدءًا من العنصر الثالث بترتيب تصاعدي؛ نبحث عن العدد الأصغر، وهو العدد ٣، ونبدله مع العنصر الموجود في الموضع الثالث وهو العدد ١٠:

إذا استمررنا بهذه الطريقة، فسيظل العدد ٤ في مكانه لأنه في الموضع الصحيح بالفعل، وسننتقل إلى العدد ٥ كي نضعه في موضع ترتيبه الصحيح:

في كل نقطة يقل عدد العناصر التي نمرُّ عليها لإيجاد العدد الأصغر أكثر وأكثر. في النهاية، سنوجِد العدد الأصغر لآخِر عنصرين، وبمجرد الانتهاء من ذلك، يكتمل ترتيب جميع العناصر.

يُطلق على طريقة الترتيب تلك اسم «الترتيب الانتقائي»؛ لأننا في كل مرة نختار العنصر الأصغر من بين العناصر التي لم تُرتَّب ونضعه حيث ينبغي أن يكون. ومثل جميع خوارزميات الفرز والترتيب التي سنتناولها، لا تواجه خوارزمية الترتيب الانتقائي مشكلةً مع الروابط؛ أي العناصر التي لها الترتيب نفسه. فإذا وجدنا أكثر من عنصر أصغر عند فحص العناصر غير المرتَّبة، نختار أيًّا منها باعتباره العنصر الأصغر. وفي المرة القادمة سنبحث عن العنصر المرتبط ونضعه بجوار العنصر المساوي له.

خوارزمية الترتيب الانتقائي من الخوارزميات البسيطة والمباشرة. فهل هي خوارزمية جيدة أيضًا؟ إذا انتبهنا إلى ما نفعله، فسنجد أننا ننتقل من بداية العناصر التي نريد ترتيبها إلى نهايتها، وفي كل مرة نحاول البحث عن العنصر الأصغر من بين العناصر غير المُرتَّبة. فإذا كان لدينا العدد من العناصر، فإن تعقيد خوارزمية الترتيب الانتقائي يساوي . وهذا ليس سيئًا في ذاته؛ فدرجةُ التعقيد تلك ليست مانعة، ويمكننا حل مسائل كبيرة (مثل ترتيب عدد كبير من العناصر) في مدة زمنية معقولة.

تتمثَّل المسألة تحديدًا في وجود خوارزمياتٍ أسرعَ من تلك؛ لأن الترتيب عملية بالغة الأهمية. لذا فعلى الرغم من أن خوارزمية الترتيب الانتقائي ليست سيئة بطبيعتها، فإننا عادة ما نفضِّل استخدام خوارزميات أخرى أكثر تطورًا، عندما يكون لدينا عدد كبير من العناصر. في الوقت نفسه، فإن خوارزمية الترتيب الانتقائي ليست سهلة الفهم على البشر فحسب، بل يسهل تنفيذها على جهاز الكمبيوتر بطريقة فعَّالة. لذا من الواضح أنها ليست ذات أهمية أكاديمية فحسب، بل إنها تُستخدم في الجانب العملي كثيرًا.

يمكن أن ينسحب الأمر نفسه على خوارزمية ترتيب بسيطة أخرى سنتناولها فيما يلي. كما هو الحال مع الترتيب الانتقائي، فإن هذه الطريقة في الترتيب سهلة الفهم بعيدًا عن أجهزة الكمبيوتر. في الحقيقة، إنها الطريقة التي قد نرتِّب بها البطاقات في أيدينا في ألعاب الورق.

تخيَّل أنك تمارس إحدى ألعاب الورق وأخذت فيها عشر أوراق (كأن تلعب لعبة الرامي على سبيل المثال). عندما تأخذ ورقةً تلو الأخرى، تريد ترتيبها في يدك. لنفترض أن ترتيب الأوراق، من الأصغر إلى الأكبر، هو:

في الحقيقة، في العديد من الألعاب (وفي لعبة الرامي) يمكن أن تكون ورقة الآس هي الورقة ذات الترتيب الأقل والأعلى، لكن سنفترض أنه لا يوجد سوى ترتيب واحد.

ستلعب بكل ورقة، بحيث تبدأ بورقة واحدة في يدك ويبقى تسع أوراق تأتي تباعًا كما يلي:

الآن، تأتي إلى الورقة الثانية، وهي الرقم ستة:

مكان ورقة الستة جيد بجوار بطاقة الأربعة، ولذا تتركها وتأخذ ورقة أخرى ويتبيَّن أنها اثنان:

هذه المرة، وحتى تُبقِي الأوراق مرتَّبة في يدك، تحتاج إلى نقل الورقة اثنين إلى يسار الورقة أربعة، ومِن ثَم تتحرك الورقة أربعة والورقة ستة موضعًا واحدًا جهة اليمين. ويكون ذلك قبل أن تلعب بورقة أخرى، وهي ثلاثة:

تُدخل الورقة ثلاثة بين الورقتين اثنين وأربعة، وتبحث عن الورقة التالية، وهي الورقة تسعة. تلك الورقة في المكان الصحيح بالفعل في يدك.

لقد أُدخِلت كل ورقة جديدة في الموضع الصحيح بالنسبة إلى الأوراق السابقة التي وُزِّعت. لذلك تسمَّى هذه الطريقة «الترتيب بالإدراج» وتصلح لأي نوع من العناصر، وليس أوراق اللعب فقط.

ومثل خوارزمية الترتيب الانتقائي، تتسم خوارزمية الترتيب بالإدراج بالبساطة في تنفيذها. وتبيَّن أن لها درجةَ التعقيد نفسها: . ولكن لها خاصية تميزها؛ فكما رأينا في مثال لعبة الأوراق، «لست بحاجة إلى معرفة العناصر سلفًا قبل ترتيبها». في الواقع إن ترتيب العناصر يتم وقت الحصول عليها. وهذا يعني أنه يمكنك استخدام خوارزمية الترتيب بالإدراج عندما تتدفَّق إليك العناصر المراد ترتيبها مباشرة. لقد قابلنا هذا النوع من الخوارزميات التي تطبَّق مباشرة مع توفير المدخلات عندما تناولنا مسألة جدولة المسابقات في التمثيلات البيانية بالفصل الثاني، وأسميناها «الخوارزمية الفورية». فإذا كان علينا ترتيب عدد غير معروف من العناصر، أو إذا كان لا بد أن نستطيع التوقُّف من فورنا ونقدِّم قائمة مرتَّبة في أي وقت يُطلب منَّا ذلك بلا سابق إنذار، تكون خوارزمية الترتيب بالإدراج هي الطريقة الملائمة.²

الترتيب بالجذر

أسهل طريقة للتعرُّف على خوارزمية الترتيب بالجذر هي استخدام أوراق اللعب مرة أخرى. لنفترض أن لدينا مجموعةً كاملة مختلطة من أوراق اللعب نريد ترتيبها. توجد طريقة لذلك وهي تكوين ١٣ مجموعة، واحدة لكل قيمة مَنزَلة. نتفحَّص المجموعة ونأخذ كل ورقة ونضعها في المجموعة التي تنتمي لها. سنحصل على ١٣ مجموعة كلٌّ منها تتكوَّن من ٤ أوراق: مجموعة تتضمَّن كل أوراق الآس وأخرى تتضمَّن كل بطاقات العدد اثنين وهكذا.

ثم نجمع الأوراق مجموعةً تلو الأخرى وننتبه إلى وضع كل مجموعة نأخذها تحت الأوراق التي نجمعها. بهذه الطريقة، ستكون كل الأوراق في أيدينا مرتَّبة جزئيًّا. ستكون أولُ أربع أوراق هي الآس، والأربع التي تليها هي الاثنين، وهكذا وصولًا إلى أوراق الملِك.

نكوِّن الآن أربع مجموعات جديدة، مجموعة لكل رمز. نتفحَّص الأوراق ونأخذ كل ورقة ونضعها في المجموعة التي تنتمي لها. سنحصل على أربع مجموعات من الرموز. ونظرًا لأن القيم قد رُتِّبت بالفعل، فسيكون لدينا في كل مجموعة كل البطاقات ذات الرمز الواحد مرتَّبة حسب القيمة.

للانتهاء من ترتيب الأوراق، لا نحتاج إلا إلى جمعها مجموعةً تلو الأخرى.

هذا هو جوهر طريقة الترتيب بالجذر. لم نرتِّب البطاقات بالمقارنة بينها جميعًا. بل أجرينا مقارناتٍ جزئية، حسب القيمة في البداية، ثم حسب الرمز.

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

نتأكد من أن جميع الأعداد الصحيحة تتكوَّن من عدد الحدود نفسه. ومِن ثَم نضيف إلى الأعداد أصفارًا جهة اليسار إذا لزم الأمر بحيث نحوِّل العدد ٥ إلى ٠٠٥ والعدد ٩٧ إلى ٠٩٧ والعدد ٥٣ إلى ٠٥٣. نراجع جميع الأعداد ونصنِّفها حسب الحد الموجود أقصى اليمين. نستخدم ذلك الحد لوضع الأعداد في عشر مجموعات:

خفَّفنا لون تظليل الأعداد للإشارة إلى أنها قد رُتِّبت جزئيًّا؛ وتتضمَّن كل مجموعة الأعداد المشتركة في نفس الحد جهة اليمين. تنتهي كل الأعداد في المجموعة الأولى بالرقم صفر، وفي المجموعة الثانية تنتهي بالرقم ١، حتى مجموعة الأعداد الأخيرة حيث تنتهي بالرقم ٩. الآن، نجمع المجموعات العشر، مع البدء من المجموعة الأولى جهة اليسار وإضافة المجموعات جهة الأسفل (مع الانتباه إلى عدم خلط الأعداد بأي طريقة). ثم نعيد توزيعها على عشر مجموعات باستخدام الحد الثاني جهة اليمين، ومِن ثَم يصبح لدينا الترتيب التالي:

هذه المرة، كل الأعداد في المجموعة الأولى تحتوي على الرقم صفر في الخانة الثانية جهة اليمين؛ بينما تحتوي المجموعة الثانية على الرقم واحد في الخانة الثانية جهة اليمين، وهكذا في بقية المجموعات الأخرى. في الوقت نفسه، تُرتَّب العناصر في كل مجموعة حسب الحد الأخير؛ لأن هذا ما فعلناه عندما جمعنا المجموعات في المرة الأولى.

ننتهي بتجميع المجموعات وإعادة توزيع الأعداد باستخدام الرقم الثالث من جهة اليمين هذه المرة:

الآن، تبدأ العناصر في كل مجموعة بالحد نفسه وتُرتَّب حسب الحد الثاني، نتيجةً لعملية تكوين المجموعات السابقة، وحسب الحد الأخير، نتيجةً لعملية تكوين المجموعات الأولى. لإكمال ترتيب الأعداد، نجمع فقط المجموعات مرة أخيرة.

يمكن تطبيقُ الترتيب بالجذر مع الكلماتِ أو أي تسلسل من حروف الأبجدية الرقمية وكذا الأعداد الصحيحة. في علم الكمبيوتر، نطلِق على تسلسل حروف الأبجدية الرقمية والرموز «سلسلة». يمكن تطبيق الترتيب بالجذر مع السلاسل، التي يمكن أن تتكوَّن من أرقام، كما في المثال الذي تناولناه، ولكن قد تكون أي نوع من السلاسل. عدد المجموعات في سلاسل الترتيب الأبجدي الرقمي يساوي عدد الحروف المميزة التي تؤلِّف الأبجدية (على سبيل المثال، تتكوَّن من ٢٦ مجموعة في أبجدية اللغة الإنجليزية)، ولكن ستكون العمليات مطابقة تمامًا. السمة المميزة لطريقة الترتيب بالجذر أننا نتعامل مع السلاسل على أنها سلاسل أبجدية رقمية لا سلاسل أرقام، حتى عندما تكون هذه السلاسل مؤلَّفة بالكامل من أرقام. إذا راجعت الطريقة التي اتبعناها، فسترى أننا لم نهتم بقيم الأعداد، ولكننا في كل مرة نتعامل مع حدٍّ معيَّن من حدود العدد، بالطريقة نفسها التي كنا سنتبعها عن طريق استخراج الحروف من كلمةٍ ما متجهين من اليمين إلى اليسار. ولذلك يُطلق على الترتيب بالجذر في بعض الأحيان اسم «طريقة الترتيب بالسلسلة».

لا تدع تلك العبارة تخدعك وتجعلك تظن أن الترتيب بالجذر يمكن أن يرتِّب السلاسل بينما طرق الترتيب الأخرى التي تناولناها في هذا الكتاب لا تستطيع ذلك. كل الطرق يمكنها فعل ذلك. يمكننا ترتيب السلاسل ما دام يمكن ترتيب الرموز نفسها التي تتكوَّن منها. إن أسماء البشر هي سلاسل بالنسبة إلى الكمبيوتر، ومِن ثَم يمكننا ترتيبها لأن الحروف مرتَّبة أبجديًّا والأسماء يمكن مقارنتها معجميًّا. لقد جاء مسمَّى «الترتيب بالسلسلة» من كون الترتيب بالجذر يعامل كل المفاتيح، حتى الأرقام، باعتبارها سلاسل. أما طرق الترتيب الأخرى المذكورة في هذا الفصل فتُعامِل الأرقام كأرقام والسلاسل كسلاسل، وتعمل عن طريق مقارنة الأرقام أو السلاسل حسبما يقتضي الأمر. ونحن نستخدم الأرقام باعتبارها مفاتيح في الأمثلة التي نقدِّمها في مختلف خوارزميات الترتيب من باب التيسير ليس إلا.

تكمُن فاعلية طريقة الترتيب بالجذر في أنها تعالج العناصر المراد ترتيبها حدًّا بحدٍّ (أو حرفًا بحرف). فإذا كان لدينا من العناصر نريد ترتيبها، وتتكوَّن العناصر من من الحدود أو الحروف، فإن تعقيد الخوارزمية يساوي . وهذا التعقيد أفضل بكثير من المطلوب في الترتيب الانتقائي أو الترتيب بالإدراج.

وها قد عُدنا إلى آلات الجدولة. كانت آلة الجدولة تعمل بطريقةٍ مشابهة لترتيب البطاقات المثقبة. تخيَّل أن لدينا مجموعة من البطاقات في كلٍّ منها عشرة أعمدة، وتشير الثقوب في كل عمود منها إلى رقم معيَّن. كانت الآلة تستطيع التعرُّف على الثقوب في كل عمود، وبذلك تتعرَّف على الرقم المطابق لها. وكان عامل التشغيل يضع البطاقات في الآلة، وتضع الآلة بدورها البطاقات في عشرة صناديق مخرجات اعتمادًا على العمود الأخير منها؛ أي أقل أرقامها أهميةً. كان عامل التشغيل يجمع البطاقات من صناديق المخرجات، مع الحرص على ألَّا يخلطها بأي حال، ويضعها مرة أخرى في الآلة وفي هذه المرة يوزِّعها في صناديق المخرجات باستخدام الرقم قبل الأخير؛ أي الرقم المجاور لأقل الأرقام أهمية. بعد تكرار هذه العملية عشر مرات، كان عامل التشغيل يستطيع جمع مجموعات من البطاقات المرتَّبة. وهذا هو المطلوب.

الترتيب السريع

لنفترض أن لدينا مجموعة من الأطفال يلهون في ساحة ما (ربما في المدرسة) وتريد أن توقفهم صفًّا، من الأقصر إلى الأطول. في البداية، نطلب منهم الوقوف في صفٍّ وهو ما سيفعلونه بأي ترتيب يشاءون:

الآن، نختار طفلًا بصورة عشوائية:

نخبر الأطفال أن يتنقلوا بحيث يتحرَّك كل الأطفال الأقصر من الطفل المختار جهة اليسار وباقي الأطفال جهة اليمين. في الشكل التالي، نوضِّح أين وقف الطفل المختار في النهاية، ويمكنك التحقُّق من أن الأطفال الأطول يقفون إلى يمينه والأقصر يقفون إلى يساره:

لم نطلب من الأطفال الوقوف بالترتيب الصحيح. لم نطلب منهم سوى التحرُّك نحو الطفل الذي اخترناه. ومِن ثَم شكلوا مجموعتين، إحداهما إلى يسار الطفل المختار والأخرى إلى يمينه. لا يقف الأطفال في هاتين المجموعتين بأي تسلسل من الأقصر إلى الأطول. لكننا نعلم يقينًا أن طفلًا «واحدًا» يقف في الموضع النهائي له في الصف الذي نحاول تكوينه؛ ذلك الطفل الذي اخترناه. كل الأطفال الواقفين إلى يساره أقصر منه، وكل الأطفال الواقفين إلى يمينه أطول منه. نطلق على الطفل الذي اخترناه «المحور»؛ لأن بقية الأطفال يتحركون حوله.

وكوسيلة مساعدة بصرية، نتَّبع طريقة تلوين الأطفال الذين يقفون في أماكنهم الصحيحة باللون الأبيض. وعندما نختار طفلًا كي يكون المحور، سنلوِّنه باللون الأسود؛ وعندما يتحرك بقية الأطفال حول المحور، سنستخدم قبَّعة سوداء صغيرة للإشارة إلى الموضع النهائي للمحور (الملوَّن بالأبيض؛ لأنه في المكان الصحيح ورأسه باللون الأسود للإشارة إلى أنه المحور).

الآن، نحوِّل انتباهنا إلى مجموعة من المجموعتين — جهة اليمين أو اليسار — ولنقُل المجموعة جهة اليسار. مرة أخرى، نختار محورًا عشوائيًّا في تلك المجموعة:

نطلب من الأطفال في تلك المجموعة أن يفعلوا الشيء نفسه الذي فعلوه من قبل: التحرُّك بحيث ينتقلون إلى يسار المحور، إذا كانوا أقصر، ونحو اليمين إذا كانوا أطول. مرة أخرى، سيصبح لدينا مجموعتان جديدتان أصغر، كما يمكنك أن ترى أدناه. إحدى المجموعتين مكوَّنة من طفل واحد؛ ومِن ثَم يقف الطفل في الموضع الصحيح في تلك المجموعة الصغيرة. ومِن ثَم يكون بقية الأطفال واقفين على يمين المحور الثاني. يقف المحور الثاني في المكان الصحيح، حيث يقف كل الأطفال الأقصر إلى يساره والباقون جميعًا إلى يمينه. المجموعة جهة اليمين تمتد إلى المحور الأول. عندها نختار محورًا جديدًا ثالثًا من تلك المجموعة.

عندما نخبر الأطفال في المجموعة أن يتحركوا مثل المرة السابقة، حسب طولهم بالنسبة إلى المحور الثالث، ستتكوَّن مجموعتان صغيرتان. نركِّز على المجموعة جهة اليسار. ونفعل كما فعلنا في السابق. نختار محورًا — رابعًا — ونطلب من الأطفال في هذه المجموعة المكوَّنة من ثلاثة أن يتحركوا حول هذا المحور.

عندما يفعلون ذلك، ينتهي الأمر بالمحور إلى أن يصبح الأول بين الثلاثة، ومِن ثَم تتبقى لدينا مجموعة مكوَّنة من طفلين على يمين المحور. نختار واحدًا من الاثنين ليكون محورًا، وسيتحرك الطفل الآخر، إذا لزم الأمر، إلى يمين المحور.

يتبيَّن أن هذا الطفل ليس بحاجة إلى الانتقال من مكانه على الإطلاق. وهكذا نكون قد تمكَّنا الآن من ترتيب نصف الأطفال تقريبًا؛ علمًا بأن هناك مجموعتين تركناهما عندما كنَّا نتعامل مع المحاور السابقة. نعود إلى المجموعة الأولى منهما من اليسار حتى نختار محورًا ونكرِّر العملية.

مرة أخرى، لا حاجة إلى التحرُّك من الموضع؛ ومِن ثَم ننتقل إلى المجموعة الأخيرة من الأطفال الذين لم يُرتَّبوا لنختار محورًا من بينهم.

يصبح لدينا مجموعة مكوَّنة من طفل واحد على يمين المحور، ومجموعة مكوَّنة من طفلين على يسار المحور. نركِّز على المجموعة جهة اليسار ونختار المحور الأخير من الطفلين.

ها قد انتهينا. وصار الأطفال يقفون بترتيب حسب طول القامة.

لنوضِّح ما قمنا به. لقد تمكَّنا من ترتيب الأطفال عن طريق وضع طفل واحد في موضعه الصحيح في كل مرة. وللقيام بذلك، لم نحتَج إلا إلى مطالبة بقية الأطفال بأن يتحركوا حول ذلك الطفل. بالطبع سوف تؤتي هذه الطريقة ثمارها دائمًا، ليس مع الأطفال فحسب، بل مع أي شيء نريد ترتيبه. فإذا كان لدينا مجموعة من الأعداد يمكن ترتيبها، يمكننا اتِّباع عملية مماثلة، وذلك باختيارِ عددٍ ما عشوائيًّا، وننقل بقية الأعداد حوله بحيث ينتهي المآل بالأعداد الأصغر قبل الرقم المختار والأعداد الأكبر بعده. سنكرِّر العملية في المجموعات الأصغر التي تكوَّنت؛ وفي النهاية، سنجد كل الأعداد في الترتيب الصحيح. وهذه العملية هي أساس خوارزمية «الترتيب السريع».

يعتمد الترتيب السريع على ملاحظة أنه إذا أمكن وضع عنصر واحد في الموضع الصحيح بالنسبة إلى بقية العناصر — بغض النظر عن مكان هذا الموضع — ثم تكرار العملية مع بقية العناصر، فسينتهي الأمر بوضع جميع العناصر في مواضعها الصحيحة. إذا عُدنا بالذاكرة إلى ما قمنا به في عملية الترتيب الانتقائي، فسنجد أننا أخذنا كل عنصر من العناصر أيضًا ووضعناه في المكان الصحيح بالنسبة إلى بقية العناصر، ولكن العنصر الذي أخذناه كان العنصر الأصغر دومًا من بين العناصر المتبقية. وهذا فرقٌ بالغ الأهمية؛ ففي الترتيب السريع، «لسنا» بحاجةٍ إلى اختيار العنصر الأصغر من بين العناصر المتبقية ليكون المحور. لِنرَ ما سيحدث إذا قمنا بذلك.

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

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

وبالقيام بالأمر نفسه مع الطفل الثالث، نحصل على الصورة التالية:

لكن لاحظ مدى التشابه الغريب لهذا مع الفرز الانتقائي؛ إذ إننا نرتِّب الصف من اليسار إلى اليمين بدءًا من الطفل الأقصر بين الأطفال المتبقين.

لم نذكر كيف اخترنا عنصرًا في كل مرة كي يكون المحور. نرى الآن أننا لسنا مضطرين إلى اختيار العنصر الأصغر من بين العناصر. أولًا: لأن اختيار العنصر الأصغر يتطلب جهدًا؛ إذ علينا أن نبحث في كل مرة عن العنصر الأصغر ونجده. ثانيًا: تلك العملية تسير على نهج خوارزمية نعرفها بالفعل، ومِن ثَم لا يُفترض أن تكون هناك فائدة كبيرة تُرجى من القيام بذلك.

الحقيقة أن الترتيب السريع أفضلُ من الترتيب الانتقائي؛ لأننا «بطبيعة الحال» (وسنعرف المقصود بكلمة بطبيعة الحال بعد قليل) سوف نختار محورًا يقسم البيانات التي لدينا بطريقةٍ أكثر تساويًا. أما اختيار العنصر الأصغر فيؤدي إلى قسمة غير متساوية إلى أقصى حدٍّ؛ إذ لا توجد عناصر على يسار المحور، وكل العناصر المتبقية توجد على يمين المحور. ومِن ثَم لا نتمكَّن إلا من تحديد موضع المحور نفسه في كل مرة.

أما إذا كانت القسمة متساوية أكثر، فإننا لا نتمكَّن من تحديد موضع المحور فحسب. بل نتمكَّن أيضًا من تحديد المواضع الصحيحة لجميع العناصر على يسار المحور «بالنسبة إلى العناصر الواقعة على يمين المحور». صحيح أن تلك العناصر ليست في مواضعها النهائية بعد. ولكنها بوجه عام في مواضع أفضل من ذي قبل. وهكذا يكون لدينا عنصر واحد — المحور — في أفضل موضع ممكن، والعناصر الأخرى في مواضع أفضل من ذي قبل.

ولهذا الأمر تأثيرٌ مهم في أداء خوارزمية الترتيب السريع؛ فتعقيد الخوارزمية المتوقَّع يساوي وهو أفضل بكثير من التعقيد . فإذا أردنا ترتيب مليون عنصر، تتحوَّل إلى ١٠^١٢ أي تريليون، ولكن تساوي نحو ٢٠ مليونًا.

يعتمد الأمر برُمَّته على اختيار المحور المناسب. فليس من المنطق أن نبحث في كل مرة عن محورٍ يقسم البيانات بأفضل طريقة ممكنة؛ إذ سيتطلب الأمر البحث لإيجاد المحور المناسب، ما يضيف مزيدًا من التعقيد إلى العملية. إذن، فالاستراتيجية الجيدة هي ترْك الأمر إلى الحظ. ما علينا سوى اختيار محور عشوائي واستخدامه لتقسيم البيانات.

كي نعرف السببَ وراء صلاحية هذه الاستراتيجية، لِنرَ أولًا الأسباب التي تجعلها غير سيئة. ستكون استراتيجية سيئة لو أدَّت إلى سلوك يشبه السلوك الذي رأيناه لتوِّنا لما تحوَّل الترتيب السريع إلى ترتيب انتقائي. وهو ما قد يحدث إذا انتقينا المحور في كل مرة من عنصر لا يقسم العناصر بالتساوي فعليًّا. ويمكن أن يحدث ذلك الأمر إذا انتقينا في كل مرة العنصر الأصغر أو الأكبر من بين العناصر (الموقف سيان). ويمكن أن تبلغ الاحتمالية الإجمالية لحدوث كل هذا .

يصعب استيعاب احتمالية بقيمة ؛ لأنها منخفضة إلى أقصى الحدود. وكي نوضِّحها بالسياق، إذا أخذت مجموعة مكوَّنة من ٥٢ ورقة لعب وخلطتها عشوائيًّا، فإن احتمالية أن تصبح المجموعة مرتَّبة في النهاية تساوي ١ / ٥٢! هذا الأمر مشابه تقريبًا لقذف عملة معدنية وإنزالها على الصورة ٢٢٦ مرة على التوالي. وعندما تضرب في ، لا تتحسَّن الأمور كثيرًا. فالعدد !٢^٥١ / ٥٢ يساوي تقريبًا ٢٫٨ × ١٠^−٥٣. ولوضع المسألة في منظور كونيٍّ، تتكوَّن الأرض من ١٠^٥٠ ذرة تقريبًا. إذا كان عليك أن تنتقي أنت وأحد أصدقائك ذرةً من الأرض كلٌّ بمفرده، فإن احتمالية أن تنتقيا الذرة نفسها تساوي ١٠^−٥٠، وتلك القيمة فعليًّا أكبر من !٢^٥١ / ٥٢؛ وهي احتمالية الترتيب السريع غير العادية بشأن مجموعة بطاقات اللعب.⁴

بذلك يتضح أننا «بطبيعة الحال» نختار محورًا يقسم المسألة بطريقة أكثر تساويًا، كما ذكرنا من قبل. وباستثناء سلسلة الحظ السيئ بشأن النسب الكونية، فإننا لا نتوقَّع أن نختار أسوأ محور ممكن في كل مرة. فالاحتمالات، في واقع الأمر، تصب في صالحنا أكثر؛ فباختيار المحاور عشوائيًّا، نتوقَّع أن تكون قيمة التعقيد . من الناحية النظرية، يُحتمل أن يكون التعقيد أسوأ من ذلك، ولكن أهمية الاحتمالية هي أهمية أكاديمية فحسب. وستعمل خوارزمية الترتيب السريع بالسرعة التي نتوقَّعها لجميع الأغراض العملية.

الترتيب بالدَّمج

تعرَّفنا على خوارزمية الترتيب بالجذر التي ترتِّب العناصر بالأساس عن طريق التوزيع؛ حيث تضع كلَّ عنصر في مجموعته الصحيحة في كل دورة ترتيب للبيانات. والآن، سنتناول طريقةَ ترتيبٍ أخرى ترتِّب العناصر عن طريق «دمجها» معًا بدلًا من تقسيمها. الطريقة تسمَّى «الترتيب بالدَّمج».

تبدأ خوارزمية الترتيب بالدَّمج بالتسليم بقدرتها المحدودة على الترتيب والتصنيف؛ تخيَّل أننا لا نستطيع ترتيب العناصر إذا أُعطيت لنا بأي ترتيب عشوائي. ليس بمقدورنا سوى القيام بالتالي: إذا كان لدينا مجموعتان من العناصر، وكل مجموعة مرتَّبة بالفعل، يمكننا دمجهما معًا والحصول على مجموعة واحدة مرتَّبة.

على سبيل المثال، لنقُل إن لدينا المجموعتين التاليتين، واحدة في كل صف (على الرغم من أن المجموعتين في المثال لهما العدد نفسه من العناصر، فلا يلزم أن تكون المجموعتان بالحجم نفسه):

كما ترى، كل مجموعة من المجموعتين مرتَّبة بالفعل. نريد دمج المجموعتين من أجل الحصول على مجموعةٍ واحدة مرتَّبة. وهذه عملية بسيطة للغاية. نتحقَّق من العنصر الأول في كل مجموعة. فنجد أن ١٥ أصغر من ٢١، ومِن ثَم سيكون هذا هو العنصر الأول في المجموعة الثالثة التي نعمل على تكوينها:

نتحقَّق مرة أخرى من العناصر الأولى في المجموعتين، وفي هذه المرة، نرى أن العدد ٢١ في المجموعة الثانية أصغر من العدد ٢٧ في المجموعة الأولى. ومِن ثَم نأخذ العدد ونُلحِقه بالمجموعة الثالثة.

إذا واصلنا على هذه الوتيرة، فسنأخذ العدد ٢٧ من المجموعة الأولى، ثم ٣٥ من المجموعة الثانية ونضيفهما إلى نهاية المجموعة الثالثة كما يلي:

الآن، ٥١ أصغر من ٥٩، وكذلك ٥٦ أصغر من ٥٩. وبما أننا بالفعل نقلنا العدد ٣٥ من المجموعة الثانية إلى الثالثة، نكون في النهاية قد نقلنا ثلاثة عناصر متتالية من المجموعة الثانية إلى الثالثة. وهذا شيء رائع؛ لأننا بذلك نحافظ على العناصر في المجموعة الثالثة مرتَّبة. فما من سببٍ يستدعي تقليل حجم أول مجموعتين بالمعدَّل نفسه.

نعود إلى المجموعة الأولى، حيث العدد ٥٩ أصغر من ٦٩، ومِن ثَم نضيفه إلى المجموعة الثالثة:

بعد ذلك، وبنقل العدد ٦٩ إلى المجموعة الثالثة، نكون قد أفرغنا المجموعة الثانية بالكامل:

ننهي العملية بنقل آخر العناصر المتبقية من المجموعة الأولى إلى المجموعة الثالثة، التي هي قطعًا أكبرُ من العنصر الأخير في المجموعة الثالثة، وإلَّا لما نقلناه هناك أولًا. ها قد صارت جميع العناصر مرتَّبة الآن:

جميل أن تكون هناك طريقة لإخراج مجموعة مرتَّبة من مجموعتين مرتَّبتين، ولكن لا يبدو أن تلك الطريقة تقدِّم حلًّا لمسألة ترتيب مجموعة واحدة ذات عناصر غير مرتَّبة. صحيح أنها لا تقدِّم حلًّا، ولكنها عنصر مهم من عناصر الحل.

تخيَّل الآن أن لدينا مجموعة من الأشخاص. أعطينا واحدًا منهم مجموعة عناصر كي يرتِّبها. هذا الشخص لا يعرف طريقة الترتيب، ولكنه يعلم جيدًا أنه إذا كان لديه جزءان من هذه العناصر مرتَّبان بصورة أو بأخرى، يمكنه أن يُخرِج منهما مجموعةً مرتَّبة في النهاية. ومِن ثَم سيفعل ذلك الشخص ما يلي: سيقسم المجموعة إلى جزأين ويعطيهما لشخصين آخرين. يقول للأول منهما: «خذ تلك المجموعة ورتِّبها. وبمجرد أن تنتهي، أعِدْها إليَّ.» ويقول الشيءَ نفسه للشخص الثاني. ثم ينتظر.

إن الشخص الأول لا يعرف كيف يرتِّب العناصر، ولكن إذا نجح الشخصان الآخران بصورةٍ ما في ترتيب الجزأين اللذين معهما وأعاداهما إليه، فسيعيد لنا الشخص الأول المجموعة النهائية المرتَّبة بالكامل. لكن الشخصين الآخرين لا يعرفان أكثرَ مما يعرفه الشخص الأول — إنهما لا يعرفان كيفية الترتيب، بل فقط يعرفان طريقة دمج عناصر مرتَّبة باستخدام الخوارزمية الواردة أعلاه — إذن هل تُوصِّل إلى أي شيء؟

الإجابة نعم، بشرط أن يفعل كلٌّ منهما ما قام به الأول: يقسم كلُّ واحد منهما الجزء الذي معه إلى جزأين، ويعطي كلٌّ منهما الجزأين اللذين معه إلى شخصين آخرين، ثم ينتظرانهما حتى يفعل كلُّ شخصٍ ما أُسند إليه ويعطيانه الجزأين وقد رُتِّبا.

الأفراد عند مستوى أوراق الشجرة ليس لديهم ما يفعلونه في الحقيقة. فكلٌّ من بيجي وكوينتين يتلقيان عددًا واحدًا ويُطلب منهما ترتيبه. ولكن عددًا واحدًا لا يحتاج إلى الترتيب بطبيعة الحال؛ فهو مرتَّب بذاته. ومِن ثَم يعيد بيجي وكوينتين العددين إلى هيدي. وكذلك يعيد إيفان وجودي وكارين وسيبيل ومالوري ونيك وأوليفيا الأعداد التي تلقَّوها.

لننتقل الآن إلى الشجرة التالية. في هذه الشجرة، سننتقل من الأوراق في القمة (ولهذا تبدو هذه الشجرة عادية وليست مقلوبة) إلى الجذور في الأسفل. لنركِّز على هيدي. تستعيد هيدي عددين، رُتِّب كلٌّ منهما (بلا أي قيمة تُذكر). تعرف هيدي كيف تَدمُج مجموعتين مرتَّبتين لإنشاء مجموعةٍ واحدة، ومِن ثَم تستطيع استخدام العددين ٩٥ و٥٩ لتُنشِئ المجموعةَ ٥٩ و٩٥. بعد ذلك تعيد تلك المجموعة المرتَّبة المكوَّنة من عددين إلى ديف. سيفعل ليو الأمر نفسه: سيحصل على العددين ٣٥ و٥٦ المرتَّبين بالفعل (تلقائيًّا) ويعلم كيف يرتِّب هذين العددين ويُنشِئ المجموعةَ ٣٥ و٥٦ ويعيدها إلى فرانك.

لا يملك ديف أدنى فكرة عن الأعداد ٩٥ و٥٩ و١٥ التي تلقاها في البداية؛ إذ تلقَّى ٥٩ و٩٥ من هيدي و١٥ من إيفان. كلتا هاتين المجموعتين مرتَّبة بالفعل، ما يعني أن ديف يمكنه دمجهما وتكوين المجموعة ١٥ و٥٩ و٩٥. وبالطريقة نفسها، يحصل فرانك على العددين ٣٥ و٥٦ من ليو وعلى العدد ٥١ من مالوري ويمكنه تكوين المجموعة ٣٥ و٥١ و٥٦.

إذا تصرَّف كلُّ فرد بالطريقة نفسها، فسيصبح لدى أليس، عندما تصلها الأعداد، قائمتان مرتَّبتان، إحداهما من كارول والأخرى من بوب. عندئذٍ ستدمج القائمتين لإنشاء القائمة النهائية المرتَّبة.

هاتان الشجرتان هما جوهر الترتيب بالدَّمج. نسند عملية الترتيب إلى أكبر عدد ممكن حتى لا يمكن إجراء الترتيب؛ لأن العناصر المفردة عناصر مرتَّبة بطبيعة الحال. ثم ندمج مجموعاتٍ أكبر وأكبر إلى أن نستوعب كل العناصر في مجموعة واحدة نهائية مرتَّبة.

مقدار الذكاء المطلوب من الشخصيات قليل جدًّا. يمكنك أن ترى في الشجرة الأولى أن إيف تلقَّت من بوب مجموعةَ أعداد تصادف أنها مرتَّبة بالفعل: ٢٧ و٨٢. هذا لا يهم. فهي لا تتوقَّف عن التحقُّق ممَّا إذا كانت المجموعة بحاجة إلى ترتيب من عدمه، ونحن لا نريدها أن تفعل ذلك؛ لأن مثل هذا التحقُّق سيستغرق وقتًا. كل ما تفعله هو تقسيم العناصر وتمريرها إلى شخصٍ آخر. وستستعيدها وتدمجها لإنشاء المجموعة التي كانت معها بالفعل. لا بأس؛ في المخطَّط الأكبر للعناصر، لن يؤثِّر هذا التعاون غير المبرَّر بين إيف وجودي وكارين في أداء الخوارزمية.

تعقيد خوارزمية الترتيب بالدمج جيدٌ مثل خوارزمية الترتيب السريع؛ إذ يساوي . وهذا يعني أن لدينا خوارزميتين لهما الأداء نفسه. وفي الجانب العملي، قد يختار المبرمجون إحداهما أو الأخرى بناءً على عوامل أخرى إضافية. وعادةً ما تكون برامج الترتيب السريع أسرع من برامج الترتيب بالدمج نظرًا لسرعة تنفيذها الفعلي في لغة البرمجة. أما الترتيب بالدمج فيقسِّم البيانات قبل دمجها، ما يعني أنه يمكن تشغيلها في عمليات متوازية، بحيث يمكن ترتيب كميات هائلة من البيانات باستخدام مجموعة من أجهزة الكمبيوتر، حيث يعمل كل جهاز مثل الشخصيات في مثال الترتيب الموضَّح آنفًا.