الترتيب المنازلي أو الجذري

الترتيب المنازلي أو الجذري

بيانات عامّة

الصنف	خوارزمية ترتيب
بنية البيانات	Array
المكتشف	هيرمان هولليريث
تاريخ الاكتشاف	1887

الأداء

أسوء حالة	$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. أصبحت خوارزميات الفرز الجذري شائعة الاستخدام كطريقة لفرز البطاقات المثقوبة منذ عام 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 ,803 , 3)، (46, 76)،(7 6)]

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

[(03,803,03)، (46)، (67)، (171,76)، (91)]

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

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

[{003 ، 003، 460 ، 670 ،760 ، 910 } ، { 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 تمثل عدد الخانات. الترتيب حسب الخانة الأقل دلالة يمكن ان يتطلب تعقيدا أقل  حيث لا يتم توسعة عدد الخانات لتكون جميع القيم بنفس الطول في هذه الحالة يعتمد عدد الخطوات على معدل الأطوال لجميع القيم بدلا من الاعتماد على أطول قيمة.

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

تطبيقات خاصة

الترتيب بنفس المكان بناء قيمة الخانة الأعلى دلالة

تهدف عملية الترتيب هذه إلى فرز وترتيب القيم الثنائية (Binary) المخزنة داخل مصفوفة _مثلا_ بدون الحاجة إلى استخدام مصفوفات اضافية لتخزين القيم عند توزيعها إلى مجموعات. يتم تقسيم المصفوفة المحتوية على القيم إلى جزئين أو قسمين. القسم الأول هو قسم الأصفار والقسم الثاني هو قسم الواحدات يبدأ قسم الواحدات من اقصى يمين المصفوفة وينتهي عند حدود قسم الواحدات فيما يبدأ قسم الواحدات من أقصى اليسار وينتهي عند حدود قسم الأصفار.

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

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

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

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

الترتيب بناء قيمة الخانة الأعلى دلالة بطريقة مستقرة

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

استخدام الترتيب الجذري بطريقة هجينة

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

تطبيق على الحوسبة المتوازية

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