الرئيسية / الخوارزميات / خوارزمية الترتيب بالإدخال: شرح رائع و تحليل الخوارزمية

خوارزمية الترتيب بالإدخال: شرح رائع و تحليل الخوارزمية

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

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

كةتش

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

السودوكود 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)، و هي من الخوارزميات الأساسية للترتيب، و لها بدائل و أُخيّات قد تطلع عليهم بمتابعتك لمدونة علوم.

عن سامي محمد آدم

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

10 تعليقات

  1. جزاك الله خيرا شرح وافي وجميل ..
    لدي طلب : من الممكن شرح ال
    Loop Invariant ؟

    وموضوع آخر اقترح طرحه لأني لم أجد شرحاً وافياً له أبداً وهو موضوع الRunning Time أو الTime Compliexity .

    ولكم جزيل الشكر والإمتنان

    • مرحباً أخي زين، حُيّيت و جُزيت خيراً.
      بإذن الله سأغطيها من ضمن تدويناتي. رُبّما يكون شرح “زمن التشغيل” و “تعقيد الزمن” أقرب في الشرح.

      و لك مني كُلَّ التقدير.

  2. السلام عليكم ورحمة الله وبركاته
    جزيت خيرا الشرح وافي ومتكامل خصوصا مع الاكواد اللبرمجية لعدة لغات …علي بحث عن خوارزميات ترتيب للمصفوفات وجدت عدة شروحات لكن بدون الاكواد البرمجيه .فهلك ان تغطي بقية الخوارزميات كا الفقاعيه والاختيار والترتيب السريع …الخ .ولك جزيل الشكر .

  3. السلام عليكم اخي ممكن شرح لخوارزمية الاضافه واكوون ممنونه

    • و عليكم السلام و رحمة الله و بركاته حوراء،

      خوارزمية الترتيب بالإضافة هي نفسها خوارزمية الترتيب بالإدخال، ستجدين التفاصيل بالأعلى فقط استبدلي الإدخال بالإضافة.

  4. يعطيك الف عافية لكن لو كان باستطاع حضرتك كتب المصادر اللي منها معلوماتك

  5. السلام عليكم و رحمة الله و بركاته

    شكرا على الشرح دكتور مصطفى الله يجعلها بموازين حسناتك

    مشكلتي كانت كيف أحسب تعقيد الخوارزمية بالنسبة للوقت و المساحة
    time and space complexity
    و هي التي قادتني الى مدونتك المفيدة فهل تستطيع مساعدتي خاصة في حساب الـ (space complixty)

    وشكرا .

    • و عليكم السلام ورحمة الله و بركاته الغامدي،

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

أضف تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *