اختيار نوع

مرحبا. لقد كتبت هذه المقالة خصيصًا لإطلاق دورة "الخوارزميات وهياكل البيانات" من OTUS.

---

المقدمة

يعد تصنيف المصفوفة من أولى المشكلات الخطيرة التي تمت دراستها في الدورة الكلاسيكية "الخوارزميات وهياكل البيانات" في تخصص علوم الكمبيوتر. في هذا الصدد ، غالبًا ما تتم مواجهة مهام كتابة الأنواع والأسئلة المقابلة في المقابلات كمتدرب متدرب أو مبتدئ.

صياغة المشكلة

تقليديا ، يجدر البدء في تقديم حلول للمشكلة مع بيانها. عادة ما تتضمن مهمة الفرز طلب مجموعة من الأعداد الصحيحة بترتيب تصاعدي. لكن في الواقع ، هذا تبسيط مفرط إلى حد ما. يمكن استخدام الخوارزميات الموضحة في هذا القسم لترتيب مصفوفة من أي كائنات يتم إنشاء علاقة ترتيب بينها (أي ، بالنسبة لأي عنصرين يمكننا أن نقول: الأول أكبر من الثاني ، والثاني أكبر من الأول ، أو متساويان). يمكنك الفرز بترتيب تصاعدي وتنازلي. سنستخدم التبسيط القياسي.

اختيار نوع

من أبسط أنواع الفرز التحديد.

وصف الخوارزمية

يتم فرز المصفوفة حسب التحديد على النحو التالي: يتم تقسيم المصفوفة إلى قسمين. جزء واحد يسمى الفرز والآخر غير مفروز. تفترض الخوارزمية اجتياز المصفوفة بالكامل بحيث يصبح طول الجزء المصنف مساوًا لطول المصفوفة بأكملها. داخل كل تكرار ، نجد الحد الأدنى في الجزء غير المصنف من الصفيف ونستبدل هذا الحد الأدنى بالعنصر الأول للجزء غير المصنف من الصفيف. ثم نقوم بزيادة طول الجزء المصنف من الصفيف بمقدار واحد. وفيما يلي مثال لتكرار واحد:

1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8

التنفيذ

أقترح النظر في تنفيذ هذه الخوارزمية في C:

void choiseSortFunction(double A[], size_t N)
{
    for(size_t tmp_min_index = 0; tmp_min_index < N;
                                  tmp_min_index++) {
        // 
        for(size_t k = tmp_min_index + 1; k < N; k++) {
            if (A[k] < A[tmp_min_index]) {
                double min_value = A[k];
                A[k] = A[tmp_min_index];
                A[tmp_min_index] = min_value;
            }
        }
    }
}

تحليل

أقترح تحليل هذه الخوارزمية. يأخذ جسم الحلقة الداخلية نفسها O (1) ، أي أنها لا تعتمد على حجم المصفوفة التي يتم فرزها. هذا يعني أنه لفهم الخطوط المقاربة للخوارزمية ، من الضروري حساب عدد المرات التي يتم فيها تنفيذ هذا الجسم. عند التكرار الأول للحلقة الخارجية ، هناك تكرار (n - 1) للحلقة الداخلية. في التكرار الثاني للحلقة الخارجية - (n - 2) التكرارات للحلقة الداخلية. استمرارًا لهذا المنطق ، نصل إلى ما يلي:

$$

$$T(n) = (n - 1) * O(1) + (n - 2) * O(1) + ... + O(1) = O((n - 1) + (n - 2) + ... + 1) = O((n - 1) * n / 2) = O(n ^ 2)$$

في عملية الحسابات ، استخدمنا أولاً خصائص الترميز O ، ثم الصيغة لحساب مجموع التقدم الحسابي.



بالنسبة للطلب ، من الضروري أيضًا تقدير الذاكرة الإضافية المطلوبة لتنفيذ الخوارزمية. كل شيء أكثر بساطة هنا: لقد خصصنا ذاكرة فقط لعدادات الحلقة ومتغير - مخزن مؤقت ، والذي يسمح بتبديل عنصري صفيف. وبالتالي:

$$

$$M(n) = O(1)$$

نتيجة للتحليل ، توصلنا إلى استنتاج مفاده أن تعقيد الخوارزمية يعتمد على حجم صفيف الإدخال بشكل تربيعي. لذلك ، ينتمي هذا التصنيف إلى فئة الأنواع التربيعية . لا تعتمد نتيجة التحليل على محتوى المصفوفة: فهي صحيحة في أحسن الأحوال ، وأسوأها ، وفي المتوسط.



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

نوع التحديد على الوجهين

قد يكون تحسين الخوارزمية التي تم تنفيذها أعلاه أمرًا ذا أهمية: أثناء المشي خلال الجزء غير المصنف من المصفوفة ، يمكنك البحث عن الحد الأقصى بالتوازي مع الحد الأدنى للعنصر. وبالتالي ، بعد التكرار ، يمكنك تقليل الجزء غير المصنف من الصفيف ليس بمقدار واحد ، ولكن بمقدار اثنين. لا تتحسن الخوارزمية بشكل تقارب ، ولكن مع ذلك ، قد تزيد سرعة تنفيذها قليلاً ، كما يتضاعف عدد المقارنات أيضًا.

فرز التحديد العودي

كتمرين ، يمكنك محاولة كتابة خوارزمية لا تستخدم حلقة ، ولكن باستخدام العودية. في جافا قد تبدو كالتالي:

public static int findMin(int[] array, int index){
    int min = index - 1;
    if(index < array.length - 1) min = findMin(array, index + 1);
    if(array[index] < array[min]) min = index;
    return min;
}
  
public static void selectionSort(int[] array){
    selectionSort(array, 0);
}
  
public static void selectionSort(int[] array, int left){
    if (left < array.length - 1) {
        swap(array, left, findMin(array, left));
        selectionSort(array, left+1);
    }
}
  
public static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

النتيجة

نظرنا إلى أحد الأنواع التربيعية: فرز الاختيار ، نظرنا إلى تنفيذ مستقر باستخدام حلقة ، العودية ، تحسين الخوارزمية التي تمت مناقشتها من خلال تقليل اتجاهين للجزء غير المصنف من الصفيف. الفرز تعليمي بحت ولم يتم تطبيقه على نطاق واسع في الممارسة.

---

إذا كنت ترغب في معرفة المزيد عن الدورة ، فأنا أدعو الجميع إلى ندوة مجانية عبر الإنترنت ، والتي ستعقد في 10 يوليو .

---