الترتيب بالإدراج
الترتيب بالإدراج هو الطريقة التي يرتب بها معظم الناس أوراق اللعب في أيديهم: التقط الورقة التالية وأدخلها في مكانها الصحيح بين الأوراق المرتبة. وهو بطيء مع القوائم العشوائية الطويلة، لكنه سريع جدًا مع القوائم القصيرة أو شبه المرتبة، ولهذا ما زالت مكتبات الترتيب الحقيقية تستخدمه.
الفكرة
أبقِ بداية القائمة مرتبة. في البداية يكون الجزء المرتب هو القيمة الأولى وحدها. خذ القيمة التالية وقارنها بالقيمة التي تسبقها. فإن كانت تلك أكبر، فبدّلهما وقارن من جديد، متراجعًا مكانًا واحدًا. توقف عندما لا تكون القيمة السابقة أكبر، أو عندما تصل القيمة إلى بداية القائمة. لقد زاد الجزء المرتب قيمة واحدة. كرر ذلك مع كل قيمة حتى النهاية.
مثال
خذ 5, 1, 4, 2, 8. الجولة 1 تأخذ 1: القيمة 5 أكبر، فيتبادلان، وتصل 1 إلى البداية: 1, 5, 4, 2, 8. الجولة 2 تأخذ 4: تتبادل مع 5، ثم تتوقف عند 1: 1, 4, 5, 2, 8. الجولة 3 تأخذ 2: تتبادل مع 5 ثم مع 4، ثم تتوقف عند 1: 1, 2, 4, 5, 8. الجولة 4 تأخذ 8، وهي أكبر من 5 أصلًا، فتكفي مقارنة واحدة. المجموع 7 مقارنات و4 تبديلات. أما الترتيب الفقاعي فيحتاج إلى 9 مقارنات على القائمة نفسها، والترتيب بالاختيار إلى 10.
التبديلات تساوي الانقلابات
الانقلاب زوج من القيم في ترتيب خاطئ. وتبديل جارين في غير ترتيبهما يزيل انقلابًا واحدًا بالضبط، والترتيب بالإدراج لا يبدّل إلا مثل هذين الجارين. لذا يجري من التبديلات بقدر ما في القائمة الأولية من انقلابات تمامًا، وهو العدد نفسه في الترتيب الفقاعي. وتجري كل جولة أيضًا مقارنة واحدة على الأكثر لا تؤدي إلى تبديل، وهي التي توقفها. لذا فعدد المقارنات هو عدد الانقلابات مضافًا إليه n − 1 على الأكثر.
تكيفي: سريع حين تكون القائمة شبه مرتبة
لأن مقدار العمل هو عدد الانقلابات مضافًا إليه نحو n، يكون الترتيب بالإدراج سريعًا كلما قلّت الانقلابات. تحتاج القائمة المرتبة إلى n − 1 مقارنة دون أي تبديل. والقائمة التي تبعد كل قيمة فيها أماكن قليلة فقط عن موضعها تستغرق وقتًا قريبًا من n. ولا يستغرق وقتًا يتناسب مع n² إلا قائمة بعيدة عن الترتيب، مثل القائمة المعكوسة ذات n(n − 1)/2 انقلاب. وفي القائمة العشوائية يبلغ المتوسط نحو n²/4 تبديل.
أين يُستخدم
الترتيب بالإدراج مستقر، ولا يحتاج إلى ذاكرة إضافية، وعبؤه الإضافي ضئيل جدًا. ومع القوائم القصيرة يتفوق على خوارزميات أسرع منه نظريًا. وكثير من دوال الترتيب في المكتبات، مثل Timsort في Python وJava وintrosort المستخدم في C++، تنتقل إلى الترتيب بالإدراج مع الأجزاء الصغيرة من القائمة، عادةً حتى بضع عشرات من القيم. ويناسب أيضًا البيانات التي تصل قيمةً قيمة، لأن كل قيمة جديدة يمكن إدراجها فور وصولها.
جرّبه بنفسك
افتح التطبيق واضغط تشغيل، أو اضغط خطوة للتقدم مقارنةً واحدة في كل مرة. للقيمة قيد الإدراج لونها الخاص، وتُبرز القيمة التي تُقارن بها، والجزء المرتب أخضر. وعلى عكس الترتيب الفقاعي والترتيب بالاختيار، ليس الجزء الأخضر نهائيًا: فقد تنزلق إليه لاحقًا قيمة أصغر. جرّب قائمة شبه مرتبة لترى كم هي قصيرة الجولات، ثم قائمة معكوسة.
الأسئلة المتداولة
ما التعقيد الزمني للترتيب بالإدراج؟
O(n²) في أسوأ حالة وفي المتوسط، وO(n) في أفضل حالة، أي حين تكون القائمة مرتبة مسبقًا. وبدقة أكبر، يستغرق وقتًا يتناسب مع n مضافًا إليه عدد الانقلابات. ولا يحتاج إلا إلى ذاكرة إضافية O(1).
ما الفرق بين الترتيب بالإدراج والترتيب بالاختيار؟
يمسح الترتيب بالاختيار الجزء غير المرتب كله ليجد أصغر قيمة، لذا يجري دائمًا n(n − 1)/2 مقارنة لكن تبديلات قليلة. أما الترتيب بالإدراج فيأخذ القيمة التالية كما تأتي ويعيدها بالقدر اللازم فقط، لذا يجري مقارنات أقل، خاصةً مع القوائم شبه المرتبة، لكن تبديلات أكثر.
ما الترتيب بالإدراج الثنائي؟
صيغة تجد موضع القيمة الجديدة بالبحث الثنائي في الجزء المرتب، فتحتاج إلى نحو log n مقارنة بدلًا من n على الأكثر. لكن القيم ما زالت تحتاج إلى الإزاحة لإفساح المكان، لذا يبقى عدد النقلات وأسوأ حالة O(n²) كما هما.
هل الترتيب بالإدراج مستقر؟
نعم. لا تتراجع القيمة إلا متجاوزةً القيم الأكبر منها تمامًا، لذا تحافظ القيم المتساوية على ترتيبها الأصلي.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب الترتيب بالإدراج