ترتيب بالإدراج
من ويكيبيديا، الموسوعة الحرة
الترتيب بالإدراج هو الترتيب الأفضل بالنسبة للقوائم الصغيرة.
المبدأ بسيط: هذا الترتيب يتم استعماله من أي شخص يريد مثلا ترتيب ملفاته أو أوراقه، يتم وضع ملف في مكانه ضمن الملفات التي سبق ترتيبها، ثم نمر إلى الملف الموالي.
[تحرير] خصائص
عدد المفارنات اللازمة من الرتبة N²/4. معدل التبديلات من الرتبة 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] */
        }
}
| 
 | |

