فرز العد

الموسوعة الحرة

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

فرز العد ليس فرزًا مقارنًا ؛ فهو يستخدم قيم المفاتيح كمؤشرات في مصفوفة، وبالتالي لا ينطبق عليه الحد الأدنى Ω ( n log n ) للفرز المقارن. [ 1 ] يمكن استخدام فرز الدلو بدلًا من فرز العد، ويتطلب تحليلًا زمنيًا مشابهًا. مع ذلك، بالمقارنة مع فرز العد، يتطلب فرز الدلو قوائم مرتبطة ، أو مصفوفات ديناميكية ، أو مساحة كبيرة من الذاكرة المخصصة مسبقًا لتخزين مجموعات العناصر داخل كل دلو، بينما يخزن فرز العد رقمًا واحدًا (عدد العناصر) لكل دلو. [ 4 ]

افتراضات المدخلات والمخرجات

في الحالة العامة، يتكون مُدخل فرز العد من مجموعة من n عنصرًا، لكل منها مفتاح عدد صحيح غير سالب، وقيمته القصوى لا تتجاوز k . [ 3 ] في بعض توصيفات فرز العد، يُفترض أن المُدخل المراد فرزه هو ببساطة سلسلة من الأعداد الصحيحة نفسها، [ 1 ] لكن هذا التبسيط لا يُناسب العديد من تطبيقات فرز العد. على سبيل المثال، عند استخدامه كدالة فرعية في فرز الجذر ، تكون مفاتيح كل استدعاء لفرز العد هي أرقام فردية من مفاتيح العناصر الأكبر؛ ولن يكفي إرجاع قائمة مُرتبة من أرقام المفاتيح فقط، منفصلة عن العناصر.

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

الناتج عبارة عن مصفوفة من العناصر مرتبة حسب مفاتيحها. ونظرًا لتطبيقها في فرز الجذر، يجب أن يكون فرز العد فرزًا مستقرًا ؛ أي إذا اشترك عنصران في نفس المفتاح، فيجب أن يتطابق ترتيبهما النسبي في مصفوفة الناتج مع ترتيبهما النسبي في مصفوفة الإدخال. [ 1 ] [ 2 ]

الشفرة الزائفة

في الشفرة الزائفة، يمكن التعبير عن الخوارزمية على النحو التالي:

الدالة CountingSort(input, k ) هي عدد ← مصفوفة من k + 1 أصفار الناتج ← مصفوفة بنفس طول المدخلات for i = 0 to length(input) - 1 do j = key(input[ i ]) count[ j ] = count[ j ] + 1 for i = 1 to k do count[ i ] = count[ i ] + count[ i - 1] for i = length(input) - 1 down to 0 do j = key(input[ i ]) count[ j ] = count[ j ] - 1 output[count[''j'']] = input[''i'']إرجاع المخرجات

أين inputالمصفوفة المراد فرزها، keyتُرجع المفتاح الرقمي لكل عنصر في مصفوفة الإدخال، countوهي مصفوفة مساعدة تُستخدم أولاً لتخزين أعداد العناصر التي تحتوي على كل مفتاح، ثم (بعد الحلقة الثانية) لتخزين المواضع التي يجب وضع العناصر التي تحتوي على كل مفتاح فيها، kوهي القيمة القصوى لقيم المفاتيح غير السالبة، outputوهي مصفوفة الإخراج المرتبة.

باختصار، تقوم الخوارزمية بالمرور على العناصر في الحلقة الأولى، وحساب مدرج تكراري لعدد مرات ظهور كل مفتاح ضمن inputالمجموعة. بعد ذلك، في الحلقة الثانية، تُجري عملية حساب مجموع البادئاتcount لتحديد نطاق المواضع الذي يجب وضع العناصر التي تحمل هذا المفتاح فيه، وذلك لكل مفتاح؛ أي العناصر التي تحمل المفتاحأنا{\displaystyle i}يجب وضعها بدءًا من الموضع . أخيرًا، في الحلقة الثالثة، يتم المرور على عناصر المصفوفة مرة أخرى، ولكن بترتيب عكسي، ونقل كل عنصر إلى موضعه المُرتب في المصفوفة. [ 1 ] [ 2 ] [ 3 ]count[i{\displaystyle i}]inputoutput

يتم الحفاظ على الترتيب النسبي للعناصر ذات المفاتيح المتساوية هنا؛ أي أن هذا فرز مستقر .

تحليل التعقيد

