شرح الترتيب بالعد في بايثون counting sort

شرح خوارزمية الترتيب بالعد في بايثون counting sort

كيف تعمل خوارزمية الترتيب بالعد counting sort؟

تعمل خوارزمية الترتيب بالعد counting sort من خلال انشاء قائمة جديدة يكون عدد عناصرها يساوي قيمة اكبر عنصر في المصفوفة المراد ترتيبها ، ثم عد العناصر وتخزين عددهم في القائمة الجديدة بحيث يكون عدد كل عنصر علي نفس رقم الفهرس المساوي له، وبعد ذلك اعادة كتابة المصفوفة الاصلية.

تحليل الكود الموجود في محرر بايثون بالاعلي

متغير m يحتوي علي قيمة اكبر عنصر في المصفوفة mylist مع اضافة 1 وهذا لان الفهرس يبدا من رقم صفر الي 7.

ومتغير count سوف يحتوي علي قائمة مكونة من 8 عناصر قيمتهم صفر.

[0, 0, 0, 0, 0, 0, 0, 0]

سوف تستخدم القائمة السابقة لعد كل رقم داخل فهرسة اذا كان العنصر قيمتة صفر سوف يتم زيادة قيمة فهرس صفر بمقدار رقم واحد ( 1 ) ، واذا كان قيمة العنصر هي 5 يتم زيادة قيمة فهرس 5 بمقدار واحد ( 1 ).

مثال

اذا كانت المصفوفة المراد ترتيبها كالتالي

[1, 2, 7, 3, 2, 1, 4, 2, 3, 2, 1]

سوف تكون قيمة متغير count بعد عد عدد العناصر كالتالي

[0, 3, 4, 2, 1, 0, 0, 1]

كما تشاهد تم عد الارقام وتخزين عددها كل منها علي رقم فهرسه، وبما ان المصفوفة mylist لا تحتوي علي اي رقم صفر لم تتغير قيمة الفهرس 0 في count ، وتم اضافة رقم 3 في الفهرس 1 ؛ لان رقم واحد تكرر ثلاث مرات في المصفوفة mylist.

اعادة كتابة المصفوفة mylist

بعد ان تم عد كل عناصر المصفوفة وتخزين اعدادهم ياتي دور اعادة كتابة المصفوفة مع ترتيبها.

في البداية يتم التعريف عن متغير i بقيمة 0 وسوف يستخدم للفهرسة.

بعد ذلك تستخدم حلقة تكرار فرعية في نطاق متغير m من 0 الي 8 وهي عدد عناصر القائمة count، وتمتلك الحلقة متغير التكرار a والذي سوف نستخدمة في شكل قيمة، وفهرس.

for a in range(m):

وفي حلقة التكرار الفرعية سوف يكون التكرار في نطاق قيمة قيمة فهرس a في القائمة count ، وفي اول تكرار في الحلقة الرئيسية سوف تكون قيمة a تساوي 0 وقيمة فهرس 0 في count هي 0.

for c in range(count[a]):
  arr[i] = a
  i += 1

لاحظ ان النطاق range يجب ان يكون من 0 الي 1 علي الاقل، وبما ان اول تكرار a يساوي 0 فان الحلقة الفرعية في اول تكرار لن تعمل، ولن يتم اضافة الصفر الي القائمة الجديدة mylist.

وهذا ما سوف يحدث مع كل القيم الصفرية في count ، غير ذلك سوف يتم اضافة قيمة a الي الفهرس i في المصفوفة arr وزيادة i بمقدار واحد 1.

بعد الانتهاء من كل حلقات التكرار يتم ارجاع المصفوفة arr المرتبة.

الي هنا نكون قد شرحنا الترتيب بالعد counting sort اذا كان لديك اي استفسار او ملاحظة لا تتردد في مراسلتنا.