سموث سورت

في علم الحاسوب ، تُعدّ خوارزمية الترتيب السلس (smoothsort) خوارزمية ترتيب تعتمد على المقارنة . وهي نوع مُعدّل من خوارزمية الترتيب الهرمي ( heapsort ) ، وقد ابتكرها ونشرها إدسكار ديكسترا عام 1981. ^{[ 1 ]} ومثل خوارزمية الترتيب الهرمي، تُعتبر خوارزمية الترتيب السلس خوارزمية ترتيب موضعي بحد أقصى O ( n log n ) عملية (انظر ترميز Big O ). ^{[ 2 ]} ومثل خوارزمية الترتيب الهرمي، لا تُعتبر خوارزمية الترتيب السلس خوارزمية ترتيب مستقرة . وتكمن ميزة خوارزمية الترتيب السلس في أنها تقترب من زمن O ( n ) إذا كانت المدخلات مُرتبة بالفعل إلى حد ما ، بينما يبلغ متوسط ​​زمن خوارزمية الترتيب الهرمي O ( n log n ) بغض النظر عن حالة الترتيب الأولية.  

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

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

تستخدم خوارزمية Smoothsort طريقةً مختلفةً لترتيب البيانات، وهي اجتيازٌ تصاعديٌّ عميقٌ بترتيبٍ لاحق . يتبع الابن الأيسر الشجرة الفرعية التي جذرها شقيقه، ويتبع الابن الأيمن والده. لكل عنصر ارتفاعٌ محددٌ فوق الأوراق، ولكل عنصرٍ غير ورقيٍّ أبناؤه في مواقعَ سابقةٍ في المصفوفة. مع ذلك، يعتمد عمقه أسفل الجذر على حجم المصفوفة. صُممت الخوارزمية بحيث يكون الجذر في نهاية الكومة، وعند استخراج أي عنصرٍ منها يكون قد استقرّ في موقعه النهائي ولا يحتاج إلى نقله. كذلك، تُعدّ المصفوفة المرتبة كومةً صالحةً، والعديد من الفترات المرتبة هي أشجارٌ فرعيةٌ مرتبةٌ وفقًا لترتيب الكومة.

بصورة أدق، كل موضع i هو جذر لشجرة فرعية فريدة، تشغل عقدها فاصلاً متصلاً ينتهي عند i . قد تكون البادئة الأولية للمصفوفة (بما في ذلك المصفوفة بأكملها) فاصلاً كهذا يُقابل شجرة فرعية، ولكنها عمومًا تتحلل إلى اتحاد عدد من فواصل الأشجار الفرعية المتتالية هذه، والتي يُطلق عليها ديكسترا اسم "الامتدادات". أي شجرة فرعية بدون أصل (أي جذرها عند موضع يقع أصله خارج البادئة قيد الدراسة) تُعطي امتدادًا في تحلل ذلك الفاصل، وبالتالي يكون هذا التحلل فريدًا. عند إضافة عقدة جديدة إلى البادئة، يحدث أحد أمرين: إما أن يكون الموضع ورقة ويُضيف امتدادًا بطول 1 إلى التحلل، أو أنه يندمج مع آخر امتدادين، ليصبح أصل جذورهما، وبالتالي يستبدل الامتدادين بامتداد جديد يحتوي على اتحادهما بالإضافة إلى الموضع الجديد (الجذر).

أشار ديكسترا ^{[ 1 ]} إلى أن القاعدة البديهية هي دمج الأجزاء إذا وفقط إذا كانت متساوية في الحجم، وفي هذه الحالة ستكون جميع الأشجار الفرعية أشجارًا ثنائية مثالية بحجم 2k ^- 1 . ومع ذلك، فقد اختار قاعدة مختلفة، تُتيح أحجامًا أكثر احتمالًا للأشجار. تتمتع هذه القاعدة بنفس الكفاءة التقاربية ^{[ 2 ]،} ولكنها تُحسّن الكفاءة بمعامل ثابت صغير من خلال تقليل عدد الأجزاء المطلوبة لتغطية كل فترة.

تعتمد قاعدة ديكسترا على دمج آخر جزأين إذا وفقط إذا كانت أحجامهما أعداد ليوناردو المتتالية L ( i +1 ) و L ( i ) (بهذا الترتيب)، والتي يتم تعريفها بشكل متكرر، بطريقة مشابهة جدًا لأعداد فيبوناتشي ، على النحو التالي:

• L (0) = L (1) = 1
• L ( k +2) = L ( k +1) + L ( k ) + 1

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

إضافةً إلى كون كل امتداد شجرة مرتبة ترتيبًا هرميًا، تُحفظ جذور الأشجار مرتبةً ترتيبًا تصاعديًا. وهذا يُضيف فعليًا فرعًا ثالثًا (يُطلق عليه ديكسترا اسم "الابن بالتبني") إلى كل جذر، رابطًا إياه بالجذر السابق. وبذلك، تُدمج جميع الأشجار معًا في كومة عالمية واحدة، مع وجود القيمة القصوى العالمية في النهاية.

على الرغم من أن موقع الابن المتبنى لكل عقدة ثابت، إلا أن الرابط موجود فقط لجذور الشجرة، مما يعني أن الروابط تُزال عند دمج الأشجار. وهذا يختلف عن الأبناء العاديين، الذين يرتبطون طالما أن الأصل موجود.

في المرحلة الأولى (مرحلة نمو الكومة) من عملية الفرز، يُعاد تنظيم جزء أولي متزايد الحجم من المصفوفة بحيث تكون الشجرة الفرعية لكل امتداد منها كومة قصوى: أي أن العنصر في أي موضع غير طرفي يكون على الأقل بنفس حجم العناصر في المواضع التي تمثل أبناءه. بالإضافة إلى ذلك، فإن جميع الجذور تكون على الأقل بنفس حجم أبنائها.

في المرحلة الثانية (مرحلة تقليص الكومة)، يتم فصل العقدة القصوى عن نهاية المصفوفة (دون الحاجة إلى تحريكها) ويتم إعادة تأسيس ثوابت الكومة بين أبنائها. (وتحديدًا، بين الأبناء المتبنين الذين تم إنشاؤهم حديثًا).

يتطلب التطبيق العملي في كثير من الأحيان حساب أعداد ليوناردو L ( k ) . يوفر خوارزمية ديكسترا شيفرة ذكية تستخدم عددًا ثابتًا من المتغيرات الصحيحة لحساب القيم المطلوبة بكفاءة عند الحاجة إليها. بدلاً من ذلك، إذا كان هناك حد أقصى N لحجم المصفوفات المراد فرزها، فيمكن تخزين جدول مُعد مسبقًا لأعداد ليوناردو في مساحة O (log N ) . 

على الرغم من أن المرحلتين من عملية الفرز متعاكستان فيما يتعلق بتطور بنية تسلسل الأكوام، إلا أنهما يتم تنفيذهما باستخدام عنصر أساسي واحد، وهو ما يعادل عملية "الفرز لأسفل" في كومة ثنائية قصوى.

تستغرق خوارزمية Smoothsort زمنًا قدره O ( n ) لمعالجة مصفوفة مُرتبة مسبقًا، و O ( n log n )  في أسوأ الحالات، وتحقق أداءً خطيًا تقريبًا على العديد من المدخلات شبه المرتبة. مع ذلك، فهي لا تتعامل مع جميع التسلسلات شبه المرتبة على النحو الأمثل. باستخدام عدد الانعكاسات كمقياس لعدم الترتيب (عدد أزواج المؤشرات i و j حيث i < j و A [ i ] > A [ j ] ؛ بالنسبة للمدخلات المرتبة عشوائيًا، يكون هذا العدد تقريبًا n² /4 ⁾ ، توجد تسلسلات إدخال محتملة تحتوي على O ( n log n )  انعكاسًا، مما يجعلها تستغرق زمنًا قدره Ω( n log n )  ، بينما تستطيع خوارزميات الفرز التكيفية الأخرى حل هذه الحالات في زمن قدره O ( n log  log n )  . ^{[ 2 ]}

يحتاج خوارزمية الفرز السلس إلى تخزين أحجام جميع الأشجار في كومة ليوناردو في الذاكرة. ولأنها مُرتبة حسب الرتبة، وكل رتبة مميزة، يُستخدم عادةً متجه بتات يُشير إلى الرتب الموجودة. علاوة على ذلك، ولأن أكبر رتبة لا تتجاوز O (log n )  ، يمكن ترميز هذه البتات في O (1) كلمة من كلمات الآلة، بافتراض نموذج آلة ثنائي التفرع .

لاحظ أن O (1) كلمة آلة لا تعني كلمة آلة واحدة . يكفي متجه 32 بت للأحجام الأقل من L (32) = 7049155. بينما يكفي متجه 64 بت للأحجام الأقل من L (64) = 34335360355129 ≈ 2⁴⁵ ^. عمومًا، يتطلب الأمر 1/log² ₍ φ ) ≈ 1.44 بت من المتجه لكل بت من الحجم.

هناك خوارزمية أبسط مستوحاة من خوارزمية smoothsort وهي خوارزمية poplar sort . ^{[ 3 ]} سميت هذه الخوارزمية نسبة إلى صفوف الأشجار ذات الحجم المتناقص التي غالباً ما تُرى في الأراضي الهولندية المستصلحة ، وهي تُجري مقارنات أقل من خوارزمية smoothsort للمدخلات غير المرتبة في الغالب، ولكنها لا تستطيع تحقيق وقت خطي للمدخلات المرتبة.

يتمثل التغيير الجوهري الذي أحدثته خوارزمية فرز الحور في أن جذور الأشجار المختلفة لا تُحفظ بترتيب مُرتب؛ فلا توجد روابط "متدرجة" تربطها معًا في كومة واحدة. بدلًا من ذلك، في كل مرة تُقلص فيها الكومة في المرحلة الثانية، يتم البحث في الجذور للعثور على المدخل الأقصى.

نظرًا لوجود n خطوة تقليص، يجب على كل منها البحث في O (log n )  من جذور الشجرة عن الحد الأقصى، فإن أفضل وقت تشغيل لفرز الحور هو O ( n log n )  .

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

تم اقتراح نفس الهيكل كطابور أولوية للأغراض العامة تحت اسم كومة الترتيب اللاحق ، ^{[ 4 ]} تحقيق وقت إدخال مستهلك O (1) في هيكل أبسط من كومة ذات الحدين الضمنية .

تستخدم مكتبة musl C خوارزمية smoothsort لتنفيذها لـ qsort(). ^{[ 5 ] [ 6 ]}

• نسخة مع تعليق من EWD796a، 16 أغسطس 1981
• شرح حديث مفصل لخوارزمية Smoothsort
• ويكي بوكس: تنفيذ الخوارزميات/الفرز/الفرز السلس
• وصف وتطبيق نموذج كومة الحور
• نوشيتا، كوهي. ناكاتاني ، يوشينوبو (أبريل 1985). "في بنية الكومة المتداخلة في Smoothsort" . الأسس الرياضية لعلوم الكمبيوتر وتطبيقاتها ( اليابانية :数理解析研究所講究録) . 556 : 1 – 16. HDL : 2433/98975 .