فرز الجذر

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 11 صور
الموسوعة الحرة

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

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

تاريخ

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

طُوِّرت أول خوارزمية حاسوبية فعّالة من حيث استخدام الذاكرة لهذا النوع من الفرز عام ١٩٥٤ في معهد ماساتشوستس للتكنولوجيا على يد هارولد إتش. سيوارد . وكانت خوارزميات فرز الجذر المحوسبة تُعتبر سابقًا غير عملية نظرًا للحاجة المُتصوَّرة إلى تخصيص متغير لمجموعات ذات أحجام غير معروفة. تمثلت ابتكارات سيوارد في استخدام مسح خطي لتحديد أحجام المجموعات والإزاحات المطلوبة مسبقًا، مما يسمح بتخصيص ثابت واحد للذاكرة الإضافية. ويرتبط المسح الخطي ارتباطًا وثيقًا بخوارزمية سيوارد الأخرى، وهي فرز العد .

في العصر الحديث، تُستخدم خوارزميات فرز الجذر بشكل شائع لمجموعات من السلاسل الثنائية والأعداد الصحيحة . وقد أظهرت بعض الاختبارات المعيارية أنها أسرع من خوارزميات الفرز الأخرى ذات الأغراض العامة، حيث تصل سرعتها أحيانًا إلى 50% أو ثلاثة أضعاف. [ 3 ] [ 4 ] [ 5 ]

آلة فرز بطاقات من IBM تقوم بفرز مجموعة كبيرة من البطاقات المثقبة باستخدام نظام الفرز الجذري . تُغذى البطاقات إلى قادوس أسفل ذقن المشغل، ثم تُفرز في إحدى سلال الإخراج الثلاث عشرة للآلة، بناءً على البيانات المثقوبة في عمود واحد على البطاقات. يُستخدم ذراع التدوير الموجود بالقرب من قادوس الإدخال لتحريك رأس القراءة إلى العمود التالي مع تقدم عملية الفرز. ويحتوي الرف الخلفي على البطاقات من عملية الفرز السابقة.

ترتيب الأرقام

يمكن تطبيق خوارزمية فرز الجذر بحيث تبدأ إما من الرقم الأكثر أهمية (MSD) أو الرقم الأقل أهمية (LSD). على سبيل المثال، مع العدد 1234 ، يمكن البدء من 1 (MSD) أو 4 (LSD).

تستخدم خوارزميات فرز الجذر LSD عادةً ترتيب الفرز التالي: تأتي المفاتيح القصيرة قبل المفاتيح الأطول، ثم تُفرز المفاتيح ذات الطول نفسه معجميًا . يتوافق هذا مع الترتيب الطبيعي لتمثيلات الأعداد الصحيحة، مثل المتتالية [1، 2، 3، 4، 5، 6، 7، 8، 9، 10، 11] . تُعتبر خوارزميات فرز LSD عمومًا خوارزميات فرز مستقرة .

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

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

مع ذلك، تُعدّ عمليات فرز MSD أكثر ملاءمةً للتقسيم الفرعي والتكرار. فكل مجموعة تُنشأ في خطوة MSD يمكن فرزها باستخدام الرقم الأكثر أهمية التالي، دون الرجوع إلى أي مجموعات أخرى أُنشئت في الخطوة السابقة. وبمجرد الوصول إلى الرقم الأخير، يكفي دمج المجموعات لإتمام عملية الفرز.

أمثلة

أقل رقم معنوي

قائمة المدخلات:

[170, 45, 75, 90, 2, 802, 2, 66]

ابدأ بترتيب الأرقام من الرقم الأخير (الأيمن) إلى اليمين، بناءً على ذلك الرقم:

[{17 0 , 9 0 }, { 2 , 80 2 , 2 }, {4 5 , 7 5 }, {6 6 }]

الترتيب حسب الرقم التالي من اليسار:

[{ 0 2, 8 0 2, 0 2}, { 4 5}, { 6 6}, {1 7 0, 7 5}, { 9 0}]
لاحظ أنه يتم إضافة الرقم 0 ضمنيًا للرقمين 2 بحيث يحافظ الرقم 802 على موقعه بينهما.

وأخيراً، حسب الرقم الموجود في أقصى اليسار:

[{ 0 0 2, 0 0 2, 0 45, 0 66, 0 75, 0 90}, { 1 70}, { 8 02}]
لاحظ أن الرقم 0 يُضاف إلى بداية جميع الأرقام المكونة من رقم واحد أو رقمين.

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

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

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

الرقم الأكثر أهمية، تكرار أمامي

قائمة إدخال، سلاسل رقمية ذات عرض ثابت مع أصفار بادئة:

[170, 045, 075, 025, 002, 024, 802, 066]

الرقم الأول، مع وجود أقواس تشير إلى الفئات:

