خوارزميات الترتيب
| English | العربية |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | الترتيب |
| selection sort/sɪˈlekʃn sɔːt/ | فرز الاختيار |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | فرز الإدراج |
| in place/ɪn pleɪs/ | في المكان |
ترتيب الأشياء
- الترتيب يعيد ترتيب العناصر في تسلسل (من الأصغر للأكبر، على سبيل المثال).
- يغطي منهج AP نوعين من الترتيبات البسيطة: ترتيب الاختيار وترتيب الإدراج.
- كلاهما يستخدم حلقات متداخلة ويقوم بتبديل أو إزاحة العناصر في مكانها.
- الترتيب أولاً هو ما يسمح لك باستخدام البحث الثنائي السريع لاحقاً.
فرز بالاختيار
- ابحث عن أصغر عنصر متبقٍ وقم بـ تبديله مع العنصر الأول.
- ثم ابحث عن أصغر ما تبقى، قفله في المكان التالي، وهكذا.
- الجزء الأمامي من المصفوفة يتحول إلى مرتب؛ بينما ينكمش الجزء الخلفي ليكون غير مرتب.
- عملية تبديل واحدة في كل دورة — لكنها لا تزال تفحص الباقي في كل مرة.
فرز الإدراج
- خذ العنصر التالي وزيّده للخلف ليصل لمكانه الصحيح بين العناصر المرتبة مسبقاً.
- مثل ترتيب مجموعة أوراق: ضع كل ورقة جديدة حيث يجب أن تكون.
- المنطقة المرتبة تزداد بعنصر واحد في كل دورة.
- سريع عندما تكون البيانات مرتبة تقريباً بالفعل.
حجم الجهد المبذول
- كلا الفرزين يستخدم حلقات متداخلة، لذا ينفذان حوالي
n²مقارنة في أسوأ الحالات. - هذا مقبول للمصفوفات الصغيرة لكنه بطيء جداً للمصفوفات الكبيرة.
- يرتبان محلياً — لا حاجة لمصفوفة ثانية.
- الامتحان يطلب منك تتبع خطواتهما، وليس فقط تسمية الخوارزميات.
فرز بالاختيار يقوم بـ تبديل أصغر عنصر متبقي للأمام؛ وفرز الإدراج يقوم بإزاحة كل عنصر جديد للخلف ليدخل في الجزء المرتب — لا تخلط بينهما. كلاهما فرز باستخدام حلقات متداخلة من الرتبة O(n²) ويترتبان محلياً. تابع الخطوات خطوة بخطوة (امتحان AP يطلب حالة المصفوفة بعد كل دورة)، بدلاً من حفظ الأسماء.
فرز بالاختيار على [3, 1, 2]:
- الدورة 1: الأصغر هو
1؛ التبادل للأمام →[1, 3, 2]. - الدورة 2: الأصغر في
[3, 2]هو2؛ التبادل →[1, 2, 3]. - مرتب — لقد زاد الجزء الأمامي بعنصر واحد في كل دورة.
الفرز يرتب العناصر. فرز بالاختيار يقوم بشكل متكرر بـ تبديل أصغر عنصر متبقي للأمام؛ فرز الإدراج يقوم بـ إزاحة كل عنصر جديد للخلف ليدخل في الجزء المرتب. كلاهما استخدام حلقات متداخلة، ترتب محلياً، وهو من الرتبة O(n²). الفرز يمكّن لاحقاً من إجراء بحث ثنائي سريع.
مرور خطوات الترتيب
كل مرور يضع عنصراً إضافياً في مكانه الصحيح.
عملية اختيار الترتيب تعمل عبر...
اختيار الترتيب يحدد الأدنى ويبدله للأمام.
عملية إدراج الترتيب تعمل عبر...
إدراج الترتيب يُدرج كل عنصر في مكانه المرتب.
في أسوأ الحالات، تقوم كلا عمليتي الترتيب بـ...
الحلقات المتداخلة تعطي O(n²).
كلا عمليتي الاختيار والإدراج تعملان محلياً (بدون مصفوفة ثانية).
تعيد ترتيب نفس المصفوفة.
رتب مراحل عملية اختيار الترتيب على [3, 1, 2].
الأمام ينمو مرتباً، عنصر واحد لكل مرحلة.
الترتيب مسبقاً مفيد لأنه يسمح لاحقاً باستخدام...
البحث الثنائي يتطلب بيانات مرتبة.