مدونة التربية و التعليم في الجزائر – دروس، فروض، نتائج امتحانات مدونة التربية والتعليم في الجزائر | تحضير الدروس، فروض واختبارات، نتائج البكالوريا وBEM، مسابقات التوظيف، والتوجيه المدرسي للطلاب وأولياء الأمور.
خوارزميات الفرز: مقارنة بين 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).
تمارين
- طبق Insertion Sort خطوة بخطوة على القائمة [5, 2, 4, 6, 1, 3].
- قارن بين Insertion و Selection Sort من حيث الأداء في أفضل وأسوأ الحالات.
- أي خوارزمية تختار لترتيب قائمة شبه مرتبة؟ ولماذا؟
خلاصة
خوارزميات الفرز البسيطة (Bubble, Insertion, Selection) مناسبة للتعلم والقوائم الصغيرة. Insertion Sort الأفضل بينها للقوائم شبه المرتبة. للقوائم الكبيرة، استخدم خوارزميات متقدمة (Quick, Merge, Heap).
📍 دروس مشابهة
- المرجح في المستوي: مفهومه وخصائصه وتطبيقاته – الرياضيات — السنة الأولى ثانوي (ج
- الاحتمال الشرطي: مفهومه وقواعده والأحداث المستقلة – الرياضيات — السنة الأولى ثا
- الإحصاء الوصفي: مقاييس النزعة المركزية والتشتت – الرياضيات — السنة الأولى ثانوي