خوارزميات الترتيب

خوارزميات الترتيب Sorting Algorithms هي خوارزميات تستخدم لإعادة ترتيب مصفوفة معطاة أو قائمة من العناصر بالاعتماد على عامل مقارنة معيّن. يُستخدم عامل المقارنة لتحديد ترتيب العناصر الجديد في بنية المعطيات المراد إعادة ترتيب عناصرها.

مصطلحات عملية الترتيب

الترتيب في نفس المكان

لا تستخدم خوارزمية الترتيب في نفس المكان in-place sorting مساحة إضافية ثابتة لإنتاج المخرجات (وذلك بتعديل المصفوفة المعطاة فقط)، وترتّب العناصر في هذه الطريقة بتعديل ترتيب العناصر في المصفوفة فقط، ومن الخوارزميات التي تعتمد هذه الطريقة خوارزميتا الترتيب بالإدراج Insertion Sort والترتيب بالتحديد Selection Sort وذلك لأنّها لا تستخدم أيّ مساحة إضافية لترتيب عناصر القائمة.

الترتيب الداخلي والترتيب الخارجي

عندما لا يكون بالإمكان وضع جميع البيانات التي تحتاج إلى ترتيب في الذاكرة، فإنّ عملية الترتيب تسمّى حينئذٍ بالترتيب الخارجي external sorting، وتستخدم هذه العملية مع الكميات الكبيرة جدًّا من البيانات.

تستخدم خوارزمية الترتيب بالدمج Merge Sort بأنواعها المختلفة في هذا النوع من عمليات الترتيب، ويمكن الاستفادة من مصادر تخزين خارجية مثل الأقراص الصلبة أو الأقراص المضغوطة لتخزين البيانات.

تكون عملية الترتيب داخلية Internal Sorting إن كان بالإمكان وضع البيانات التي تحتاج إلى ترتيب في الذاكرة.

الترتيب بالفقاعات

خوارزمية الترتيب بالفقاعات Bubble Sort هي أبسط خوارزميات الترتيب والتي تعمل على تبديل مواقع العناصر المتجاورة إن كان ترتيبها خاطئًا.

الترتيب بالتحديد

ترتّب خوارزمية الترتيب بالتحديد selection sort المصفوفة عن طريق العثور على أصغر عنصر (بافتراض أنّ الترتيب سيكون ترتيبًا تصاعديًا) في الجزء غير المرتّب من المصفوفة ووضعه في بدايتها.

الترتيب بالإدراج

الترتيب بالإدراج Insertion Sort من خوارزميات الترتيب البسيطة التي تعمل بنفس الطريقة التي ترتّب فيها أوراق اللعب يدويًا.

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

تقسم خوارزمية الترتيب بالدمج Merge Sort المصفوفة المدخلة إلى نصفين، ثم تستدعي الخوارزمية نفسها على هذين النصفين ثم تدمج نصفي المصفوفة المرتبين بعضهما ببعض.

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

تنتقي عنصرًا من عناصر المصفوفة وتجعله محورًا pivot ثمّ تقسّم المصفوفة المعطاة حول ذلك العنصر.

الترتيب بالكومة

تستند خوارزمية الترتيب بالكومة Heap Sort على الكومة الثنائية Binary Heap، وهي مشابهة لخوارزمية الترتيب بالتحديد إذ نختار في البداية العنصر الأكبر في المصفوفة ونضعه في نهاية المصفوفة، وتعاد العملية على بقية العناصر.

الترتيب بالعد

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

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

تتلخص هذه الخوارزمية بإجراء ترتيب للعناصر رقمًا تلو الآخر بدءًا من الرقم الأقل أهمية إلى الرقم الأكثر أهمية.

خوارزمية شِل للترتيب

ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من h ، ثم تستمر في تقليص قيمة h إلى حين الوصول إلى 1.

الترتيب بالدلو

تظهر فائدة خوارزمية الترتيب بالدلو Bucket Sort عندما تكون المدخلات موزّعة بانتظام ضمن نطاق معيّن.

الترتيب ببرج الحمام

تلائم خوارزمية الترتيب ببرج الحمام Pigeonhole sort قوائم العناصر التي يكون فيها عدد العناصر وعدد القيم المفتاحية الممكنة possible key values متساويين تقريبًا.

الترتيب بالتدوير

مبدأ عمل خوارزمية الترتيب بالتدوير Cycle sort هو تدوير مواقع العناصر في المصفوفة إلى حين الحصول على مصفوفة مرتبة بالكامل.

الترتيب بالشجرة

تعتمد خوارزمية الترتيب بالشجرة Tree Sort في عملها على شجرة البحث الثنائية، إذ أنّها تصنع شجرة بحث ثنائية في البداية من العناصر المتوفّرة في المصفوفة المدخلة ثم تنفّذ عملية تنقل وسطي للحصول على العناصر مرتّبة.

الترتيب المخلوط

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

الترتيب فردي-زوجي (الترتيب بالقرميد)

خوارزمية الترتيب فردي-زوجي Odd-Even Sort (أو الترتيب بالقرميد Brick sort) هي تحوير على خوارزمية الترتيب بالفقاعات. تقسم هذه الخوارزمية إلى قسمين القسم الفردي والقسم الزوجي. تستمر الخوارزمية في عملها إلى أن تصبح جميع العناصر في المصفوفة مرتبة