مستخدم:Remah Younisse/Radix sort
| الصنف | |
|---|---|
| بنية البيانات |
| أسوء حالة |
, 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
ثم الخانةالموجودة في أقصى اليسار:
- [{ 0 2 ، 0 0 2 ، 0 45 ، 0 66 ، 0 75 ، 0 90} ، { 1 70} ، { 8 02}]
- لاحظ أن الخانات تم اعتبارها صفرا في حالة عدم وجودها أيضا
كل خطوة تتطلب مسحا واحدا للقيم لأن كل عنصر يتم فرزه دون الحاجة لمعرفة باقي الخانات.
بعض التطبيقات للخوارزمية تهيء مساحة لتخزين المجموعات باستخدام طريقة العد. حيث يتم عد العناصر التابعة لكل مجموعة قبل البدء بعملية التوزيع الى مجموعات. يتم تخزين عدد مرات ظهور الأرقام في مصفوفة .
على الرغم من أنه من الممكن معرفة حدود المصفوفة مسبقا[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.
- ^ [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.
- ^ "Is radix sort faster than quicksort for integer arrays?". erik.gorset.no.
- ^ "Function template integer_sort - 1.62.0". www.boost.org.
- ^ 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.
- ^ 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.
{{استشهاد بدورية محكمة}}: تحقق من التاريخ في:|date=(مساعدة) - ^ "Efficient Trie-Based Sorting of Large Sets of Strings".