خوارزم الحشر Insertion Sort Algorithm

Spread the love

خوارزم الحشر Insertion Sort Algorithm

(بواسطة : رسيــــس | بتاريخ : 10 أغسطس 2004 )

 

بسم الله الرحمن الرحيم

هاقد وصلنا إلى خوارزم الترتيب الثاني، سنتعرف في درس اليوم على:

خوارزم الحشر Insertion Sort Algorithm

تعمل هذه الطريقة على اعتبار أن هناك مصفوفتين، في البداية تحتوي إحداهما على البيانات المطلوب ترتيبها بمعنى الغير مرتبة unsorted والأخرى فارغة. وفي النهاية ستحتوي المصفوفة الفارغة على بيانات المصفوفة الأولى ولكن مرتبه إما تصاعدياً أو تنازلياً!

الفكرة الأساسية في هذه الطريقة هي تحريك العناصر من المصفوفة الأولى (الغير مرتبة العناصر) إلى المصفوفة الثانية عنصراً كل مرة مع مراعاة وضع العنصر المتحرك في مكانه الصحيح، ولكي نضع العنصر في مكانه الصحيحة في المصفوفة الثانية المرتبة العناصر بالنسبة لجميع العناصر التي سبقت هذا العنصر المتحرك، فإن هذه العملية قد تتطلب حشر هذا العنصر الجديد بين عنصرين مرتبين مسبقاً ليأخذ  مكانه الصحيح، من هنا أتى اسم هذا الخوارزم 🙂 انظر إلى flowchart التالي والذي يحاكي العملية:

هذا أبسط تمثيل لهذا الخوارزم باستخدام مصفوفتين! ………….. نعم وكما يتبادر إلى ذهنكم الآن يمكننا أن نمثل هذا الخوارزم باستخدام مصفوفة واحدة عن طريق حشر العنصر في مكانه الصحيح فيها ثم عمل shift لبقية العناصر وهكذا ستتقسم المصفوفة الواحدة إلى قسمين، قسم به العناصر المرتبة وقسم به العناصر الغير مرتبة:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::1

لنرى مثال على ذلك:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::2

لنمثله الآن برمجياً ,وباستخدام مصفوفة واحدة، الكود كاملاً موجود في برنامج “خوارزميات الترتيب” الذي قمت بتحميله من درس المقدمة، هذا هو:

// array of integers to hold values
private int[] a = new int[100];

// number of elements in array
private int x;

// Insertion Sort Algorithm
public void sortArray()
{
int i;
int j;
int index;

for( i = 1; i < x; i++ )
{
index = a[i];
j = i;

while( (j > 0) && (a[j-1] > index) )
{
a[j] = a[j-1];
j = j – 1;
}

a[j] = index;
}
}

وكما رأيتم فهي من حيث السرعة مناسبة لتطبق على مصفوفة ذات ألف عنصر أو أقل. هذا الخوارزم يعتبر أسرع مرتين من طريقة الفقاعة Bubble كما أنه أسرع 40% كذلك من خوارزم التحديد Selection التي سنتعرف عليها الدرس المقبل بإذن الله.

هذه هي النتيجة باستخدام برنامجنا:

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::3

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::4

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::6

رائع، أليس كذلك، هذه الخوارزميات تعطينا خيال برمجي كبير جداً

تابعنا في الدرس القادم ومع خوارزم جديد 🙂

معلومة إضافية متقدمة:

لو استخدمنا مفهوم Big-Oh Notation لتحليل هذا الخوارزم لاستنتجنا أن أسوأ حالات تطبيق هذا الخوارزم هي عندما يكون (O(n2 وهو نفسه درجة فعالية هذا الخوارزم في الحالة القياسية.

الكاتب geek4arab

geek4arab

مواضيع متعلقة

التعليقات مغلقة