تصنيف الإدراج: ما هو وكيف يعمل

فرز الإدراج عبارة عن خوارزمية فرز بسيطة لعدد صغير من العناصر.

مثال:

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

ابدأ من الفهرس 1 إلى حجم صفيف الإدخال.

[8 3 5 1 4 2]

الخطوة 1 :

 key = 3 //starting from 1st index. Here `key` will be compared with the previous elements. In this case, `key` is compared with 8. since 8 > 3, move the element 8 to the next position and insert `key` to the previous position. Result: [ 3 8 5 1 4 2 ]

الخطوة 2 :

 key = 5 //2nd index 8 > 5 //move 8 to 2nd index and insert 5 to the 1st index. Result: [ 3 5 8 1 4 2 ]

الخطوه 3 :

 key = 1 //3rd index 8 > 1 => [ 3 5 1 8 4 2 ] 5 > 1 => [ 3 1 5 8 4 2 ] 3 > 1 => [ 1 3 5 8 4 2 ] Result: [ 1 3 5 8 4 2 ]

الخطوة الرابعة:

 key = 4 //4th index 8 > 4 => [ 1 3 5 4 8 2 ] 5 > 4 => [ 1 3 4 5 8 2 ] 3 > 4 ≠> stop Result: [ 1 3 4 5 8 2 ]

الخطوة الخامسة:

 key = 2 //5th index 8 > 2 => [ 1 3 4 5 2 8 ] 5 > 2 => [ 1 3 4 2 5 8 ] 4 > 2 => [ 1 3 2 4 5 8 ] 3 > 2 => [ 1 2 3 4 5 8 ] 1 > 2 ≠> stop Result: [1 2 3 4 5 8]

الخوارزمية الموضحة أدناه هي نسخة محسنة قليلاً لتجنب تبديل keyالعنصر في كل تكرار. هنا ، keyسيتم تبديل العنصر في نهاية التكرار (الخطوة).

 InsertionSort(arr[]) for j = 1 to arr.length key = arr[j] i = j - 1 while i > 0 and arr[i] > key arr[i+1] = arr[i] i = i - 1 arr[i+1] = key

فيما يلي تنفيذ مفصل في JavaScript:

function insertion_sort(A) { var len = array_length(A); var i = 1; while (i 
    
     = 0 && A[j] > x) { A[j + 1] = A[j]; j = j - 1; } A[j+1] = x; i = i + 1; } }
    

يظهر تنفيذ سريع في Swift أدناه:

 var array = [8, 3, 5, 1, 4, 2] func insertionSort(array:inout Array) -> Array{ for j in 0..
    
      0 && array[i] > key){ array[i+1] = array[i] i = i-1 } array[i+1] = key } return array }
    

يظهر مثال Java أدناه:

public int[] insertionSort(int[] arr) for (j = 1; j 
    
      0 and arr[i] > key) { arr[i+1] = arr[i] i -= 1 } arr[i+1] = key } return arr;
    

نوع الإدراج في ج ....

void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i = 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } 

الخصائص:

• تعقيد الفضاء: O (1)

تعقيد الوقت: O (n)، O (n * n)، O (n * n) للحالات الأفضل والمتوسطة والأسوأ على التوالي.

• أفضل حالة: تم فرز المصفوفة بالفعل
• متوسط ​​الحالة: يتم فرز المصفوفة عشوائيًا
• أسوأ حالة: يتم فرز المصفوفة بشكل عكسي.
• الفرز في المكان: نعم
• مستقر: نعم

مصادر أخرى:

• ويكيبيديا
• CS50 - يوتيوب
• SortInsertion - GeeksforGeeks ، يوتيوب
• إدراج فرز التصور
• فرز الإدراج - MyCodeSchool
• فرز الإدراج - VisuAlgo