فرز بالدلاء

الترميز الوصفي

علاوةً على ذلك، يؤدي استخدام bucketSort (المبينة أعلاه داخل الصندوق الوصفي) كدالة nextSort، إلى إنشاء نوع قريب من خوارزمية الترتيب المنازلي ، وفي حالة ما إذا كانت n = 2 فإنها تُقابل في هذه الحالة الخاصة خوارزمية الترتيب السريع وإن كان ذلك قد يتم باختيار محاور غير جيدة.

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

من جانب آخر، الدالة nextSort هي دالة ترتيب تُستعمل لترتيب كل دلو على حدة. تقليديا، من المعتاد استخدام الترتيب بالإدراج ، ولكن يمكن استخدام خوارزميات أخرى كذلك، مثل خوارزمية الترتيب الانتقائي أو خوارزمية الترتيب بالدمج .

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

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

حيث يُفرز البريد أولًا إلى محلي ودولي،

ثم حسب خطوط التوزيع، وهكذا.

ثم حسب الولاية أو المقاطعة أو الإقليم،

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

ثم حسب مكتب البريد الوجهة،

من جهة ثانية، هذه هي الخوارزمية التي تستعملها آلات فرز الرسائل في مكاتب البريد:

من جانب آخر، وبما أن المفاتيح لا تُقارن فيما بينها مباشرة، فإن الزمن اللازم للترتيب هو O( cn )، حيث تعتمد c على حجم المفتاح وعدد الدلاء.

الترتيب بالمجموعة التمهيدية

وفي السياق ذاته، بعدها تُوزع الـ 7/8 من العناصر المتبقية على الدلاء السابقة التي تم إنشاءها من أول 1/8 من العناصر، ثم يُرتب كل "دلو" على حده.

وفي السياق ذاته، الترتيب بالمجموعة التمهيدية أو الترتيب بالخلط هو أحد أشكال خوارزمية الترتيب بالدلاء والذي يبدأ بإزالة أول 1/8 من العناصر n المطلوب ترتيبها، ثم تُرتب هذه العناصر بشكل متكرر وتُوضَع في مصفوفة، وهذا يُنشئ عدد n /8 من الدلاء.

وفي النهاية تُدمج جميع الدلاء في مصفوفة واحدة مُرتبة.

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

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

المراجع

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

كذلك، مكن اعتبار الترتيب بالدلو بمثابة تعميم للترتيب بالعد ؛ في الواقع، إذا كان حجم كل دلو 1، فإن ترتيب الدلو يتحول إلى ترتيب بالعدّ. يسمح حجم الدلو المتغير لترتيب الدلو باستخدام ذاكرة O( n ) بدلاً من ذاكرة O( M )، حيث M هو عدد القيم المميزة؛ في المقابل، فإنه يتخلى عن حساب أسوأ سلوك للترتيب O( n + M ).

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

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

من جهة ثانية، تختلف خوارزمية الترتيب بخريطة التقارب عن خوارزميات الترتيب بطريقة الدلو من حيث أنها تستعمل "مفتاح الخريطة" لتحديد الموضع التقريبي للبيانات في الترتيب النهائي، فتُنتِ بذلك "خريطة التقارب" أي المواضع التقريبية التي ينبغي أن توضع فيها تلك المفاتيح مُرتبة.

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

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

تحليل أسوأ حالة

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

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

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

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

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

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

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

من جهة ثانية، تعمل الصيغة المألوفة والأوسع استخدامًا لخوارزمية الترتيب بالدلاء، على قائمة مكونة من عدد n من المدخلات الرقمية قيمهم تتراوح بين الصفر وبعض القيم القصوى M، ويُقسَّم المجال العددي إلى عدد b من الأقسام المتساوية، حجم كل منها يساوي M / b.

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

وفي السياق ذاته، هذا التدهور في الأداء لا يحدث في خوارزمية فرز الدلاء الأصلية، لأنها تفترض أن المُدخلات (البيانات) موزعة توزيعًا عشوائيًا منتظمًا خلال الفترة [0،1).

طريقة عمل الخوارزمية

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

الخوارزمية المستعملة لترتيب محتويات كل دلو،

من جهة ثانية، التجميع : المرور على الدلاء بالترتيب، وإعادة جميع العناصر مرة أخرى ووضعها في المصفوفة الأصلية.

وعدد الدلاء التي يجب استخدامها،

يعتمد مدى تعقيد التحليل الحسابي لهذه اخوارزمية على:

التحسينات

أنواع فرعية من الترتيب بالدلاء

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

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

وفي هذا السياق، إحدى التحسينات الشائعة هي إعادة العناصر غير المُرتبة من الدلاء إلى المصفوفة الأصلية أولاً، ثم تنفيذ الترتيب بالإدراج على المصفوفة بالكامل:

التحليل في الحالات العادية

ولذلك،

يصبح لدينا عدد العناصر في الدلو يساوي: .

من جانب آخر، وبما أن احتمال توزيع أحد المدخلات إلى الدلو هو ، فإن سوف تساوي 1 باحتمالية ، وفي غير ذلك سوف تساوي 0.

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

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

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

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

من جهة ثانية، وبما أننا نريد حساب بالوقت المتوسط، فيجب تقييم التوقع الرياضي: بدلًا من القيمة الفعلية.

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

طريقة التحليل

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

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

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

وبإجراء عملية الجمع، سيكون لدينا

لذلك، فإن "إجمالي تعقيد العملية" سيكون .

في هذا الإطار، لاحظ أنه إذا تم اختيار k بحيث تكون ، فإن خوارزمية الترتيب بالدلاء ستعمل في متوسط زمن مقداره ، بشرط أن تكون المُدخلات موزعة توزيعًا منتظمًا.

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

وأخيرا، فإن "تعقيد العملية" سيكون: