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