فرز حسب إدراج

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

---

المقدمة

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

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

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

فرز حسب إدراج

تحدثنا في المرة الأخيرة عن أحد أبسط الأنواع - فرز الاختيار . سنركز اليوم على خوارزمية أكثر تعقيدًا قليلاً - فرز الإدراج.

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

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

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

التنفيذ

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

void insertionSortFunction(double array[], int size) {
    int i, j, temp;
    // i     ,   1,         
    for (i = 1; i < size; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] < temp) {
                break;
            }
  
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}

تحليل

أقترح تحليل هذه الخوارزمية.



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

$$

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

...



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



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

$$

$$T(n) = (n - 1) * O(1) = O(n)$$

وبالتالي ، يتم الفرز في الوقت الخطي.



في أسوأ الأحوال ، يُفترض أن يكون عدد التكرارات هو الأكبر ، أي أن الكسر لا يشتعل. في التكرار الأول للحلقة الخارجية ، يتم تنفيذ تكرار واحد للحلقة الداخلية. في التكرار الثاني للحلقة الخارجية ، يتم تنفيذ 2 تكرار للحلقة الداخلية. بمواصلة التفكير ، يمكن للمرء أن يستنتج أنه في الماضي (n - 1) - th) سيتم تكرار تكرار الحلقة الخارجية (n - 1) للحلقة الداخلية. نحن نحصل:

$$

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

لإجراء الحسابات ، استخدمنا خصائص O - الترميز وصيغة مجموع التقدم الحسابي.



في الحالة المتوسطة ، يُفترض أن عدد تكرارات الحلقة الداخلية لتكرار معين للحلقة الخارجية يساوي متوسط ​​قيمته ، أي التوقعات الرياضية. افترض أن جميع الأرقام المسموح بها لإطلاق الحلقة الداخلية محتملة بنفس القدر. في هذه الحالة ، يكون متوسط ​​عدد التكرارات للحلقة الداخلية . من المفترض أن أكون رقم التكرار للحلقة الخارجية. الآن ، لحساب الخطوط المقاربة ، تحتاج إلى الحساب . أي أننا نحسب فقط عدد المرات التي يتم فيها تنفيذ جسم الحلقة الداخلية. وهكذا نحصل .



وباختصار ، فإن الخطوط المقاربة للخوارزمية الذاكرة

$$

$$O(1)$$

في الوقت المناسب على أفضل تقدير

$$

$$O(n)$$

وفي المتوسط ​​وأسوأ الحالات

$$

$$O(n^2)$$

لذلك ، ينتمي هذا التصنيف إلى فئة الأنواع التربيعية .



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

النتيجة

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

$$

$$O(n)$$

ترتيب حجم البيانات.

---

تعلم المزيد عن الدورة.

---