خوارزميات الفرز: مقارنة بين Insertion و Selection – الإعلام الآلي — السنة الأولى ثانوي (جذع مشترك علوم وتكنولوجيا) — المنهاج الجزائري

خوارزميات الفرز: مقارنة بين Insertion و Selection

بعد التعرف على Bubble Sort، نقدم خوارزميتين أخريين: Insertion Sort (الفرز بالإدراج) و Selection Sort (الفرز بالاختيار). لكل منهما مزايا وعيوب من حيث السرعة والبساطة.

الفرز بالإدراج (Insertion Sort)

فكرة: بناء القائمة المرتبة عنصراً عنصراً بأخذ عنصر من القائمة غير المرتبة وإدراجه في الموضع الصحيح في القائمة المرتبة. يشبه ترتيب أوراق اللعب في اليد. التعقيد: O(n^2) في أسوأ الحالات، O(n) في أفضل الحالات (قائمة شبه مرتبة). جيد للقوائم الصغيرة أو القريبة من الترتيب.

الفرز بالاختيار (Selection Sort)

فكرة: إيجاد أصغر عنصر في القائمة وتبديله مع العنصر الأول، ثم إيجاد ثاني أصغر عنصر وتبديله مع الثاني، وهكذا. التعقيد: O(n^2) في جميع الحالات (لا يتأثر بترتيب القائمة). بسيط لكن غير فعال للقوائم الكبيرة.

مقارنة الخوارزميات

أسوأ حالة: الثلاثة O(n^2). أفضل حالة: Insertion O(n)، Bubble O(n) (مع تحسين)، Selection O(n^2). الاستخدامات: Insertion للقوائم شبه المرتبة، Selection للقوائم الصغيرة، وإلا استخدم خوارزميات أسرع (Quick Sort, Merge Sort).

تمارين

1. طبق Insertion Sort خطوة بخطوة على القائمة [5, 2, 4, 6, 1, 3].
2. قارن بين Insertion و Selection Sort من حيث الأداء في أفضل وأسوأ الحالات.
3. أي خوارزمية تختار لترتيب قائمة شبه مرتبة؟ ولماذا؟

خلاصة

خوارزميات الفرز البسيطة (Bubble, Insertion, Selection) مناسبة للتعلم والقوائم الصغيرة. Insertion Sort الأفضل بينها للقوائم شبه المرتبة. للقوائم الكبيرة، استخدم خوارزميات متقدمة (Quick, Merge, Heap).