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

للتعبير عن الخوارزمية يُستخدم ما يعرف بالسودوكود و هو عبارة عن تعبير للخوارزمية بأي طريقة كانت ولا يعتبر كود حقيقي أي لا يمكن إكتشاف الأخطاء فيه ولا يمكن تطبيقه، و عادة ما يكتب بالكلمات الإنجليزية الإعتيادية، ويجب أن يكون السودوكود سهل الفهم و يمكن تحويله إلي أي لغة برمجة بأقل مجهود.
السودوكود 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)، و هي من الخوارزميات الأساسية للترتيب، و لها بدائل و أُخيّات. هل ترى أن هذه الخوارزمية بسيطة؟ ولماذا؟ شاركنا رأيك في التعليقات أدناه
امثلة علي خوارزميات أخرى:
انت اكثر من رائع
اريد الجوريزم يقوم بوضع اشياء داخل صندوق له حجم بقيمه معينه يتم وضع الاشياء داخل الصندوق ذات القيمه العاليه الثمن بشرط انت تجمع تحت وذن معين وحجم معين
اي ان لكل سلعه ثمن وحجم وي وذنها
أرنا محاولتك الجادّة.
السلام عليكم
ممكن مساعدة بموضوع خوارزمية الثقب الاسود في تحسن تجميع البيانات
اكتب برنامجا باي لغة برمجة يقوم بالتالي
لديك مصفوفة ذات بعدين 20 ..20 يقوم البرنامج بترتيب قطر هذه المصفوفة تصاعديا اي من القيمة الصغرى الى القيمة الكبرى
ملاحظة لا يسمح باستعمال اي مصفوفات اخرى فقط المصفوفة المذكورة اعلاه .
السلام عليكم السؤال اعلاه ,عند ترتيب قطر المصفوفة [i][j] حيث j موشر الصفوف و i مؤشر الاعمدة عند القارنة:[i+1][i+1]<[i][i] كيف تكون صورة المصفوة؟اريد ان امكن خوارزمية ترتيب المصفوفة بعد تعديل القطر اذا شترطنا:[i+1][i+1]<[i][i]
[i][i]=holder(متغير)
[i+1][i+1]=[i][i]
[i+1][i+1]=holder
يعني:كيف يكون شكل المصفوة [i][i] وشكلها:[i+1][i+1]
شكرا لك
مرحباً بك نزار،
يبدو في نهاية الأمر أن هذه المسألة عبارة عن ترتيب لمصفوفة واحدة مع اختلاف طريقة الوصول عبر المؤشرات.
على كُلّ، في مدونة علوم لا نقدم حلولاً لمسائل، ولكن بإمكانك مشاركة ما يقف أمامك لنجد لهُ حلاً سوياً مع القرّاء.
السلام عليكم و رحمة الله و بركاته
شكرا على الشرح دكتور مصطفى الله يجعلها بموازين حسناتك
مشكلتي كانت كيف أحسب تعقيد الخوارزمية بالنسبة للوقت و المساحة
time and space complexity
و هي التي قادتني الى مدونتك المفيدة فهل تستطيع مساعدتي خاصة في حساب الـ (space complixty)
وشكرا .
و عليكم السلام ورحمة الله و بركاته الغامدي،
مرحباً بك و يُسعدني وجودك في مدونة علوم، هذه من المشاكل المتكررة لمن يرغب بتعلم الخورازميات فعلاً، و قد تم وضعها في قائمة التدوينات القادمة، و لكن ليس قريباً إن كُنت على عجل.
يعطيك الف عافية لكن لو كان باستطاع حضرتك كتب المصادر اللي منها معلوماتك
مرحباً روان،
هذه التدوينة مشاركة من قبل الأخ سامي، على كل أعتقد أن كتاب Introduction to Algorithms كتاب رائع لتعلم مبادئ الخوارزميات.
السلام عليكم اخي ممكن شرح لخوارزمية الاضافه واكوون ممنونه
و عليكم السلام و رحمة الله و بركاته حوراء،
خوارزمية الترتيب بالإضافة هي نفسها خوارزمية الترتيب بالإدخال، ستجدين التفاصيل بالأعلى فقط استبدلي الإدخال بالإضافة.
السلام عليكم ورحمة الله وبركاته
جزيت خيرا الشرح وافي ومتكامل خصوصا مع الاكواد اللبرمجية لعدة لغات …علي بحث عن خوارزميات ترتيب للمصفوفات وجدت عدة شروحات لكن بدون الاكواد البرمجيه .فهلك ان تغطي بقية الخوارزميات كا الفقاعيه والاختيار والترتيب السريع …الخ .ولك جزيل الشكر .
و عليكم السلام و رحمة الله و بركاته،
جُزيتي الجنة، بإذن الله ستُغطى أغلب خوارزميات الترتيب، و أتمنى لك التوفيق
جزاك الله خيرا شرح وافي وجميل ..
لدي طلب : من الممكن شرح ال
Loop Invariant ؟
وموضوع آخر اقترح طرحه لأني لم أجد شرحاً وافياً له أبداً وهو موضوع الRunning Time أو الTime Compliexity .
ولكم جزيل الشكر والإمتنان
مرحباً أخي زين، حُيّيت و جُزيت خيراً.
بإذن الله سأغطيها من ضمن تدويناتي. رُبّما يكون شرح “زمن التشغيل” و “تعقيد الزمن” أقرب في الشرح.
و لك مني كُلَّ التقدير.