[{ 0 45, 0 75, 0 25, 0 02, 0 24, 0 66}, { 1 70}, { 8 02}]
لاحظ أن 170 و802 مكتملتان بالفعل لأنهما كل ما تبقى في مجموعاتهما، لذلك لا حاجة إلى مزيد من التكرار

الرقم التالي:

[{ {0 0 2}, {0 2 5, 0 2 4}, {0 4 5}, {0 6 6}, {0 7 5} }, 170, 802]

الرقم الأخير:

[ 002, { {02 4 }, {02 5 } }, 045, 066, 075 , 170, 802]

كل ما تبقى هو الربط:

[002, 024, 025, 045, 066, 075, 170, 802]

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

تعمل خوارزمية فرز الجذر فييا(د⋅ن){\displaystyle O(d\cdot n)}الوقت، أينن{\displaystyle n}هو عدد المفاتيح، ود{\displaystyle d}يمثل طول المفتاح بالأرقام (مثلاً، أرقام مكونة من 8 بتات). يمكن لمتغيرات LSD تحقيق حد أدنى لـد{\displaystyle d}من "متوسط ​​طول المفتاح" عند تقسيم المفاتيح ذات الأطوال المتغيرة إلى مجموعات كما نوقش أعلاه.

يمكن تشغيل خوارزمية فرز الجذر LSD في وقت خطيΘ(د(ن+ك)){\displaystyle \Theta (d(n+k))}، أيند{\displaystyle d}يمثل عدد الأرقام في كل عنصر من عناصر المصفوفة، حيث يقع كل رقم في النطاق من 0 إلىك-1{\displaystyle k-1}مثل الأرقام من 0 إلى 255 لرقم مكون من 8 بتات. وينطبق هذا عندماد{\displaystyle d}ثابت، أيΘ(1){\displaystyle \Theta (1)}وك{\displaystyle k}يحدها من الأعلى:ن{\displaystyle n}، أييا(ن){\displaystyle O(n)}بغض النظر عن حجم قيمةن{\displaystyle n}، وهذا يجعلد{\displaystyle d}يمر عبر البيانات. [ 6 ] [ 7 ] يستخدم فرز الجذر MSD تمريرة واحدة فقط في أفضل الحالات، وفي أسوأ الحالات، يكون أداؤه مماثلاً لفرز الجذر LSD. [ 8 ]

تتميز خوارزميات فرز الجذر المُحسّنة بسرعة فائقة عند استخدامها في مجال مناسب. [ 9 ] وهي مُقيدة بالبيانات المعجمية، ولكن هذا لا يُشكل عائقًا في العديد من التطبيقات العملية. قد تُعيق أحجام المفاتيح الكبيرة تطبيقات LSD عندما يُصبح عدد مرات المرور المُستحث هو العامل المُحدد. [ 2 ]

يرتبط أداء خوارزمية فرز الجذر LSD بعدد مرات المرور على المصفوفة، وهوΘ(2د(ن+ك)){\displaystyle \Theta (2d(n+k))}يتم إجراء عمليتي مسح على المصفوفة لكل رقم: عملية عد، تليها عملية تبديل. يمكن تقليل عدد عمليات المسح إلىΘ((د+1)(ن+ك)){\displaystyle \Theta ((d+1)(n+k))}عن طريق إجراء عملية عدّ لجميع أرقام المفتاح في دورة واحدة. هذا ممكن لأن عمليات العدّ تتم دائمًا على كامل المصفوفة، ولا يؤدي تبديل عناصر المصفوفة إلى تغيير نتائج العدّ. [ 10 ] [ 11 ]

أنواع متخصصة

تطبيقات فرز الجذر MSD في مكانها

يمكن تنفيذ خوارزمية فرز الجذر MSD الثنائية، والتي تُسمى أيضًا الفرز السريع الثنائي، في مكانها بتقسيم مصفوفة الإدخال إلى خانتين: خانة الأصفار وخانة الآحاد. تُوسّع خانة الأصفار من بداية المصفوفة، بينما تُوسّع خانة الآحاد من نهايتها. يُوضع حد خانة الأصفار قبل العنصر الأول في المصفوفة، بينما يُوضع حد خانة الآحاد بعد العنصر الأخير. يتم فحص البت الأكثر أهمية في العنصر الأول. إذا كان هذا البت يساوي 1، يُبدّل العنصر الأول مع العنصر الذي يسبق حد خانة الآحاد (العنصر الأخير في المصفوفة)، وتُوسّع خانة الآحاد بمقدار عنصر واحد عن طريق إنقاص فهرس حد الآحاد. أما إذا كان هذا البت يساوي 0، فيبقى العنصر الأول في مكانه، وتُوسّع خانة الأصفار بمقدار عنصر واحد. يُفحص العنصر التالي في المصفوفة، وهو العنصر الذي يسبق حدود خانة الأصفار (أي أول عنصر لا يقع في خانة الأصفار أو خانة الآحاد). تستمر هذه العملية حتى تتلاقى خانة الأصفار مع خانة الآحاد. بعد ذلك، تُرتّب خانة الأصفار وخانة الآحاد بشكل متكرر بناءً على البت التالي لكل عنصر من عناصر المصفوفة. يستمر هذا الترتيب المتكرر حتى يُستخدم البت الأقل أهمية في عملية الترتيب. [ 12 ] [ 13 ] تتطلب معالجة الأعداد الصحيحة ذات المكمل الثنائي المُوقّعة التعامل مع البت الأكثر أهمية بعكس اتجاهه، ثم التعامل مع بقية البتات كأعداد غير مُوقّعة.

يمكن توسيع خوارزمية فرز MSD الثنائية ذات الأساس الموضعي لتشمل أسسًا أكبر مع الحفاظ على قدرتها على الفرز في مكانها. يُستخدم فرز العد لتحديد حجم كل خانة وفهرس بدايتها. يُستخدم التبديل لوضع العنصر الحالي في خانته، ثم توسيع حدود الخانة. أثناء مسح عناصر المصفوفة، يتم تخطي الخانات ومعالجة العناصر الواقعة بينها فقط، حتى تتم معالجة المصفوفة بأكملها ووضع جميع العناصر في خاناتها المناسبة. عدد الخانات هو نفسه عدد الأسس المستخدمة - على سبيل المثال، 16 خانة للأساس 16. تعتمد كل دورة على رقم واحد (على سبيل المثال، 4 بتات لكل رقم في حالة الأساس 16)، بدءًا من الرقم الأكثر أهمية . ثم تتم معالجة كل خانة بشكل متكرر باستخدام الرقم التالي، حتى يتم استخدام جميع الأرقام للفرز. [ 14 ] [ 15 ]

لا يعتبر كل من فرز الأساس الثنائي في مكانه وفرز الأساس n-bit، اللذان تمت مناقشتهما في الفقرات أعلاه، خوارزميات مستقرة .

تطبيقات مستقرة لفرز الجذر MSD

يمكن تنفيذ فرز الجذر MSD كخوارزمية مستقرة، ولكنه يتطلب استخدام مخزن مؤقت في الذاكرة بنفس حجم مصفوفة الإدخال. تسمح هذه الذاكرة الإضافية بمسح مخزن الإدخال من العنصر الأول إلى الأخير، ونقل عناصر المصفوفة إلى حاويات الوجهة بنفس الترتيب. وبالتالي، تُوضع العناصر المتساوية في مخزن الذاكرة بنفس ترتيبها في مصفوفة الإدخال. تستخدم خوارزمية MSD مخزن الذاكرة الإضافي كمخرج في المستوى الأول من الاستدعاء الذاتي، ولكنها تُبدّل المدخلات والمخرجات في المستوى التالي لتجنب عبء نسخ نتيجة المخرجات إلى مخزن الإدخال. تتم معالجة كل حاوية بشكل متكرر، كما هو الحال في فرز الجذر MSD الموضعي. بعد اكتمال الفرز حسب الرقم الأخير، يتم فحص مخزن المخرجات للتأكد مما إذا كان هو مصفوفة الإدخال الأصلية، وإذا لم يكن كذلك، يتم إجراء نسخة واحدة. إذا تم اختيار حجم الرقم بحيث يكون حاصل قسمة حجم المفتاح على حجم الرقم عددًا زوجيًا، يتم تجنب النسخ في النهاية. [ 16 ]

الأساليب الهجينة

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

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

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

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

تتوفر خوارزميات فرز متوازية أسرع، فعلى سبيل المثال، تتميز خوارزميات "المجريون الثلاثة" و"ريتشارد كول" [ 18 ] [ 19 ] بتعقيد زمني مثالي قدره O(log( n )) ، بينما تتميز خوارزمية فرز الدمج الثنائي لباتشر بتعقيد زمني قدره O(log2 ( n ) )، وكلها أقل تعقيدًا زمنيًا من فرز الجذر على ذاكرة CREW- PRAM . وقد وصف ديفيد إم دبليو باورز أسرع خوارزميات فرز PRAM المعروفة في عام 1991، وهي خوارزمية فرز سريع متوازية تعمل في زمن قدره O(log(n)) على ذاكرة CRCW-PRAM ذات n معالجًا من خلال إجراء التقسيم ضمنيًا، بالإضافة إلى خوارزمية فرز الجذر التي تعمل باستخدام نفس الأسلوب في زمن قدره O( k )، حيث k هو الحد الأقصى لطول المفتاح. [ 20 ] مع ذلك، لا يمكن بناء بنية PRAM أو معالج تسلسلي واحد بطريقة قابلة للتوسع دون زيادة عدد تأخيرات البوابات الثابتة لكل دورة بمقدار O(log( n ) )، بحيث يكون في الواقع إصدار خطي من خوارزمية فرز الدمج الثنائي لباتشر وخوارزميات فرز PRAM ذات O(log( n )) جميعها من رتبة O(log2 ( n ) ) من حيث دورات الساعة، مع إقرار باورز بأن خوارزمية باتشر ستكون ذات ثابت أقل من حيث تأخيرات البوابات مقارنةً بخوارزمية الفرز السريع المتوازي وخوارزمية فرز الجذر، أو خوارزمية فرز الدمج لكول ، وذلك لشبكة فرز مستقلة عن طول المفتاح من رتبة O(nlog2 ( n ) ). [ 21 ]

