فرز بالدلاء

يسار|إطار| ثم يتم ترتيب العناصر داخل كل صندوق على حِدة.

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

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

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

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

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

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

تصغير|302x302بك|عرض توضيحي متحرك لعمل خوارزمية الترتيب بالإدراج .

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

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

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

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

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

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

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

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

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

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

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

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

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

ولذلك،

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

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

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

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

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

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

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

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

ونظراً لأن زمن تنفيذ الترتيب بالإدراج يعتمد على مدى ابتعاد كل عنصر عن موضعه النهائي، فإن عدد المقارنات يظل صغيرًا نسبيًا، ويتم استغلال التسلسل الهرمي للذاكرة بشكل أفضل عن طريق تخزين القائمة بشكل متجاور في الذاكرة.Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort". Journal of Computing Sciences in Colleges, 20, 1, pp.197–202. October 2004.

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

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

 ترتيب عام بالدلاء 
تصغير|280x280بك|عرض رقمي لخوارزمية الترتيب بالإدراج .

القائمة المرتبة جزئيًا (باللون الأسود) تحتوي في البداية على العنصر الأول فقط من القائمة.

ومع كل تكرار ، يتم إزالة عنصر واحد (باللون الأحمر) من البيانات المدخلة التي لم تُفحص بعد من حيث الترتيب،

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

إذا تم ترتيب كل دلو باستخدام خوارزمية الترتيب بالإدراج، فيمكن إثبات أن الخوارزمية تعمل في زمن خطي متوقع، حيث يُؤخذ المتوسط على جميع المدخلات الممكنة.Thomas H. Cormen، Charles E. Leiserson، رونالد ريفست, and كليفورد شتاين. مقدمة في الخوارزميات (كتاب), Second Edition. MIT Press and McGraw-Hill, 2001. . Section 8.4: Bucket sort, pp.174–177.

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

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

 ترتيب بخريطة التقارب 
تصغير|280x280بك|عرض توضيحي لخوارزمية الترتيب بخريطة التقارب .

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

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

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

 ترتيب المدرج التكراري 
تصغير|280x280بك|رسم توضيحي لترتيب الدلاء باستخدام خوارزمية الترتيب بالمدرج التكراري .

هناك نوع آخر من خوارزمية الترتيب بالدلاء يُعرف باسم ترتيب المدرج التكراري  أو الترتيب بالعدّ ، يقوم بإضافة تمرير أوَّلي يعدّ فيه عدد العناصر التي ستقع في كل دلو، وذلك باستخدام مصفوفة عدّ .NIST's Dictionary of Algorithms and Data Structures: histogram sort 

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

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

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

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

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

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

 الترتيب بالمجموعة التمهيدية 
تصغير|277x277بك|عرض توضيحي متحرك لخوارزمية الترتيب بالمجموعة التمهيدية .

الترتيب بالمجموعة التمهيدية أو الترتيب بالخلط  هو أحد أشكال خوارزمية الترتيب بالدلاء والذي يبدأ بإزالة أول 1/8 من العناصر n المطلوب ترتيبها، ثم تُرتب هذه العناصر بشكل متكرر  وتُوضَع في مصفوفة، وهذا يُنشئ عدد n /8 من الدلاء.A revolutionary new sort from John Cohen Nov 26, 1997 

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

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

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

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

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

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

 المراجع 

 مصادر 
 بول إي. بلاك "ترتيب ساعي البريد" من قاموس الخوارزميات وهياكل البيانات في المعهد الوطني للمعايير والتكنولوجيا.
 روبرت رامي "صنف ساعي البريد" ، مجلة المستخدمين، أغسطس 1992م.
 قاموس NIST للخوارزميات وهياكل البيانات: الترتيب بالدلاء

 روابط خارجية 
 رمز الترتيب بالدلاء لـ Ansi C.
 متغير الترتيب بالدلاء مع العرض التوضيحي .

تصنيف:مقالات تحوي أمثلة مكتوبة بشبه رماز
تصنيف:خوارزميات فرز