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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
ترتيب بالإدراج لمجموعة اعداد, الخط الافقي هو المؤشر

الترتيب بالإدراج هو الترتيب الأفضل بالنسبة للقوائم الصغيرة ولكنه ليس الأمثل للاستخدام في القوائم الكبيرة.

المبدأ بسيط: هذا الترتيب يتم استعماله من أي شخص يريد مثلا ترتيب ملفاته أو أوراقه، يتم وضع ملف في مكانه ضمن الملفات التي سبق ترتيبها، ثم نمر إلى الملف الموالي.

خصائص[عدل]

  • عدد المفارنات اللازمة من الرتبة  \frac{n^2}{4}.
  • معدل التبديلات من الرتبة  \frac{n^2}{2}.
  • تعقيد الخوارزم:  \mathcal{O} ( n^2 )

مثال[عدل]

مثال بسيط لترتيب بالإدراج في C

typedef int tab_entiers[MAX];
 
void insertion(tab_entiers t) {
        /* Spécifications externes : Tri du tableau t par insertion séquentielle */
        int i،p،j،x;
        for(i = 1 ; i < MAX ; i++) {
                /* Calcul de la position d'insertion p : */
                /* détermine le plus petit indice p       / 0 <= p <= i */
                /* qui vérifie t[p] >= t[i] */
                p = 0;
                while(t[p] < t[i]) p++;
 
                x = t[i]; /* Sauvegarde de t[i] */
 
                for(j = i-1 ; j >= p  ; j--) t[j+1] = t[j]; /* translation de t[p..i-1] vers t[p+1..i] */
 
                t[p] = x; /* insertion de t[p] */
        }
}

مثال بلغة c++

template <class T> void insertionSort(std::vector<T>& v, int fin) {

   int i, j, index;
   for (i=1; i <fin; i++) {
       index = v.at(i);
       j = i-1;
       while (j >= 0 && v.at(j)>index) {
           v.at(j+1)=v.at(j);
           j--;
       }
       v.erase(v.begin()+j+1);
       v.insert(v.begin()+j+1,index);
   }

}

مثال بلغة جافا

public static void insertSort (int[] v) {

     for (int i=1; i<v.length; i++) {
        int aux = v[i];
        int j;
        for (j=i-1; j>=0 && v[j]>aux; j--)
           v[j+1] = v[j];
        v[j+1] = aux;
     }
  }

مثال بلغه Visual Basic .NET

Private Sub insertionSort(ByVal numbers() As Integer)()

       Dim i, j, index As Integer
       i = 1

       Do
           index = numbers(i)
           j = i - 1

           While ((j >= 0) And (numbers(j) > index))
               numbers(j + 1) = numbers(j)
               j = j - 1
               If j < 0 Then  
                   Exit While
               End If
           End While
           numbers(j + 1) = index
           i = i + 1
       Loop Until i > (UBound(v))
   End Sub
خوارزميات الترتيب

بالفقاعات · بالإختيار · بالإدراج · سريع ·