فرز الجذر القائم على الشجرة

يمكن أيضًا تحقيق فرز الجذر عن طريق بناء شجرة (أو شجرة جذرية ) من مجموعة المدخلات، وإجراء عملية اجتياز بترتيب مسبق . يشبه هذا العلاقة بين فرز الكومة وبنية بيانات الكومة . قد يكون هذا مفيدًا لأنواع بيانات معينة، انظر فرز الانفجار .

انظر أيضاً

مراجع

  1. ↑ الولايات المتحدة 395781  والمملكة المتحدة 327 
  2. 1 2 دونالد كنوث . فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ، الطبعة الثالثة. أديسون-ويسلي، 1997. ISBN 0-201-89685-0القسم 5.2.5: الفرز حسب التوزيع، الصفحات  168-179.
  3. ↑ "لقد كتبت خوارزمية فرز أسرع" . 28 ديسمبر 2016.
  4. ↑ "هل فرز الجذر أسرع من الفرز السريع لمصفوفات الأعداد الصحيحة؟" . erik.gorset.no .
  5. ↑ "قالب الدالة integer_sort - 1.62.0" . www.boost.org .
  6. ↑ تي إتش كورمن، سي إي ليسرسون، آر إل ريفست، سي شتاين، "مقدمة في الخوارزميات"، الطبعة الرابعة، 2022، ص 213-214
  7. ↑ ر. سيدجويك، ك. واين، "الخوارزميات"، الطبعة الرابعة، 2011، ص 708-709
  8. ↑ ر. سيدجويك، ك. واين، "الخوارزميات"، الطبعة الرابعة، 2011، ص 717
  9. ↑ سينها، رانجان؛ زوبيل، جاستن. "فرز فعال قائم على شجرة البحث لمجموعات كبيرة من السلاسل النصية" . CiteSeerX 10.1.1.12.2367 . تاريخ الاسترجاع: 24 أغسطس 2023 . 
  10. ↑ أدينيتس، آندي؛ ميريل، دوان. "Onesweep: خوارزمية فرز أسرع لأقل عدد من الأرقام ذات الأهمية الأساسية لوحدات معالجة الرسومات" . تم الاطلاع عليه بتاريخ 3 يونيو 2022 .
  11. ↑ دوفانينكو، فيكتور. "فرز جذور LSD المتوازي" . تم الاسترجاع في 17 فبراير 2020 .
  12. ↑ ر. سيدجويك، "الخوارزميات في لغة C++"، الطبعة الثالثة، 1998، ص 424-427
  13. ↑ دوفانينكو، فيكتور ج. "تحسين الخوارزميات من خلال قياس الأداء: الجزء 2" . دكتور دوبس .
  14. ↑ دوفانينكو، فيكتور ج. "تحسين الخوارزميات من خلال قياس الأداء: الجزء 3" . دكتور دوبس .
  15. ^ دوفانينكو ، فيكتور ج. “الفرز المتوازي في المكان الأساسي مبسط” . دكتور دوب .
  16. ↑ دوفانينكو، فيكتور ج. "تحسين الخوارزميات من خلال قياس الأداء: الجزء 4" . دكتور دوبس .
  17. ^ دوفانينكو ، فيكتور ج. “فرز متوازي في مكان N-bit-Radix” . دكتور دوب .
  18. ↑ أ. جيبونز و و. ريتر ، خوارزميات متوازية فعالة . مطبعة جامعة كامبريدج، 1988.
  19. ↑ H. Casanova et al, Parallel Algorithms . Chapman & Hall, 2008.
  20. ↑ ديفيد إم دبليو باورز، فرز سريع وفرز جذري متوازيان مع تسريع مثالي ، وقائع المؤتمر الدولي حول تقنيات الحوسبة المتوازية . نوفوسيبيرسك . 1991.
  21. ↑ ديفيد إم دبليو باورز، التوحيد المتوازي: التعقيد العملي ، ورشة عمل هندسة الحاسوب الأسترالية، جامعة فليندرز، يناير 1995