fbpx
الفضائيون

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

المُساهمون:
  • إعداد: نور عبدو

إضافة تعليق

الفضائيون

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