نظرًا لأن الخوارزمية تستخدم forحلقات بسيطة فقط، دون استدعاءات تكرارية أو إجراءات فرعية، فإن تحليلها سهل. تتكرر كل من عملية تهيئة مصفوفة العد، وحلقة التكرار الثانية التي تُجري عملية جمع جزئي على مصفوفة العد، على الأكثر k + 1 مرة، وبالتالي تستغرقان زمنًا قدره O ( k ) . أما حلقتا التكرار الأخريان، وعملية تهيئة مصفوفة الإخراج، فتستغرق كل منهما زمنًا قدره O ( n ) . لذلك، فإن زمن الخوارزمية ككل هو مجموع أزمنة هذه الخطوات، أي O ( n + k ) . [ 1 ] [ 2 ]

نظرًا لاستخدامها مصفوفات بطول k + 1 و n ، فإن إجمالي مساحة التخزين المستخدمة في الخوارزمية هو أيضًا O ( n + k ) . [ 1 ] في حالات المسائل التي تكون فيها قيمة المفتاح القصوى أصغر بكثير من عدد العناصر، يمكن أن يكون فرز العد فعالًا للغاية من حيث استخدام المساحة، حيث أن وحدة التخزين الوحيدة التي تستخدمها بخلاف مصفوفات الإدخال والإخراج هي مصفوفة العد التي تشغل مساحة O ( k ) . [ 5 ]

خوارزميات متغيرة

إذا كان كل عنصر يتم فرزه هو نفسه عدد صحيح، ويستخدم كمفتاح أيضًا، فيمكن دمج الحلقتين الثانية والثالثة من فرز العد؛ في الحلقة الثانية، بدلاً من حساب الموضع الذي iيجب وضع العناصر ذات المفتاح فيه في الإخراج، قم ببساطة بإلحاق Count[i]نسخ من الرقم iبالإخراج.

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

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

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

تاريخ

على الرغم من أن فرز الجذر نفسه يعود إلى فترة أطول بكثير، إلا أن فرز العد وتطبيقه على فرز الجذر قد تم اختراعهما بواسطة هارولد إتش. سيوارد في عام 1954. [ 1 ] [ 4 ] [ 8 ]

مراجع

  1. 1 2 3 4 5 6 7 8 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001)، "8.2 فرز العد"، مقدمة في الخوارزميات (  الطبعة الثانية)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل ، الصفحات 168-170 ، ISBN  0-262-03293-7انظر أيضًا الملاحظات التاريخية في الصفحة 181.
  2. 1 2 3 4 إدموندز، جيف (2008)، "5.2 فرز العد (فرز مستقر)"، كيف تفكر في الخوارزميات ، مطبعة جامعة كامبريدج، ص 72-75 ، ISBN  978-0-521-84931-9.
  3. 1 2 3 4 سيدجويك، روبرت ( 2003)، "6.10 العد المفهرس بالمفتاح"، الخوارزميات في جافا، الأجزاء 1-4: الأساسيات، هياكل البيانات، الفرز، والبحث ( الطبعة الثالثة)، أديسون-ويسلي، ص 312-314  .
  4. 1 2 كنوت، دي إي (1998)، فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ( الطبعة الثانية)، أديسون-ويسلي، ISBN  0-201-89685-0القسم 5.2، الفرز عن طريق العد، الصفحات  75-80، والملاحظات التاريخية، الصفحة  170.
  5. ↑ بوريس، ديفيد س.؛ شيمبر، كورت (1980)، "فرز الملفات المتسلسلة مع مساحة تخزين إضافية محدودة"، وقائع المؤتمر الإقليمي السنوي الثامن عشر لجنوب شرق الولايات المتحدة ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM، الصفحات 23-31 ، doi : 10.1145/503838.503855 ، ISBN  0897910141، S2CID 5670614 .
  6. ↑ زاغا، ماركو؛ بليلوش، غاي إي. (1991)، "فرز الجذر للمعالجات المتعددة المتجهة"، وقائع مؤتمر الحوسبة الفائقة 91، 18-22 نوفمبر 1991، ألبوكيرك، نيو مكسيكو، الولايات المتحدة الأمريكية ، جمعية مهندسي الكهرباء والإلكترونيات/رابطة مكائن ​​الحوسبة، الصفحات 712-721 ، doi : 10.1145/125826.126164 ، ISBN  0897914597.
  7. ↑ ريف، جون هـ. (1985)، "خوارزمية متوازية مثلى لفرز الأعداد الصحيحة"، وقائع الندوة السنوية السادسة والعشرين حول أسس علوم الحاسوب (FOCS 1985) ، الصفحات 496-504 ، doi : 10.1109/SFCS.1985.9 ، ISBN  0-8186-0644-4، S2CID 5694693 .
  8. ↑ سيوارد، إتش إتش (1954)، "2.4.6 الفرز الداخلي بواسطة الفرز الرقمي العائم"، فرز المعلومات في تطبيق الحواسيب الرقمية الإلكترونية على العمليات التجارية (ملف PDF) ، رسالة ماجستير، التقرير R-232، معهد ماساتشوستس للتكنولوجيا ، مختبر الحاسوب الرقمي، الصفحات 25-28 .