Golden man
03-01-2008, 02:07 PM
الفرز بالإقحام
Insertion Sort
تقوم فكرة هذا النوع من الفرز على ترتيب مجموعة العناصر كما يقوم البعض بترتيب أوراق الشدة حيث يتم أخذ العناصر واحدا تلو الآخر بداية من ثاني عنصر و مقارنته مع جميع العناصر التي قبله ) حيث تتم هذه العملية من الأعلى إلى الأسفل كما في المثال )
يتم أخذ رقم 7 و مقارنته مع 10 و وضعه في المكان المناسب و هو هنا في الأعلى و من ثم أخذ 5 و وضعه في المكان المناسب و هو هنا في الأعلى و هكذا ......... حتى يتم ترتيب العناصر بشكل تصاعدي مثلا (حسب الحاجة).
358
و بنفس الطريقة يتم فرز أي لائحة بمسحها كاملة بداية من ثاني عنصر و البحث عن المكان المناسب لإقحامه في العناصر التي قبله.
مثال: نريد فرز الائحة التالية فرزا تصاعديا.
359
تتم العملية على المراحل التالية
:
360
هنا نبحث عن مكان إقحام العدد 2 في المجموعة المحددة و نضعه بمكانه.
361
هنا نبحث عن مكان إقحام العدد 4 في المجموعة المحددة و نضعه بمكانه.
362
هنا نبحث عن مكان إقحام العدد 9 في المجموعة المحددة و نضعه بمكانه.
[363
هنا نبحث عن مكان إقحام العدد 3 في المجموعة المحددة و نضعه بمكانه.
364
هنا نبحث عن مكان إقحام العدد 6 في المجموعة المحددة و نضعه بمكانه.
365
بعد الانتهاء من عمليات الإقحام تم فرز المصفوفة.
خوارزمية الفرز:
1 for j ← 2 to length[A]
2 do key ← A[j]
3 i ← j - 1
4 while i > 0 and A[i] > key
5 do A[i + 1] ← A[i]
6 i ← i - 1
7 A[i + 1] ← key
و بالنسبة لدراسة تعقيد الخوارزمية (أسوأ حالة) فهو موجود في الملف التالي:
http://www.100hla.com/up/uploads/9546a74a19.rar
و هذا تابع الفرز بالإقحام بلغة C++ :
const int ARRDIM = 1000000;
int *InitArr = new int[ARRDIM];
void InsertionSort()
{
int key=0;
for(int j=1; j<ARRDIM; j++)
{
key = InitArr[j];
for(int i=j-1; InitArr[i] > key && i>=0; i--)
{
int tmp = InitArr[i];
InitArr[i] = InitArr[i+1];
InitArr[i+1] = tmp;
}
InitArr[i+1] = key;
}
}
Insertion Sort
تقوم فكرة هذا النوع من الفرز على ترتيب مجموعة العناصر كما يقوم البعض بترتيب أوراق الشدة حيث يتم أخذ العناصر واحدا تلو الآخر بداية من ثاني عنصر و مقارنته مع جميع العناصر التي قبله ) حيث تتم هذه العملية من الأعلى إلى الأسفل كما في المثال )
يتم أخذ رقم 7 و مقارنته مع 10 و وضعه في المكان المناسب و هو هنا في الأعلى و من ثم أخذ 5 و وضعه في المكان المناسب و هو هنا في الأعلى و هكذا ......... حتى يتم ترتيب العناصر بشكل تصاعدي مثلا (حسب الحاجة).
358
و بنفس الطريقة يتم فرز أي لائحة بمسحها كاملة بداية من ثاني عنصر و البحث عن المكان المناسب لإقحامه في العناصر التي قبله.
مثال: نريد فرز الائحة التالية فرزا تصاعديا.
359
تتم العملية على المراحل التالية
:
360
هنا نبحث عن مكان إقحام العدد 2 في المجموعة المحددة و نضعه بمكانه.
361
هنا نبحث عن مكان إقحام العدد 4 في المجموعة المحددة و نضعه بمكانه.
362
هنا نبحث عن مكان إقحام العدد 9 في المجموعة المحددة و نضعه بمكانه.
[363
هنا نبحث عن مكان إقحام العدد 3 في المجموعة المحددة و نضعه بمكانه.
364
هنا نبحث عن مكان إقحام العدد 6 في المجموعة المحددة و نضعه بمكانه.
365
بعد الانتهاء من عمليات الإقحام تم فرز المصفوفة.
خوارزمية الفرز:
1 for j ← 2 to length[A]
2 do key ← A[j]
3 i ← j - 1
4 while i > 0 and A[i] > key
5 do A[i + 1] ← A[i]
6 i ← i - 1
7 A[i + 1] ← key
و بالنسبة لدراسة تعقيد الخوارزمية (أسوأ حالة) فهو موجود في الملف التالي:
http://www.100hla.com/up/uploads/9546a74a19.rar
و هذا تابع الفرز بالإقحام بلغة C++ :
const int ARRDIM = 1000000;
int *InitArr = new int[ARRDIM];
void InsertionSort()
{
int key=0;
for(int j=1; j<ARRDIM; j++)
{
key = InitArr[j];
for(int i=j-1; InitArr[i] > key && i>=0; i--)
{
int tmp = InitArr[i];
InitArr[i] = InitArr[i+1];
InitArr[i+1] = tmp;
}
InitArr[i+1] = key;
}
}