in

خوارزمية الفرز بالاختيار Selection Sort

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

تحدّثنا في مقال سابق عن خوارزمية الفرز الفقاعي (Bubble Sort)، الآن سنكمل في سلسلتنا ونبدأ بالحديث عن خوارزمية الفرز بالاختيار (Selection Sort).

ماهي خوارزمية الفرز بالاختيار؟

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

ماهي آلية عمل الخوارزمية؟

فلنفترض أنّ لدينا مصفوفة A غير مرتبة تحتوي على n عنصر، والمطلوب هو ترتيب العناصر تصاعدياً، فلنفرض أن المصفوفة تحتوي على العناصر الآتية : {7 , 5 , 4 , 2}

أولاً؛ نبحث عن العنصر الأصغر في المصفوفة (في مثالنا هو الرقم 2). ثانيًا؛ نقوم بالتبديل بينه وبين العنصر الذي يقع في الخانة الأولى من المصفوفة (في مثالنا هو الرقم 7). الآن، نبحث عن العنصر الأصغر من بين العناصر المتبقية من المصفوفة ونضعه في الخانة الثانية، وهكذا دواليك حتى يتم ترتيب جميع العناصر تصاعديًا.

مثال برمجي لتوضيح آلية العمل:

https://gist.github.com/YassineBajdou/1a2f7ce5a117263f44eed0694e3d3d08

درجة تعقيد الخوارزمية (Time Complexity)

تعقيد تربيعيO(n2).

السبب: لإيجاد العنصر الأصغر من بين N عنصر تحتاج إلى N-1 عملية مُقارنة، وبعد وضعه في المكان المناسب (عملية تبديل واحدة) يتبقى N-1 عنصر بحاجة إلى ترتيب. ولإيجاد العنصر الأصغر من بينها تحتاج إلى N-2 مُقارنة، وهكذا. وبالتالي، النتيجة هي:

(N-1) + (N-2) + … +1 = (N . (N-1)) / 2 (عدد عمليات المقارنة)

N  (عدد عمليات التبديل)

لتكون النتيجة النهائية من رتبة O(n2)

  • إعداد: نور عبدو.

بواسطة نور عبدو

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني.

الملاقيط الضوئية، وتوليد نبضات ضوئية عالية الكثافة

ما هو المميز في خلايا الدماغ البشري؟