الترتيب الجذري
| الصنف | |
|---|---|
| بنية البيانات |
| أسوء حالة |
, where is the number of keys, and is the key length. |
|---|---|
| أسوأ حالة تعقيد مكاني |
في علم الحاسوب يعتبر الترتيب الجذري طريقة ترتيب غير مقارنة. يتم ترتيب القيم باستخدام هذه الخوارزمية من خلال توزيع القيم إلى مجموعات (buckets) في داخل كل مجموعة قيم مرتبطة بناء على خانة محددة في كل قيمة. يتم تكرار تصنيف القيم المكونة من أكثر من رقم (منزلة) لكل منزلة حيث يتم توزيع القيم إلى مجموعات بناء على أول منزلة ثم بناء على ثاني منزلة ثم ثالث منزلة الخ... تسمى هذه الخوارزمية خوارزمية التصنيف إلى مجموعات أو خوارزمية التصنيف حسب المنزلة أيضا.
يتم تطبيق هذه الخوارزمية عند الحاجة إلى ترتيب القيم حسب الترتيب الابجدي حيث يمكن تطبيقها على الكلمات، الأرقام، أوراق اللعب أو البريد الالكتروني.
تاريخ الترتيب الجذري
[عدل]يعود تاريخ الترتيب الجذري إلى عام 1887 حيث طوره العالم هيرمان هوليرثHerman Hollerith ليتم استخدامه لترتيب البطاقات المثقوبة(Punched Cards) باستخدام الات الجدولة[1] حوالي العام 1923.
يعود تاريخ الفرز الجذري إلى عام 1887 إلى عمل Herman Hollerith على آلات الجدولة.[2] أصبحت خوارزميات الفرز الجذري شائعة الاستخدام كطريقة لفرز البطاقات المثقوبة منذ عام 1923.[3]
تم تطوير أول خوارزمية حاسوبية فعالة للذاكرة لطريقة الفرز هذه في عام 1954 في معهد ماساتشوستس للتكنولوجيا بواسطة Harold H. Seward . حيث كانت خوارزميات الترتيب التي تعتمد على طريقة الترتيب الجذري قبل خوارزمية العالم سيوارد تعاني قصورا ملموسا بسبب الحاجة إلى تخصيص كمية متغيرة من موارد الذاكرة المساعدة. تخصيص موارد الذاكرة المساعدة يتم لحجز أماكن لتخزين المجموعات التي توزع اليها القيم المراد ترتيبها خلال عملية الترتيب. خوارزمية العالم سيوارد اعتمدت طريقة مسح خطي للمجموعات. يهدف هذا المسح إلى تحديد مسبق لحجم الذاكرة المطلوب لتخزين المجموعات في الذاكرة المساعدة، ما يسمح بالقيام بحجز الذاكرة بخطوة ثابتة واحدة. طريقة المسح الخطي هذه وثيقة الصلة بخوارزمية أخرى منسوبة للعالم سيوارد وهي طريقة الفرز العدي (counting sort).
في الوقت الحالي، يتم استخدام خوارزمية الترتيب الجذري لترتيب النصوص أو الأرقام. في بعض الحالات تفوق الترتيب الجذري على خوارزميات ترتيب عامة بنسبة 50%، كما سجل اداء ثلاث مرات أسرع في حالات أخرى.[4][5][6]
ترتيب الخانات
[عدل]من الممكن استخدام الترتيب الجذري بطريقتين؛ إما بناء على قيمة الخانة الأقل دلالة ضمن خانات القيم (من اليمين إلى اليسار) أو بناء قيمة الخانة الأعلى دلالة ضمن خانات القيم (من اليسار إلى اليمين). مثلا الرقم 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) و ذلك لجعل جميع الأرقام بنفس عدد الخانات. طريقة الترتيب بناء قيمة الخانة الأعلى دلالة هي طريقة غير مستقرة حيث لا يوجد ضمانة أن القيم المتساوية في المجموعة المراد ترتيبها ستكون بنفس الترتيب بعد عملية الترتيب.
تختلف طريقة الترتيب بناء على الخانة الأقل عن طريقة الترتيب بناء على الخانة الأعلى أن الطريقة الأولى تعتمد مسحا للقيم من الخانات اليمين باتجاه اليسار والثانية تعتمد مسحا للقيم من اليمين لليسار. باستخدام الطريقة الأولى يمكن توزيع القيم إلى مجموعات حسب عدد خاناتها ثم ترتيب كل مجموعة على حذة باستخدام الترتيب الجذري ومن ثم ضم المجموعات المرتبة في مجموعة واحدة مرتبة أيضا من خلال إضافة عناصر المجموعة الأقصر فالأطول فالأطول أو العكس. أما في حالة استخدام الطريقة الثانية يجب مساواة عدد الخانات في جميع القيم من خلال إضافة الفراغات إلى القيم الأقصر ما يجعل هذه الطريقة أكثر تعقيدا من سابقتها ناهيك عن عدم استقرارها.[7]
طريقة الترتيب بناء على الخانة الأعلى قابلة أكثر للتقسيم والتكرار (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}]
- لاحظ أن الخانات تم اعتبارها صفرا في حالة عدم وجودها أيضا
كل خطوة تتطلب مسحا واحدا للقيم لأن كل عنصر يتم فرزه دون الحاجة لمعرفة باقي الخانات.
بعض التطبيقات للخوارزمية تهيء مساحة لتخزين المجموعات باستخدام طريقة العد. حيث يتم عد العناصر التابعة لكل مجموعة قبل البدء بعملية التوزيع إلى مجموعات. يتم تخزين عدد مرات ظهور الأرقام في مصفوفة.
على الرغم من أنه من الممكن معرفة حدود المصفوفة مسبقا[8] ، لكن بعض التطبيقات تستخدم تخصيص الذاكرة الديناميكي بدلاً من ذلك.
مثال على استخدام الترتيب الجذري بطريقة الترتيب حسب الخانة الأعلى دلالة
[عدل]المجموعة المراد ترتيبها (تم بدء بعض القيم ب 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 تمثل عدد الخانات. الترتيب حسب الخانة الأقل دلالة يمكن ان يتطلب تعقيدا أقل حيث لا يتم توسعة عدد الخانات لتكون جميع القيم بنفس الطول في هذه الحالة يعتمد عدد الخطوات على معدل الأطوال لجميع القيم بدلا من الاعتماد على أطول قيمة.
يمكن أن تعطي طريقة الترتيب الجذري نتائج ممتازة خصوصا عند استخدامها في مجالات مناسبة مثل الترتيب الأبجدي.[9] كما يمكن يعوق عملها بشكل ممتاز أن تكون خانات القيم طويلة جدا خصوصا عند استخدام الترتيب حسب الخانة الأقل.
مراجع
[عدل]- ^ Contributors. Routledge. 27 فبراير 2012. ص. 327–334. مؤرشف من الأصل في 2022-11-30.
- ^ [1] and [2]
- ^ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. (ردمك 0-201-89685-0). Section 5.2.5: Sorting by Distribution, pp. 168–179.
- ^ "I Wrote a Faster Sorting Algorithm". 28 ديسمبر 2016. مؤرشف من الأصل في 2023-01-15.
- ^ "Is radix sort faster than quicksort for integer arrays?". erik.gorset.no. مؤرشف من الأصل في 2022-10-30.
- ^ "Function template integer_sort - 1.62.0". www.boost.org. مؤرشف من الأصل في 2022-10-30.
- ^ Polychroniou، Orestis؛ Ross، Kenneth A. (18 يونيو 2014). "A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort". Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. SIGMOD '14. New York, NY, USA: Association for Computing Machinery: 755–766. DOI:10.1145/2588555.2610522. ISBN:978-1-4503-2376-5. مؤرشف من الأصل في 2022-11-03.
- ^ Jimenez-Gonzalez، D.؛ Navarro، J.J.؛ Larriba-Pey، J.-L. (2003-02). "CC-Radix: a cache conscious sorting based on Radix sort". Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2003. Proceedings.: 101–108. DOI:10.1109/EMPDP.2003.1183573. مؤرشف من الأصل في 2022-11-03.
{{استشهاد بدورية محكمة}}: تحقق من التاريخ في:|تاريخ=(مساعدة) - ^ "Efficient Trie-Based Sorting of Large Sets of Strings". مؤرشف من الأصل في 2022-10-30.
