- الجزء قيد التقسيم
- المحور
- قيد المقارنة
- تم تبديله
- في مكانه
الترتيب السريع
يختار الترتيب السريع محورًا، وينقل كل قيمة أصغر منه إلى ما قبله وكل قيمة أخرى إلى ما بعده، ثم يرتب الجانبين بالطريقة نفسها. بعد كل تقسيم يستقر المحور في مكانه النهائي. اختر طريقة اختيار المحور، وشغّل الترتيب بأي سرعة أو تقدّم فيه مقارنةً واحدة في كل مرة، وشاهد لماذا يجعل المحور السيئ على قائمة مرتبة الترتيبَ السريع بطيئًا. اضغط تشغيل لمشاهدة الترتيب، أو خطوة ورجوع للتقدم مقارنةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع. تعرض المربعات عدد المقارنات والتبديلات والتقسيمات. اختر عدد الأعمدة وترتيبها الأولي، أو اكتب أرقامك، واختر طريقة اختيار المحور. عند تحديد اللوحة، تتقدم مفاتيح الأسهم وترجع خطوةً خطوة، ويشغّل مفتاح المسافة الترتيب ويوقفه مؤقتًا، وينقلك مفتاحا Home وEnd إلى البداية والنهاية.
كيف يعمل
- اختر عدد الأعمدة وترتيبها الأولي: عشوائي، أو شبه مرتب، أو معكوس، أو بقيم مختلفة قليلة. أو اكتب أرقامك.
- اضغط تشغيل، أو استخدم خطوة ورجوع للتقدم مقارنةً واحدة في كل مرة. اسحب شريط الخطوات للانتقال إلى أي موضع في الترتيب.
- اختر قاعدة المحور: القيمة الأخيرة، أو القيمة الوسطى، أو قيمة عشوائية، أو وسيط الثلاثة. جرّب كلًّا منها على قائمة مرتبة.
كيف يعمل الترتيب السريع
اختر قيمة من الجزء المراد ترتيبه لتكون المحور، وانقلها إلى النهاية. مرّ على القيم الأخرى من البداية إلى النهاية؛ كل قيمة أصغر من المحور تُبدَّل إلى جزء أول يكبر من البداية. ثم بدّل المحور إلى الموضع الذي يلي الجزء الأول مباشرةً. صار كل ما قبله أصغر منه، ولا شيء بعده أصغر منه، لذا أصبح المحور في مكانه النهائي. رتّب الجزء الذي قبله والجزء الذي بعده بالطريقة نفسها، حتى يصبح كل جزء قيمة واحدة.
لماذا يهم المحور
عندما يقع المحور قرب المنتصف، يقسم كل تقسيم المسألة إلى نصفين، ويزداد عدد المقارنات بمعدل n log n: نحو 190 لـ40 قيمة عشوائية. وعندما يكون المحور أصغر قيمة أو أكبرها، يكون أحد الجانبين فارغًا والآخر فيه كل ما تبقى. عند اختيار القيمة الأخيرة محورًا يحدث ذلك في كل خطوة على قائمة مرتبة أو معكوسة، ويحتاج الترتيب إلى n(n − 1)/2 مقارنة، أي 780 لـ40 قيمة. والمحور العشوائي أو وسيط القيم الأولى والوسطى والأخيرة يتجنبان ذلك عمليًا.
الأسئلة المتداولة
كيف يعمل الترتيب السريع؟
يختار محورًا، ويقسم القائمة بحيث تأتي القيم الأصغر قبل المحور والباقي بعده، ثم يرتب الجانبين بالترتيب السريع. بعد كل تقسيم يكون المحور في مكانه النهائي.
لماذا يكون الترتيب السريع بطيئًا على قائمة مرتبة؟
عند اختيار القيمة الأولى أو الأخيرة محورًا، يكون المحور في القائمة المرتبة دائمًا أصغر قيمة أو أكبرها. فيكون أحد جانبي التقسيم فارغًا، ولا يُزيل كل تقسيم سوى قيمة واحدة، ويحتاج الترتيب إلى n(n − 1)/2 مقارنة. والمحور العشوائي أو وسيط الثلاثة يحلان ذلك عمليًا.
هل الترتيب السريع أسرع من الترتيب بالدمج؟
غالبًا، من الناحية العملية: فهو يرتب في المكان، ولا يحتاج إلى ذاكرة مؤقتة، وحلقته الداخلية بسيطة جدًا. في المتوسط يجري مقارنات أكثر قليلًا من الترتيب بالدمج، وأسوأ حالاته n²، بينما الترتيب بالدمج دائمًا n log n. وتبدأ خوارزميات الترتيب في المكتبات، مثل introsort، بالترتيب السريع ثم تنتقل إلى الترتيب بالكومة إذا صار التقسيم غير متوازن أكثر من اللازم.
هل الترتيب السريع مستقر؟
لا. التقسيم يبدّل القيم عبر مسافات طويلة، لذا قد يتغير ترتيب القيم المتساوية.
هل تُرسَل أرقامي إلى أي مكان؟
لا. يجري الترتيب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر