ماذا يعني counting sort في مجال الخوارزميات وهياكل البيانات

ماذا يعني Counting Sort في مجال الخوارزميات وهياكل البيانات

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

ما هي خوارزمية Counting Sort؟

خوارزمية Counting Sort هي خوارزمية ترتيب غير مقارنة تعتمد على توزيع الترددات للعناصر. بدلاً من المقارنة بين العناصر، تقوم هذه الخوارزمية بحساب عدد مرات ظهور كل عنصر في المجموعة، ومن ثم تستخدم هذه المعلومات لوضع العناصر في مواقعها الصحيحة في مصفوفة مرتبة.

كيفية عمل خوارزمية Counting Sort

لفهم كيفية عمل خوارزمية Counting Sort، دعونا نستعرض الخطوات التالية:

1. تحديد النطاق:

في البداية، نحدد النطاق الذي تقع فيه جميع العناصر. على سبيل المثال، إذا كانت العناصر تتراوح بين 0 و 9، فإن النطاق سيكون من 0 إلى 9.

2. إنشاء مصفوفة التعداد:

ننشئ مصفوفة تعداد (count array) بحجم يساوي النطاق المحدد، وكل عنصر في هذه المصفوفة يُمثل عدد مرات ظهور كل قيمة في مجموعة البيانات.

3. تعبئة مصفوفة التعداد:

نمر عبر مجموعة البيانات الأصلية ونزيد قيمة العنصر في مصفوفة التعداد المقابلة لكل عنصر في المجموعة الأصلية.

4. تعديل مصفوفة التعداد:

نعدل مصفوفة التعداد بحيث تحتوي كل قيمة على مجموع القيم التي تسبقها. هذا التعديل يساعدنا في تحديد المواضع الصحيحة للعناصر في المصفوفة النهائية.

5. بناء المصفوفة المرتبة:

نمر عبر مجموعة البيانات الأصلية مرة أخرى ونستخدم مصفوفة التعداد لتحديد المواضع الصحيحة للعناصر في المصفوفة المرتبة.

مزايا خوارزمية Counting Sort

تتميز خوارزمية Counting Sort بعدة مزايا تجعلها مناسبة لبعض الحالات الخاصة:

1. الكفاءة الزمنية:

تعمل خوارزمية Counting Sort في الزمن O(n + k)، حيث n هو عدد العناصر و k هو نطاق القيم. هذا يجعلها أسرع من خوارزميات الترتيب الأخرى مثل Quick Sort و Merge Sort في بعض الحالات.

2. الثبات:

تعد خوارزمية Counting Sort خوارزمية ثابتة، مما يعني أنها تحافظ على ترتيب العناصر المتساوية كما كانت في المجموعة الأصلية.

عيوب خوارزمية Counting Sort

على الرغم من مزاياها، إلا أن خوارزمية Counting Sort ليست خالية من العيوب:

1. قيود النطاق:

تكون خوارزمية Counting Sort غير عملية إذا كان نطاق القيم كبيرًا جدًا، حيث سيؤدي ذلك إلى زيادة حجم مصفوفة التعداد بشكل كبير.

2. الذاكرة:

تستهلك خوارزمية Counting Sort كمية كبيرة من الذاكرة إذا كان نطاق القيم كبيرًا، مما يجعلها غير مناسبة للأجهزة ذات الموارد المحدودة.

تطبيقات خوارزمية Counting Sort

تُستخدم خوارزمية Counting Sort في العديد من التطبيقات حيث تكون الكفاءة والسرعة هامة. من بين هذه التطبيقات:

1. ترتيب الأعداد الصحيحة:

تُستخدم هذه الخوارزمية بشكل واسع في ترتيب الأعداد الصحيحة التي تقع في نطاق محدود.

2. تحليل الترددات:

تُستخدم خوارزمية Counting Sort في تحليل الترددات وحساب عدد مرات ظهور كل عنصر في مجموعة بيانات معينة.

3. توزيع البيانات:

يمكن استخدام خوارزمية Counting Sort في توزيع البيانات عبر نطاقات محددة، مما يساعد في تحسين أداء بعض الخوارزميات الأخرى.

أمثلة على خوارزمية Counting Sort

دعونا نستعرض مثالاً عمليًا لتوضيح كيفية عمل خوارزمية Counting Sort:

مثال 1:

لنفترض أن لدينا مجموعة البيانات التالية: [4, 2, 2, 8, 3, 3, 1].

الخطوة 1: تحديد النطاق

نطاق القيم هو 0 إلى 8.

الخطوة 2: إنشاء مصفوفة التعداد

مصفوفة التعداد ستكون بحجم 9 (0 إلى 8) ومبدئيًا ستكون جميع القيم 0: [0, 0, 0, 0, 0, 0, 0, 0, 0].

الخطوة 3: تعبئة مصفوفة التعداد

بعد تعبئتها ستصبح: [0, 1, 2, 0, 1, 0, 0, 0, 1].

الخطوة 4: تعديل مصفوفة التعداد

بعد التعديل: [0, 1, 3, 3, 4, 4, 4, 4, 5].

الخطوة 5: بناء المصفوفة المرتبة

المصفوفة النهائية ستكون: [1, 2, 2, 3, 3, 4, 8].

خاتمة

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