خوارزمية فرز الإدراج في Java مع مثال البرنامج

ما هي خوارزمية فرز الإدراج؟

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

• إزالة عنصر من مصفوفة.
• يقارنها بأكبر قيمة في مجموعة.
• ينقل العنصر إلى موقعه الصحيح.

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

وهو ينتمي إلى نفس فئة المنتجات المناسبة للمبتدئين Java إجراءات الفرز كـ فقاعة الفرزومع ذلك، فإنه عادةً ما يقوم بعمليات كتابة أقل بكثير على البيانات المرتبة جزئيًا بالفعل.

عملية خوارزمية فرز الإدراج

إليك كيفية عمل خوارزمية فرز الإدراج بيانياً:

يكرر الرسم المتحرك نفس الخطوات الثلاث Java البرنامج أدناه يعمل. جدول التشغيل التجريبي tracيقوم هذا البرنامج بتنفيذ تلك الخطوات على مصفوفة العينة {860، 8، 200، 9}، تمامًا كما يطبعها البرنامج في وقت التشغيل.

لاحظ أن المرور الثالث يتطلب مقارنتين لأن المفتاح 9 يجب أن يمر بقيمتين أكبر. وبالتالي، يزداد عدد المقارنات مع ازدياد بُعد كل عنصر عن الترتيب الصحيح.

Java مثال برنامج لفرز صفيف باستخدام خوارزمية فرز الإدراج:

يقوم البرنامج أدناه بترتيب المصفوفة {860, 8, 200, 9} ويطبع تعليقًا توضيحيًا، بحيث تكون كل مقارنة وكل إزاحة مرئية. احفظه باسم InsertionSortExample.java وقم بتجميعه باستخدام أي إصدار من JDK 8 أو إصدار أحدث.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

يؤدي تشغيل الفصل إلى إنتاج tracكل ما هو موضح هنا. رقم تمرير الفرز يشير الخط إلى تكرار واحد للحلقة الخارجية، ويُظهر الخط المطبوع بعد كل عملية تبديل المصفوفة كما هي في تلك اللحظة.

Code الإخراج:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

تعقيد الوقت والمساحة لفرز الإدراج

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

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

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

مزايا وعيوب فرز الإدخال

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

المزايا

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

عيوب

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

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

فرز الإدراج مقابل Bubblفرز e مقابل فرز التحديد

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

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

الأسئلة الشائعة