[ تعرٌف على ] الترتيب الجذري أو المنازلي

تم النشر اليوم 10-12-2025 | [ تعرٌف على ] الترتيب الجذري أو المنازلي
تم النشر اليوم [dadate] | الترتيب الجذري أو المنازلي

أمثلة

مثال على استخدام الترتيب الجذري بطريقة الترتيب حسب الخانة الأقل دلالة المجموعة المراد ترتيبها: [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 ثم الخانة الموجودة في أقصى اليسار: [{ 0 2، 0 0 2، 0 45، 0 66، 0 75، 0 90} ، { 1 70} ، { 8 02}] لاحظ أن الخانات تم اعتبارها صفرا في حالة عدم وجودها أيضا كل خطوة تتطلب مسحا واحدا للقيم لأن كل عنصر يتم فرزه دون الحاجة لمعرفة باقي الخانات. بعض التطبيقات للخوارزمية تهيء مساحة لتخزين المجموعات باستخدام طريقة العد. حيث يتم عد العناصر التابعة لكل مجموعة قبل البدء بعملية التوزيع إلى مجموعات. يتم تخزين عدد مرات ظهور الأرقام في مصفوفة. على الرغم من أنه من الممكن معرفة حدود المصفوفة مسبقا ، لكن بعض التطبيقات تستخدم تخصيص الذاكرة الديناميكي بدلاً من ذلك. مثال على استخدام الترتيب الجذري بطريقة الترتيب حسب الخانة الأعلى دلالة المجموعة المراد ترتيبها (تم بدء بعض القيم ب 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] وهذه هي النتيجة النهائية

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

من الممكن استخدام الترتيب الجذري بطريقتين؛ إما بناء على قيمة الخانة الأقل دلالة ضمن خانات القيم (من اليمين إلى اليسار) أو بناء قيمة الخانة الأعلى دلالة ضمن خانات القيم (من اليسار إلى اليمين). مثلا الرقم 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).

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

يعود تاريخ الترتيب الجذري إلى عام 1887 حيث طوره العالم هيرمان هوليرثHerman Hollerith ليتم استخدامه لترتيب البطاقات المثقوبة(Punched Cards)باستخدام الات الجدولة حوالي العام 1923. يعود تاريخ الفرز الجذري إلى عام 1887 إلى عمل Herman Hollerith على آلات الجدولة. أصبحت خوارزميات الفرز الجذري شائعة الاستخدام كطريقة لفرز البطاقات المثقوبة منذ عام 1923. تم تطوير أول خوارزمية حاسوبية فعالة للذاكرة لطريقة الفرز هذه في عام 1954 في معهد ماساتشوستس للتكنولوجيا بواسطة Harold H. Seward . حيث كانت خوارزميات الترتيب التي تعتمد على طريقة الترتيب الجذري قبل خوارزمية العالم سيوارد تعاني قصورا ملموسا بسبب الحاجة إلى تخصيص كمية متغيرة من موارد الذاكرة المساعدة. تخصيص موارد الذاكرة المساعدة يتم لحجز أماكن لتخزين المجموعات التي توزع اليها القيم المراد ترتيبها خلال عملية الترتيب. خوارزمية العالم سيوارد اعتمدت طريقة مسح خطي للمجموعات. يهدف هذا المسح إلى تحديد مسبق لحجم الذاكرة المطلوب لتخزين المجموعات في الذاكرة المساعدة، ما يسمح بالقيام بحجز الذاكرة بخطوة ثابتة واحدة. طريقة المسح الخطي هذه وثيقة الصلة بخوارزمية أخرى منسوبة للعالم سيوارد وهي طريقة الفرز العدي (counting sort). في الوقت الحالي، يتم استخدام خوارزمية الترتيب الجذري لترتيب النصوص أو الأرقام. في بعض الحالات تفوق الترتيب الجذري على خوارزميات ترتيب عامة بنسبة 50%، كما سجل اداء ثلاث مرات أسرع في حالات أخرى. فارز بطاقة IBM يقوم بفرز"ترتيب" جذري على مجموعة كبيرة من البطاقات المثقوبة . يتم وضع البطاقات في وعاء متحرك للأعلى والأسفل ثم تقوم الآلة بفرز البطاقات إلى 13 سلة بناء على قيمة واحد من الأعمدة في البطاقات المثقوبة. يقوم كرنك (crank) بالقرب من الوعاء المتحرك بتحريك رأس القراءة إلى العمود التالي مع تقدم الفرز. يحمل الرف الموجود في الخلف بطاقات من دور الفرز السابق.

تطبيقات خاصة

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

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

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

شرح مبسط

تعديل - تعديل مصدري