شرح خوارزمية الترتيب بالإدخال [سطر سطر]

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

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

للتعبير عن الخوارزمية يُستخدم ما يعرف بالسودوكود و هو عبارة عن تعبير للخوارزمية بأي طريقة كانت ولا يعتبر كود حقيقي أي لا يمكن إكتشاف الأخطاء فيه ولا يمكن تطبيقه، و عادة ما يكتب بالكلمات الإنجليزية الإعتيادية، ويجب أن يكون السودوكود سهل الفهم و يمكن تحويله إلي أي لغة برمجة بأقل مجهود.

السودوكود The Pseudocode لخوارزمية الإدخال

INSERTION-SORT(A)
For j = 2 to A.Length
key = A[j]
//Insert A[j] into the sorted sequence A[1…j-1]
i = j-1
while i>0 and A[i]>key
A[i+1] = A[i]
i = i-1
A[i+1] = key

شرح خوارزمية الإدخال

السطر 1

A هي المصفوفة المراد ترتيب عناصرها وعدد عناصر أو طول المصفوفة هنا معطى بـ A.Length ، وكل عناصر المصفوفة تعطى بـ [A [j.

السطر 2

حيث 1<= j <= A.length، أي أن [A [1  تعطي العنصر الأول، [A [2  تعطى العنصر الثاني وهكذا إلي آخر عنصر و الذي يعطى بـ [A [n  حيث n=A.Length. و بما أنه يجب إعتبار أول عنصر مرتب مسبقاً فالترتيب سيبدأ من العنصر الثاني، لذلك نضع j=2  لأن [A [2 تعني العنصر الثاني.

السطر 3

 إعتبر أن المفتاح المراد ترتيبه هو العنصر رقم j أي نريد إضافة العنصر رقم j  إلي المصفوفة المرتبة [A[1..j-1 .

السطر 5

نعتبر أن العنصر i يساوي j-1  أي أن [A [i هو العنصر الذي قبل العنصر [A [j ، إذا تحقق الشرط i>0  و A[i]>key تذكير انا نريد ترتيب تصاعدي من الأصغر للأكبر، بما ان ال key في بادئ الامر هو العنصر الثاني و [A [i  هو العنصر الأول، كأنما تقول الحلقة طالما كان العنصر i  أكبر من الصفر و A[i]>key  تخيل ماذا سيحصل؟ إذا أردت ترتيب أوراق اللعب وكنت تحمل أول ورقة لنقل مثلا 5 والورقة الثانية التي حملتها مسبقاً من الأرض كانت 3 من البديهي أنك سوف تقوم بتبديل أماكن الورقتين بحيث تصبح الـ 3 قبل الـ 5 وهذا ما سيحصل أيضا في الخوارزمية.

السطور 8،7،6

من الخطوة رقم 6 إلي الخطوة رقم 8 هي عملية التبديل.

هذا هو كل ما يتعلق بخوارزمية الترتيب بالإدخال وما يعاب عليها أنها تأخذ زمنا طويلا في حالة كثرة المدخلات عليها.

تحليل خوارزمية الترتيب بالإدخال

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

كما ذكرت لك، الحالة الأفضل هي أن تكون المصفوفة مرتبة مسبقاً، و في علم الخوارزميات تُعتبر هذه الحالة خدعه، لأن لها سرعة عالية جداً للخوارزميات البطيئة لحالات قليلة، لذا سنتحدث عن الحالة الأسوأ وهي الأكثر شيوعاً و سأستخدم أحد الرموز المستخدمة بكثرة في علم الخوارزميات و هو رمز الثيتا Θ حيث ((Θ(g(n  تمثل مجموعه من الدوال ونقول أن (Θ(g(n))  = f(n إذا وجد ثابتين c1 و c2 بحيث

(‎c1 g(n‏ أقل من أو يساوي (f(n وفي نفس الوقت (f(n أقل من أو يساوي (c2 g(n.

الحالة الأسوأ لخوارزمية الترتيب بالإدخال

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

(Θ(j)  =T(n∑

حيث حاصل الجمع من 2 إلي n.

هذا هو زمن التشغيل لخوارزمية الترتيب بالإدخال في حالة القيم مرتبة ترتيباً عكسياً (الحالة الأسوأ)، وهذا المجموع يعطينا (جبرياً) الناتج التالي

(Θ(n²) =T(n

ويمكن التعبير عن الناتج الأخير بالآتي

(‎c+bn+an² = T(n‏

و يُعتبر هذا هو زمن التشغيل لخوارزمية الترتيب بالإدخال في الحالة الاسوأ(الأكثر شيوعا).

بهذا نكون قد أكملنا مرورنا بفهم و تحليل خوارزمية الترتيب بالإدخال (Inserting Sorting Algorithm)، و هي من الخوارزميات الأساسية للترتيب، و لها بدائل و أُخيّات. هل ترى أن هذه الخوارزمية بسيطة؟ ولماذا؟ شاركنا رأيك في التعليقات أدناه

امثلة علي خوارزميات أخرى:

خوارزمية البحث الخطي Linear Search Algorithm