ترتيب الجذر
ترتيب الجذر هو الاستثناء بين خوارزميات الترتيب: فهو لا يسأل أبدًا أي القيمتين أكبر، بل يقرأ الأعداد خانةً خانة ويرتبها حسب خانة واحدة في كل مرة، مستخدمًا عشرة دلاء. والفكرة أقدم من الحواسيب: فهكذا كانت تعمل آلات فرز البطاقات المثقبة.
الفكرة
رتب الأعداد حسب رقم الآحاد وحده. ثم رتبها حسب رقم العشرات، لكن بطريقة تُبقي الأعداد التي لها رقم العشرات نفسه بالترتيب الذي منحته إياها الجولة الأولى. ثم حسب المئات، بالطريقة نفسها. بعد الجولة الأخيرة تصبح القائمة مرتبة: المئات تحسم أولًا، والمتساوية في المئات مرتبة مسبقًا حسب عشراتها، والمتساوية هناك أيضًا مرتبة حسب آحادها.
جولة واحدة بالدلاء
تستخدم كل جولة عشرة دلاء، دلوًا لكل رقم من 0 إلى 9. مُرّ على القائمة من البداية إلى النهاية وانقل كل عدد إلى دلو رقمه، خلف الأعداد الموجودة فيه. ثم أفرغ الدلاء عائدةً إلى القائمة بالترتيب، بدءًا بالدلو 0. نقلُ الأعداد بترتيب القائمة وإضافتها إلى مؤخرة الدلو هو ما يجعل الجولة مستقرة. يعدّ التطبيق الأعداد لكل رقم أولًا، كي تصطف الدلاء جنبًا إلى جنب في صف واحد، يبدأ كلٌّ منها مباشرةً بعد الذي قبله: وهذا هو ترتيب العد على خانة واحدة.
مثال
خذ 170, 45, 75, 90, 802, 24, 2, 66. حسب رقم الآحاد: 170, 90, 802, 2, 24, 45, 75, 66. حسب رقم العشرات: 802, 2, 24, 45, 66, 170, 75, 90؛ لاحظ أن 802 و2، وكلاهما رقم عشراته 0، يحتفظان بترتيبهما من الجولة الأولى. حسب رقم المئات: 2, 24, 45, 66, 75, 90, 170, 802. ثلاث جولات على ثمانية أعداد: 24 رقمًا مقروءًا و48 نقلة، ولا مقارنة واحدة.
ما مدى سرعته؟
تقرأ كل جولة رقمًا واحدًا من كل عدد وتنقل كل عدد مرتين، لذا يزداد العمل مع n · d لعدد n من الأعداد ذات d خانة. يحتاج الترتيب بالمقارنة إلى نحو n log₂ n مقارنة على الأقل في أسوأ حالة، لأن عليه أن يميّز بين n! ترتيبًا ممكنًا بسؤال واحد إجابته نعم أو لا في كل مرة. ولا يتقيد ترتيب الجذر بذلك، لأنه لا يطرح مثل هذه الأسئلة أبدًا. ومع مفاتيح قصيرة كثيرة، مثل مليون عدد أصغر من 1,000، تكون ثلاث جولات أقل عملًا بكثير من نحو 20 مليون مقارنة يحتاجها الترتيب بالمقارنة. ومع المفاتيح الطويلة أو القيم القليلة تختفي هذه الميزة.
LSD وMSD، والتاريخ
النسخة المعروضة هنا تبدأ بالخانة الأدنى قيمةً (LSD). أما الطريقة المعاكسة، أي الخانة الأعلى قيمةً أولًا (MSD)، فتقسم القائمة إلى دلاء حسب الرقم الأول وترتب كل دلو على حدة، وهذا يناسب السلاسل النصية المختلفة الأطوال. يعود ترتيب الجذر إلى آلات فرز البطاقات المثقبة التي تلت آلات الجدولة التي صنعها Herman Hollerith لتعداد الولايات المتحدة عام 1890: كانت آلة الفرز تُسقط كل بطاقة في أحد عشرة جيوب حسب الثقب في عمود واحد، وكان المشغّلون يمررون رزمة البطاقات مرة لكل عمود، بدءًا بالعمود الأخير.
استكشفه
افتح التطبيق واضغط خطوة. كل جولة تعدّ الأرقام أولًا، فتحدد الدلاء من 0 إلى 9 في الصف أسفل القائمة. ثم تسقط الأعداد في دلائها واحدًا تلو الآخر، مع إبراز الدلو النشط، ثم تُنسخ عائدةً. اكتب أعدادك حتى 999، مثل المثال أعلاه، لترى الجولات الثلاث كلها.
الأسئلة المتداولة
ما التعقيد الزمني لترتيب الجذر؟
O(n · d) لعدد n من المفاتيح ذات d خانة في أساس ثابت، إضافةً إلى كلفة الدلاء في كل جولة. ويحتاج إلى ذاكرة إضافية O(n) للمخزن المؤقت الذي توجد فيه الدلاء.
هل ترتيب الجذر مستقر؟
يجب أن يكون ترتيب الجذر LSD مستقرًا: فهو لا يعمل إلا لأن كل جولة تُبقي القيم التي تحمل الرقم نفسه بالترتيب الذي دخلت به. لذا تكون النتيجة النهائية مستقرة أيضًا.
هل يتعامل ترتيب الجذر مع الأعداد السالبة أو العشرية؟
ليس مباشرةً، لكنه يستطيع ذلك بحيلة: أزح الأعداد السالبة لتصبح كلها موجبة، أو رتبها على حدة ثم اعكسها. ويمكن ترتيب أعداد الفاصلة العائمة حسب أنماط بتاتها بعد تحويل بسيط.
لماذا الأساس 10؟
لأنه سهل المتابعة. تُرتب الحواسيب عادةً 8 أو 16 بتًا في كل مرة، لذا يحتاج العدد ذو 32 بتًا إلى أربع جولات أو جولتين، مع 256 أو 65,536 دلوًا.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب ترتيب الجذر