المقارنات
التبديلات
الجولة

  • قيد الإدراج
  • قيد المقارنة
  • تم تبديله
  • الجزء المرتب

مزيد عن الترتيب بالإدراج

الترتيب بالإدراج

يعمل الترتيب بالإدراج بالطريقة التي يرتب بها كثيرون أوراق اللعب في أيديهم. فهو يحتفظ بجزء مرتب في بداية القائمة، ويأخذ القيمة التالية ويعيدها متجاوزًا كل قيمة أكبر منها حتى تستقر في مكانها. شغّل الترتيب بأي سرعة، أو تقدّم مقارنةً واحدة في كل مرة، وراقب عدادات المقارنات والتبديلات والجولات. اضغط تشغيل لمشاهدة الترتيب، أو خطوة ورجوع للتقدم مقارنةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع. تعرض المربعات عدد المقارنات والتبديلات والجولات. اختر عدد الأعمدة وترتيبها الأولي، أو اكتب أرقامك. عند تحديد اللوحة، تتقدم مفاتيح الأسهم وترجع خطوةً خطوة، ويشغّل مفتاح المسافة الترتيب ويوقفه مؤقتًا، وينقلك مفتاحا Home وEnd إلى البداية والنهاية.

كيف يعمل

  1. اختر عدد الأعمدة وترتيبها الأولي: عشوائي، أو شبه مرتب، أو معكوس، أو بقيم مختلفة قليلة. أو اكتب أرقامك.
  2. اضغط تشغيل، أو استخدم خطوة ورجوع للتقدم مقارنةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع في الترتيب.
  3. جرّب قائمة شبه مرتبة وأخرى معكوسة، وقارن عدد المقارنات في كل منهما.

كيف يعمل الترتيب بالإدراج

القيمة الأولى وحدها جزء مرتب. خذ القيمة الثانية وقارنها بالقيمة التي تسبقها؛ فإن كانت تلك أكبر فبدّلهما، واستمر في المقارنة والتبديل حتى لا تكون القيمة السابقة أكبر أو تصل القيمة إلى بداية القائمة. الآن صارت أول قيمتين مرتبتين. كرر ذلك مع القيمة الثالثة والرابعة وهكذا حتى نهاية القائمة.

سريع مع القوائم شبه المرتبة

تتوقف كل جولة عند أول قيمة ليست أكبر، لذا لا تكلّف القيمة القريبة أصلًا من مكانها سوى مقارنة أو اثنتين. تحتاج القائمة المرتبة إلى n − 1 مقارنة دون أي تبديل؛ أما القائمة المعكوسة، وهي أسوأ حالة، فتحتاج إلى n(n − 1)/2 من كل منهما. ويساوي عدد التبديلات دائمًا عدد الانقلابات في القائمة الأولية، أي الأزواج التي في غير ترتيبها. لهذا يُستخدم الترتيب بالإدراج كثيرًا مع القوائم القصيرة أو شبه المرتبة، وداخل خوارزميات أسرع لإنهاء الأجزاء الصغيرة.

الأسئلة المتداولة

كيف يعمل الترتيب بالإدراج؟

يبني جزءًا مرتبًا في بداية القائمة. تأخذ كل جولة القيمة التالية وتعيدها متجاوزةً كل قيمة أكبر تسبقها حتى تستقر في مكانها. بعد الجولة k تكون أول k + 1 قيم مرتبة، لكن قد تُدرج بينها قيمة لاحقة.

كم مقارنة وتبديلًا يجري الترتيب بالإدراج؟

يساوي عدد التبديلات دائمًا عدد الانقلابات في القائمة الأولية: صفر للقائمة المرتبة، وn(n − 1)/2 للمعكوسة. وعدد المقارنات هو عدد التبديلات مضافًا إليه مقارنة واحدة على الأكثر في كل جولة، أي بين n − 1 وn(n − 1)/2.

لماذا الترتيب بالإدراج سريع مع القوائم شبه المرتبة؟

لأن الجولة تتوقف فور أن تصادف قيمة ليست أكبر. فإذا كانت كل قيمة قريبة من مكانها النهائي، كانت كل جولة قصيرة، واستغرق الترتيب كله وقتًا قريبًا من n.

هل الترتيب بالإدراج مستقر؟

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

هل تُرسل أرقامي إلى أي مكان؟

لا. يجري الترتيب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر