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

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

ثمانية مسارات من الأعمدة، مسار لكل خوارزمية ترتيب، بعضها مرتب بالفعل وأخضر وبعضها لا يزال غير مرتب
ثمانية مسارات من الأعمدة، مسار لكل خوارزمية ترتيب، بعضها مرتب بالفعل وأخضر وبعضها لا يزال غير مرتب

ثلاث عائلات

الترتيب الفقاعي والترتيب بالاختيار والترتيب بالإدراج هي خوارزميات الترتيب البسيطة. تقارن القيم المتقاربة وتبدّلها، وتحتاج إلى زمن يتناسب مع n² على قائمة عشوائية. أما الترتيب بالدمج والترتيب السريع والترتيب بالكومة فتقسّم العمل بذكاء وتحتاج إلى زمن يتناسب مع n log n، وهو أفضل ما يمكن لأي خوارزمية ترتيب إذا كان كل ما تستطيع سؤاله هو أي القيمتين أكبر. ويتجاوز ترتيب الجذر والترتيب بالعد هذا السؤال كليًا: فهما يستخدمان الخانات أو القيم نفسها، وهذا لا يصلح إلا لمفاتيح مثل الأعداد الصحيحة الصغيرة.

قياس العمل

يحسب سباق الترتيب عملية واحدة لكل مقارنة، ولكل قراءة لخانة أو قيمة، ولكل تبديل أو نقل. على 40 قيمة عشوائية يبلغ ذلك نحو 120 للترتيب بالعد، و240 لترتيب الجذر، و260 للترتيب السريع، و380 للترتيب بالدمج، و490 للترتيب بالكومة، ونحو 820 لكل من الترتيب بالاختيار والترتيب بالإدراج، وأكثر من 1,100 للترتيب الفقاعي. والحواسيب الحقيقية تتأثر أيضًا بالذاكرة: فالترتيب السريع عادةً أسرع عمليًا مما يوحي به عدده، والترتيب بالكومة أبطأ، بسبب طريقة تنقّلهما في القائمة.

المدخلات مهمة

على قائمة شبه مرتبة من 40 قيمة، لا يحتاج الترتيب بالإدراج إلا إلى نحو 50 عملية والترتيب الفقاعي إلى نحو 90، لأن كل قيمة قريبة من مكانها. وعلى قائمة معكوسة يحتاج كلاهما إلى 1,560، وهي أسوأ حالة لهما. ولا يكاد الترتيب بالاختيار والترتيب بالكومة والترتيب بالدمج وترتيب الجذر والترتيب بالعد تتأثر بالترتيب الأولي. يتعامل الترتيب السريع بوسيط ثلاث قيم جيدًا مع القوائم المرتبة والمعكوسة، لكن مع محور ساذج تصبح القائمة المرتبة أسوأ حالة له. وقلة القيم المختلفة تبطئ الترتيب السريع، لأن القيم المتساوية تذهب كلها إلى جهة واحدة.

الذاكرة والاستقرار

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

أيها تستخدم

عمليًا تستخدم دالة الترتيب المضمّنة في لغة البرمجة التي تعمل بها: عادةً Timsort، وهو ترتيب بالدمج يستخدم الترتيب بالإدراج للقطع القصيرة وسريع على البيانات المرتبة جزئيًا، أو introsort، وهو ترتيب سريع يتحول إلى الترتيب بالكومة عند الحاجة ويستخدم الترتيب بالإدراج للأجزاء الصغيرة. ومع كثير من المفاتيح الصحيحة الصغيرة، قد يتفوق الترتيب بالعد أو ترتيب الجذر على كليهما. أما الترتيب الفقاعي والترتيب بالاختيار فهما في الغالب أداتان للتعليم.

جرّبه بنفسك

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

الأسئلة المتداولة

ما أسرع خوارزمية ترتيب؟

للبيانات العامة، الترتيب السريع والترتيب بالدمج (والخوارزميات الهجينة المبنية عليهما مثل introsort وTimsort) هي الأسرع في المتوسط، بزمن n log n. وللمفاتيح الصحيحة الصغيرة، الترتيب بالعد وترتيب الجذر أسرع من ذلك. وللقوائم القصيرة أو شبه المرتبة، يفوز الترتيب بالإدراج.

لماذا لا يمكن لأي ترتيب بالمقارنة أن يتفوق على n log n؟

يمكن أن تكون قائمة من n قيمة في n! ترتيبًا، ولكل مقارنة نتيجتان، لذا يلزم في أسوأ حالة log₂(n!) مقارنة على الأقل للتمييز بينها جميعًا. وهذا يساوي تقريبًا n log₂ n. ويتجنب ترتيب الجذر والترتيب بالعد هذا الحد لأنهما لا يقارنان.

أي خوارزميات الترتيب مستقرة؟

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

أي خوارزميات الترتيب تحتاج إلى ذاكرة إضافية؟

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

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

ابدأ سباق الترتيب