فرز الدلو

عندما تحتوي المدخلات على عدة مفاتيح متقاربة (تجميع)، فمن المرجح أن تُوضع هذه العناصر في نفس المجموعة، مما ينتج عنه احتواء بعض المجموعات على عناصر أكثر من المتوسط. ويحدث أسوأ سيناريو عندما تُوضع جميع العناصر في مجموعة واحدة. عندها، سيتأثر الأداء العام بشكل كبير بالخوارزمية المستخدمة لفرز كل مجموعة، على سبيل المثال${\displaystyle O(n^{2})}$فرز الإدراج أو${\displaystyle O(n\log(n))}$خوارزميات فرز المقارنة ، مثل فرز الدمج .

لنفترض أن المدخلات موزعة بشكل منتظم. يمكن تنفيذ الخطوة الأولى، وهي تهيئة المجموعات وإيجاد قيمة المفتاح القصوى في المصفوفة، في${\displaystyle O(n)}$الوقت. إذا أمكن إجراء القسمة والضرب في وقت ثابت، فإن توزيع كل عنصر في مكانه المخصص يكلف أيضًا${\displaystyle O(n)}$بافتراض استخدام خوارزمية فرز الإدراج لفرز كل مجموعة، فإن تكلفة الخطوة الثالثة${\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})}$، أين${\displaystyle n_{i}}$هل طول الدلو مفهرس؟${\displaystyle i}$بما أننا نتحدث عن متوسط ​​الوقت، فإن التوقع${\displaystyle E(n_{i}^{2})}$يجب تقييمها بدلاً من ذلك. دع${\displaystyle X_{ij}}$ليكن المتغير العشوائي الذي${\displaystyle 1}$إذا عنصر${\displaystyle j}$يتم وضعها في دلو${\displaystyle i}$، و${\displaystyle 0}$وإلا. لدينا${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$. لذلك،

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _ {l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right).\end{محاذاة}}}$

يفصل السطر الأخير عملية الجمع إلى الحالات${\displaystyle j=l}$والقضية${\displaystyle j\neq l}$بما أن احتمال ظهور عنصر ما موزع على الدلو${\displaystyle i}$يكون${\displaystyle 1/k}$،${\displaystyle X_{ij}}$احتمالية أن يكون 1${\displaystyle 1/k}$وصفر فيما عدا ذلك.

${\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}}$

${\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}}$

مع الجمع، سيكون

${\displaystyle E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,k\leq n}\sum _{j\neq k}X_{ij}X_{ik}\right)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{ك^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}}$

وأخيرًا، ستكون التعقيدات${\displaystyle O\left(\sum _{i=1}^{k}E(n_{i}^{2})\right)=O\left(\sum _{i=1}^{k}{\frac {n^{2}+nk-n}{k^{2}}}\right)=O\left({\frac {n^{2}}{k}}+n\right)}$.

تتطلب الخطوة الأخيرة من فرز الدلو، وهي دمج جميع العناصر المصنفة في كل دلو،${\displaystyle O(k)}$الوقت. لذلك، فإن التعقيد الكلي هو${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$لاحظ أنه إذا تم اختيار k لتكون${\displaystyle k=\Theta (n)}$ثم يتم تشغيل فرز الدلو${\displaystyle O(n)}$متوسط ​​الوقت، بالنظر إلى مدخلات موزعة بشكل منتظم. ^{[ 1 ]}

تعتمد أكثر أنواع فرز الدلو شيوعًا على قائمة من n مدخلات رقمية تتراوح بين الصفر وقيمة قصوى M، وتقسم نطاق القيم إلى b دلو، حجم كل منها M / b . إذا تم فرز كل دلو باستخدام فرز الإدراج ، يمكن إثبات أن الفرز يعمل في زمن خطي متوقع (حيث يُحسب المتوسط ​​لجميع المدخلات الممكنة). ^{[ 3 ]} مع ذلك، يتراجع أداء هذا الفرز مع التكتل؛ فإذا تقاربت العديد من القيم، ستقع جميعها في دلو واحد ويتم فرزها ببطء. يتم تجنب هذا التراجع في الأداء في خوارزمية فرز الدلو الأصلية بافتراض أن المدخلات مُولَّدة بواسطة عملية عشوائية توزع العناصر بشكل منتظم على الفترة [0,1) . ^{[ 1 ]}

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

يُضيف نوع آخر من فرز الدلو، يُعرف بفرز المدرج التكراري أو فرز العد ، خطوة أولية لحساب عدد العناصر التي ستقع في كل دلو باستخدام مصفوفة عد. ^{[ 4 ]} وباستخدام هذه المعلومات، يمكن ترتيب قيم المصفوفة في سلسلة من الدلو في مكانها من خلال سلسلة من عمليات التبادل، دون ترك أي مساحة إضافية لتخزين الدلو.

فرز ساعي البريد هو نوع من فرز الدلو يستفيد من بنية هرمية للعناصر، تُوصف عادةً بمجموعة من السمات. هذه هي الخوارزمية المستخدمة في آلات فرز الرسائل في مكاتب البريد : يُفرز البريد أولاً بين الرسائل المحلية والدولية؛ ثم حسب الولاية أو المقاطعة أو الإقليم؛ ثم حسب مكتب البريد الوجهة؛ ثم حسب المسارات، وهكذا. ولأن المفاتيح لا تُقارن ببعضها، فإن زمن الفرز هو O( cn )، حيث يعتمد c على حجم المفتاح وعدد الدلو. وهذا مشابه لفرز الجذر الذي يعمل "من الأعلى إلى الأسفل"، أو "الرقم الأكثر أهمية أولاً". ^{[ 5 ] [ 6 ]}

تُعدّ خوارزمية فرز الخلط ^{[ 7 ]} نوعًا من خوارزمية فرز الدلو، حيث تبدأ بإزالة أول ثُمن من العناصر n المراد فرزها، ثم تُفرزها بشكل متكرر، وتضعها في مصفوفة. ينتج عن ذلك n /8 "دلوًا" تُوزّع عليها العناصر المتبقية 7/8. بعد ذلك، تُفرز كل "دلو"، وتُدمج "الدلاء" معًا لتكوين مصفوفة مُفرزة.