خوارزمية فرز شل مع مثال

ما هو فرز شل؟

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

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

تتبع هذه الفجوة، أو الفاصل الزمني، تسلسلًا مختارًا مثل تسلسل شل الأصلي، أو تسلسل كنوت، أو تسلسل هيبارد، أو تسلسل سيدجويك. تسلسل شل الأصلي هو n/2, n/4, ..., 1.

خوارزمية فرز الصدفة

الخطوة 1) قم بتهيئة قيمة الفاصل الزمني h = n/2، حيث n هو حجم المصفوفة.

الخطوة 2) ضع جميع العناصر التي تقع ضمن مسافة من الفترة h في قائمة فرعية.

الخطوة 3) قم بفرز كل قائمة فرعية باستخدام فرز الإدراج.

الخطوة 4) حدد فترة زمنية جديدة h = h/2.

الخطوة 5) إذا كانت قيمة h أكبر من 0، فارجع إلى الخطوة 2. وإلا، فانتقل إلى الخطوة 6.

الخطوة 6) أصبحت المصفوفة الناتجة الآن مرتبة بالكامل.

كيف يعمل فرز شل

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

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

شرح آلية عمل خوارزمية فرز شل مع مثال

لنقم بفرز المصفوفة أدناه باستخدام خوارزمية فرز شل.

الخطوة 1) حجم المصفوفة هو 8، لذا فإن قيمة الفاصل الزمني الأولي هي h = 8/2 = 4.

الخطوة 2) قم بتجميع العناصر على مسافة أربعة مواضع. القوائم الفرعية: {8، 1}، {6، 4}، {7، 5}، {2، 3}.

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

الخطوة 4) قلل الفترة. الفترة الجديدة هي h = 4/2 = 2.

الخطوة 5) لأن 2 > 0، ارجع إلى الخطوة 2 وقم بتجميع العناصر على بعد موضعين: {1، 5، 8، 7} و {4، 2، 6، 3}.

رتب القائمة الفرعية الأولى. تصبح المصفوفة كالتالي:

بعد فرز القائمة الفرعية الثانية:

قلل الفاصل الزمني مرة أخرى إلى h = 2/2 = 1. مع وجود فجوة مقدارها واحد، يقوم Shell Sort بتشغيل عملية فرز الإدراج النهائية على المصفوفة بأكملها، كما هو موضح أدناه.

الخطوة 6) بتقسيم الفترة مرة أخرى نحصل على 0. المصفوفة الآن مرتبة بالكامل:

مستعار-Code لفرز شل

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

برنامج فرز شل في C/C++

الإدخال:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

الإخراج:

Sorted Output:

1 2 3 4 5 6 7 8

مثال فرز شل في Python

الإدخال:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

الإخراج:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

تطبيقات شل الفرز

لا تزال خوارزمية فرز الصدفة (Shell Sort) تظهر في الأنظمة الحديثة حيث تُعد مساحة المكدس أو البساطة مهمة.

• استخدم نواة لينكس يستخدم خوارزمية فرز الصدفة في الأماكن التي يكون فيها تجنب مكدس الاستدعاءات أمراً مهماً.
• تستخدم مكتبة uClibc المضمنة للغة C خوارزمية Shell Sort للحفاظ على انخفاض استخدام الذاكرة.
• يستخدم bzip2 خوارزمية Shell Sort لتجنب التكرار العميق أثناء فرز الكتل.
• تُفضل البرامج الثابتة المدمجة خوارزمية فرز شل لمجموعات البيانات الصغيرة حيث يكون التكرار مقيدًا.

مزايا وعيوب فرز الصدف

تحليل تعقيد فرز القشرة

تعقيد الوقت لفرز القشرة

يعتمد التعقيد الزمني لخوارزمية فرز شل على تسلسل الفجوات المستخدم.

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

في أسوأ الحالات، يتم ترتيب المصفوفة بحيث تحتاج العناصر إلى أقصى عدد من المقارنات، وتسيطر الزيادة النهائية عند O(n^2) مع التسلسل الأصلي لـ Shell.

1. أفضل تعقيد للحالة: O(n log n)
2. التعقيد في الحالة المتوسطة: من O(n log n) إلى O(n^(4/3)) اعتمادًا على تسلسل الفجوات
3. التعقيد في أسوأ الحالات: O(n^2) مع التسلسل الأصلي لشركة شل

لا يزال تحديد أفضل تسلسل فجوات للأغراض العامة مسألة بحثية مفتوحة، على الرغم من أن تسلسلات سيدجويك وسيورا تعمل بشكل جيد من الناحية العملية.

تعقيد مساحة فرز القشرة

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

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