Module: الأنواع التربيعية

إدراج فرز

فرز الإدراج & nbsp؛ ( ترتيب الإدراج ) & nbsp؛ & mdash؛ & nbsp ؛ خوارزمية الفرز التي يتم فيها البحث عن عناصر تسلسل الإدخال واحدًا تلو الآخر ، ويتم وضع كل عنصر وارد جديد في المكان المناسب بين العناصر التي تم فرزها مسبقًا.

أدخل الترتيب & ndash؛ إنها خوارزمية بسيطة للغاية ولكنها غير فعالة ومع ذلك لها العديد من المزايا المحددة التي تجعلها ذات صلة حتى بعد تطوير العديد من الخوارزميات الأخرى الأكثر كفاءة بشكل عام.

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

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

تنفيذ حسابي لهذه الخوارزمية <قبل> // يعتبر العنصر الفارغ تسلسلاً تم فرزه بالفعل. // لذلك تبدأ الحلقة من 1 الحلقات الخاصة بـ I = 1 إلى N-1 الخطوة 1 X = A [I] J = أنا عندما J & gt؛ 0 AND A [J-1] & gt؛ X // يبحثان عن مكان لإدراجه تبادل أ [J] ، أ [J-1] J = J-1 في النهاية وداعا أ [J] = X بعدها انا التعقيد الحسابي: & nbsp؛ \ (\ displaystyle O (n ^ {2}) \) .