الأرقام المقروءة
النقلات
الجولة

  • الدلو المستخدم
  • نُقل للتو
  • أُعيد نسخه
  • في مكانه

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

ترتيب الجذر

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

كيف يعمل

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

كيف يعمل ترتيب الجذر

انظر فقط إلى آخر رقم في كل عدد ورتب القائمة حسبه: ضع كل عدد في أحد عشرة دلاء، من 0 إلى 9، محافظًا على الترتيب الذي جاءت به الأعداد، ثم انسخ الدلاء عائدةً واحدًا تلو الآخر. افعل الشيء نفسه مع رقم العشرات، ثم المئات. ولأن كل جولة تحافظ على ترتيب الأعداد التي تشترك في رقم، تظل الجولات السابقة هي التي تحدد الترتيب بينها، وبعد الجولة الأخيرة تصبح القائمة كلها مرتبة.

بلا مقارنات إطلاقًا

تحتاج خوارزميات الترتيب بالمقارنة إلى نحو n log₂ n مقارنة على الأقل في أسوأ حالة، مهما استخدمت من حيل ذكية. أما ترتيب الجذر فيتجاوز هذا الحد بقراءة الخانات بدلًا من ذلك: كل جولة تقرأ خانة واحدة من كل قيمة وتنقل كل قيمة مرتين، لذا تحتاج d خانة إلى d جولة ويزداد العمل مع n · d. ويؤتي هذا ثماره مع القوائم الطويلة ذات المفاتيح القصيرة: مليون عدد حتى 999 يحتاج إلى ثلاث جولات، بينما يحتاج الترتيب بالمقارنة إلى نحو 20 مليون مقارنة. والثمن أنه لا يصلح إلا للمفاتيح المكونة من أرقام أو حروف، ويحتاج إلى مساحة للدلاء.

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

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

يرتب الأعداد حسب آخر رقم فيها، ثم حسب الرقم الذي قبله، وهكذا حتى الرقم الأول. كل جولة تضع الأعداد في عشرة دلاء حسب ذلك الرقم، مع الحفاظ على ترتيبها، ثم تنسخ الدلاء عائدةً. وبعد جولة الخانة الأعلى قيمةً تصبح القائمة مرتبة.

لماذا نبدأ بآخر رقم؟

لأن كل جولة مستقرة: الأعداد التي تحمل الرقم نفسه تحتفظ بالترتيب الذي منحتها إياه الجولات السابقة. لذا فالجولة الأخيرة، على الرقم الأول، هي التي تحدد الترتيب، وتحسم الخانات المرتبة مسبقًا حالات التساوي. ويسمى هذا ترتيب الجذر LSD (الخانة الأدنى قيمةً).

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

قد يكون كذلك مع مفاتيح قصيرة كثيرة: يزداد عمله مع عدد القيم مضروبًا في عدد الخانات، دون n log n. أما مع قيم قليلة، أو مفاتيح طويلة جدًا، أو بيانات لا تتكون من أرقام، فعادةً ما يكون الترتيب السريع والترتيب بالدمج أسرع وأبسط.

ما علاقته بترتيب العد؟

كل جولة من ترتيب الجذر هي ترتيب عد على خانة واحدة: عُدّ كم قيمة تحمل كل رقم، واحسب أين يبدأ كل دلو، ثم انقل القيم إليه بالترتيب.

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

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

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

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

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