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

الترتيب الجذري بيانات عامّة الصنف خوارزمية ترتيب بنية البيانات Array الأداء أسوء حالة $O(w\cdot n)$, where $n$ is the number of keys, and $w$ is the key length. أسوأ حالة تعقيد مكاني $O(w+n)$

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

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

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

يعود تاريخ الترتيب الجذري إلى عام 1887 حيث طوره العالم هيرمان هوليرثHerman Hollerith ليتم استخدامه لترتيب البطاقات المثقوبة(Punched Cards) باستخدام الات الجدولة حوالي العام 1923.

يعود تاريخ الفرز الجذري إلى عام 1887 إلى عمل Herman Hollerith على آلات الجدولة. أصبحت خوارزميات الفرز الجذري شائعة الاستخدام كطريقة لفرز البطاقات المثقوبة منذ عام 1923.

تم تطوير أول خوارزمية حاسوبية فعالة للذاكرة لطريقة الفرز هذه في عام 1954 في معهد ماساتشوستس للتكنولوجيا بواسطة Harold H. Seward . حيث كانت خوارزميات الترتيب التي تعتمد على طريقة الترتيب الجذري قبل خوارزمية العالم سيوارد تعاني قصورا ملموسا بسبب الحاجة إلى تخصيص كمية متغيرة من موارد الذاكرة المساعدة. تخصيص موارد الذاكرة المساعدة يتم لحجز أماكن لتخزين المجموعات التي توزع اليها القيم المراد ترتيبها خلال عملية الترتيب. خوارزمية العالم سيوارد اعتمدت طريقة مسح خطي للمجموعات. يهدف هذا المسح إلى تحديد مسبق لحجم الذاكرة المطلوب لتخزين المجموعات في الذاكرة المساعدة، ما يسمح بالقيام بحجز الذاكرة بخطوة ثابتة واحدة.  طريقة المسح الخطي هذه وثيقة الصلة بخوارزمية أخرى منسوبة للعالم سيوارد وهي طريقة الفرز العدي (counting sort).

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

فارز بطاقة IBM يقوم بفرز"ترتيب" جذري على مجموعة كبيرة من البطاقات المثقوبة . يتم وضع البطاقات في وعاء متحرك للأعلى والأسفل ثم تقوم الآلة بفرز البطاقات إلى 13 سلة بناء على قيمة واحد من الأعمدة في البطاقات المثقوبة. يقوم كرنك (crank) بالقرب من الوعاء المتحرك بتحريك رأس القراءة إلى العمود التالي مع تقدم الفرز. يحمل الرف الموجود في الخلف بطاقات من دور الفرز السابق.

ترتيب الخانات

من الممكن استخدام الترتيب الجذري بطريقتين؛ إما بناء على قيمة الخانة الأقل دلالة ضمن خانات القيم (من اليمين إلى اليسار) أو بناء قيمة الخانة الأعلى دلالة ضمن خانات القيم (من اليسار إلى اليمين). مثلا الرقم 1234 تكون الخانة الأقل دلالة هي (4) والخانة الأعلى دلالة هي (1).

في حالة اعتماد طريقة الترتيب بناء قيمة الخانة الأقل، القيم المكونة من خانات أقل تأتي أولا. والقيم المحتوية على نفس عدد متساو من القيم يتم ترتيبها ابجديا. أما الأرقام فينطبق عبيها نفس المنطق حيث يكون ال (1) قبل ال (2) وال (100) قبل ال (110) مثلا. الترتيب بناء على قيمة الخانة الأقل هو ترتيب مستقر مثلا حيث يكون ترتيب القيم المتساوية مماثلا  لترتيب ظهورها ضمن القيم المراد ترتيبها.

طريقة الترتيب بناء قيمة الخانة الأعلى دلالة  مناسب أكثر لترتيب النصوص والأرقام ذات الطول الثابت.  المجموعة فمثلا [b, c, e, d, f, g, ba] سيتم ترتيبها كالآتي: [b, ba, c, d, e, f, g] .أما في حالة ترتيب الأرقام من واحد إلى عشرة سيكون الترتيب[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]  حيث سيتم اعتبار أن جميع الأرقام هي عبارة عن أرقام مكونة من خانتين وقد تم محاذاة الأرقام المكونة من خانة واحدة إلى اليسار وأن قيمة الخانة على يمينها هي فراغ أو (space)  و ذلك لجعل جميع الأرقام بنفس عدد الخانات. طريقة الترتيب بناء قيمة الخانة الأعلى دلالة  هي طريقة غير مستقرة حيث لا يوجد ضمانة أن القيم المتساوية في المجموعة المراد ترتيبها ستكون بنفس الترتيب بعد عملية الترتيب.

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

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

أمثلة

مثال على استخدام الترتيب الجذري بطريقة الترتيب حسب الخانة الأقل دلالة

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

[171، 46، 76، 91، 3، 803، 3،67]

ترتيب القيم حسب الخانة الأقل دلالة:

[{171,91 } ، { 3,802,3 } ، {46,76 } ، {7 6 }]

الفرز حسب الرقم التالي إلى اليسار:

[{ 03,802,03} ، { 46} ، {67} ، {171,76} ، {91}]

لاحظ أن الخانة تم اعتبارها صفرا في حالة عدم وجودها كما في حالة الرقم 802

ثم الخانة الموجودة في أقصى اليسار:

[{ 003، 003، 046، 067، 076، 090} ، { 171} ، { 802}]

لاحظ أن الخانات تم اعتبارها صفرا في حالة عدم وجودها أيضا

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

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

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

مثال على استخدام الترتيب الجذري بطريقة الترتيب حسب الخانة الأعلى دلالة

المجموعة المراد ترتيبها (تم بدء بعض القيم ب 0 لتكون جميع القيم بنفس الطول):

[171، 046، 076، 026، 003، 025، 803، 067]

الخانة الأولى تحدد المجموعة

[ 046، 076، 026، 003،025، 067} ، { 171} ، { 803}]

لاحظ أن 171 و 802 لا حاجة لإضافة اصفار اليهما بسبب اكتمال عدد الخانات

ثم الخانة التالية:

[{{003} ، {025،026} ، {046} ، {067} ، {076}} ، 171، 803]

الخانة الأخيرة:

[003، {{025} ، {026}} ، 046، 067، 076، 171، 803]

ثم التوصيل التعاقبي:

[003، 025، 026، 046، 067، 076، 171، 803]

التعقيد والأداء

يتطلب الترتيب الجذري خطوات محدودة بعدد القيم مضروبا بعدد الخانات للقيم O(nw) باعتبار أن  nتمثل عدد القيم و w تمثل عدد الخانات. الترتيب حسب الخانة الأقل دلالة يمكن ان يتطلب تعقيدا أقل  حيث لا يتم توسعة عدد الخانات لتكون جميع القيم بنفس الطول في هذه الحالة يعتمد عدد الخطوات على معدل الأطوال لجميع القيم بدلا من الاعتماد على أطول قيمة.

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