ما هي خوارزمية Shell Sort؟ شرح مبسّط مع مثال محلول وكود عملي

خوارزمية Shell Sort (تُنطق «شِل سورت» ونترجمها أحياناً بـ«ترتيب شِل») هي خوارزمية لترتيب عناصر مصفوفة، وهي في جوهرها نسخة مطوَّرة من خوارزمية الترتيب بالإدراج (Insertion Sort). الفكرة الأساسية بسيطة: بدلاً من مقارنة كل عنصر بجاره المباشر فقط، نقارن عناصر تفصل بينها فجوة (gap) كبيرة أولاً، ثم نُصغّر هذه الفجوة تدريجياً حتى تصل إلى 1. هذا يسمح للعناصر البعيدة عن مواقعها الصحيحة بأن تقفز مسافات طويلة بسرعة، بدلاً من التحرّك خطوة واحدة في كل مرة كما يحدث في الإدراج التقليدي.

سُمّيت الخوارزمية على اسم مبتكرها Donald Shell الذي نشرها عام 1959. وهي خوارزمية «في المكان» (in-place) أي لا تحتاج ذاكرة إضافية تُذكر، لكنها غير مستقرة (unstable)، بمعنى أنها قد تُغيّر الترتيب النسبي للعناصر المتساوية.

لماذا نحتاجها أصلاً؟

مشكلة الإدراج المباشر أن العنصر الصغير الموجود في آخر المصفوفة يحتاج إلى تبديلات كثيرة جداً ليصل إلى بدايتها، عنصراً بعنصر. Shell Sort تحلّ هذه المشكلة: بمقارنة عناصر متباعدة أولاً، ينتقل العنصر الصغير إلى قرب مكانه الصحيح بعدد قليل من الخطوات. وعندما تصل الفجوة إلى 1، تكون المصفوفة شبه مرتّبة، فتصبح خطوة الإدراج الأخيرة سريعة للغاية.

كيف تعمل خطوة بخطوة؟

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

مثال محلول خطوة بخطوة

لنأخذ المصفوفة: [23, 29, 15, 19, 31, 7, 9, 5] (عدد العناصر = 8) بفجوات 4 ثم 2 ثم 1.

الفجوة = 4: نقارن كل عنصر مع الذي يبعد عنه 4 مواضع ونبدّل عند الحاجة:

• (23, 31) سليم — (29, 7) نبدّل — (15, 9) نبدّل — (19, 5) نبدّل.
• النتيجة: [23, 7, 9, 5, 31, 29, 15, 19]

الفجوة = 2: نرتّب عناصر المواضع الزوجية معاً والفردية معاً:

• الزوجية [23, 9, 31, 15] تصبح [9, 15, 23, 31].
• الفردية [7, 5, 29, 19] تصبح [5, 7, 19, 29].
• النتيجة: [9, 5, 15, 7, 23, 19, 31, 29]

الفجوة = 1: ترتيب بالإدراج عادي على مصفوفة صارت شبه مرتّبة، فتنتهي بسرعة:

• النتيجة النهائية: [5, 7, 9, 15, 19, 23, 29, 31] ✅

كود عملي (بايثون)

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

لاحظ أن الجوهر هو نفس حلقة الإدراج، لكن بخطوة gap بدل 1. هذا التشابه الشديد هو سبب سهولة كتابتها.

سلسلة الفجوات: العامل الأهم في الأداء

أداء Shell Sort لا يعتمد على المنطق فحسب، بل على اختيار سلسلة الفجوات. استخدام n/2, n/4, ... (سلسلة شِل الأصلية) سهل لكنه يعطي أسوأ حالة بطيئة نسبياً O(n²). سلاسل أفضل تُحسّن الأداء بوضوح:

سلسلة الفجوات	الصيغة التقريبية	أسوأ حالة
Shell الأصلية	n/2, n/4, …	O(n²)
Hibbard	1, 3, 7, 15 … (2ᵏ−1)	O(n¹ᐟ⁵)
Sedgewick	متتالية خاصة	≈ O(n⁴ᐟ³)
Knuth	1, 4, 13, 40 …	جيدة عملياً

في المتوسط يتراوح الأداء الفعلي بين O(n log² n) و O(n¹ᐟ⁵) تقريباً حسب السلسلة، وهو أفضل بكثير من O(n²) الخاصة بالإدراج البسيط.

Shell Sort مقابل Quick / Merge

المعيار	Shell Sort	Quick Sort	Merge Sort
متوسط التعقيد	~O(n¹ᐟ²⁵)	O(n log n)	O(n log n)
ذاكرة إضافية	لا تُذكر	لا تُذكر	O(n)
مستقرة؟	لا	لا	نعم
سهولة الكتابة	عالية جداً	متوسطة	متوسطة

الخلاصة: Shell Sort خيار ممتاز للمصفوفات الصغيرة والمتوسطة وحين تريد كوداً بسيطاً بلا ذاكرة إضافية، بينما Quick Sort و Merge Sort تتفوّق مع البيانات الضخمة جداً.

نصيحة عملية وخطأ شائع

الخطأ الأكثر تكراراً عند التطبيق هو التعامل مع كل «مجموعة فجوة» كأنها مصفوفة منفصلة تُرتَّب بالكامل قبل الانتقال للتالية. الطريقة الصحيحة والأنظف — كما في الكود أعلاه — هي المرور على المصفوفة مرة واحدة لكل فجوة مع خطوة gap، فتُعالَج كل المجموعات بالتناوب. هذا يبسّط الكود ويقلّل الأخطاء.

الأسئلة الشائعة

هل Shell Sort أسرع من Quick Sort؟ غالباً لا مع البيانات الكبيرة؛ Quick Sort أسرع في المتوسط. لكن Shell Sort قد تتفوّق على المصفوفات الصغيرة أو شبه المرتّبة بفضل بساطتها وقلة تكاليفها الثابتة.

هل هي خوارزمية مستقرة؟ لا. قد تتغيّر المواضع النسبية للعناصر المتساوية، لذا تجنّبها إن كان الاستقرار شرطاً أساسياً.

ما أفضل سلسلة فجوات أستخدمها؟ عملياً، سلسلة Knuth (‏1, 4, 13, 40, …) أو Sedgewick تعطيان أداءً موثوقاً وسهل التطبيق، وهما أفضل من القسمة على 2 البسيطة.

أين تُستخدم فعلياً؟ تظهر في الأنظمة المدمجة ومكتبات ذات قيود ذاكرة، وأحياناً كطريقة ترتيب داخلية بسيطة حين لا يستحق الأمر تعقيد Quick أو Merge.