ترتيب بالإدراج


مستوى الصعوبة متوسط
كثيرا ما يطلب في اكسنتشر سيسكو ديل Grofers جونيبر نتوركس MAQ فيريتاس
مجموعة فرز

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

الإدخال: 9,5,1,6,11,8,4 {}

الإخراج: 1,4,5,6,8,9,11 {}

نظرية

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

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

  1. حدد / حدد العنصر الأول في مصفوفة غير مرتبة ، وانقله إلى الموضع الصحيح في المصفوفة المرتبة.
  2. تقدم العلامة إلى العنصر التالي في مصفوفة لم يتم فرزها.

ترتيب بالإدراج

برنامج C ++

#include <iostream>
using namespace std;

void insertSort(int arr[],int n)
{
    int i,j,save;

    for(int i=1;i<n;i++)
    {
        j = i-1;
        save = arr[i];
        
        // look for correct position of arr[i]
        while(j>=0 && arr[j] > save)
        {
            // shifting array elements towards the right
            arr[j+1] = arr[j];
            j--;
        }
        // place arr[i] at the correct position
        arr[j+1] = save;
    }
}

int main()
{
    
    int arr[] = {9,5,1,6,11,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    insertSort(arr,n);

    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    
    return 0;
}

الناتج

1 4 5 6 8 9 11

برنامج جافا

class iSort
{
    static void insertSort(int arr[])
    {
        int n = arr.length;
        int i,j,save;

        for(i=1;i<n;i++)
        {
            j = i-1;
            save = arr[i];

            // look for correct position of arr[i]
            while(j >= 0 && arr[j] > save)
            {
                // shifting array elements towards the right
                arr[j+1] = arr[j];
                j--;
            }
            // place arr[i] at the correct position
            arr[j+1] = save;
        }
    }

    public static void main(String args[]) 
    {
        int arr[] = {9,5,1,6,11,8,4};
        insertSort(arr);

        for(int i=0;i<arr.length;i++)
        System.out.print(arr[i] +" ");   
    }
}

الناتج

1 4 5 6 8 9 11

تحليل التعقيد

  • تعقيد الوقت: T (ن) = O (ن2)
  • يستغرق الأمر O (n2) الوقت الذي يتم فيه فرز المصفوفة بشكل عكسي والوقت الذي يتم فيه فرز المصفوفة O (n).
  • تعقيد الفضاء: أ (ن) = س (1)

معلومات تكميلية

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

الرقم المرجعي  اسئلة المقابلة