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

