مرتب‌سازی شل

مرتب‌سازی شِل یک الگوریتم مرتب سازی است که با توجه به دو مورد زیر صورت عمومی مرتب سازی درجی می‌باشد:

• مرتب سازی درجی وقتی کارآمد است که ورودی «تقریبا مرتب» باشد.
• مرتب سازی درجی معمولاً کم بازده‌است چون مقادیر را در هر زمان فقط به اندازه یک موقعیت جابجا می‌کند.

تاریخچه

این مرتب سازی به نام مخترعش، دونالد شِل که این الگوریتم را در سال ۱۹۵۹ منتشر کرد نام گذاری شده‌است. برخی کتاب‌ها و منابع قدیمی تر این الگوریتم را «شل- مِتزنِر» نیز نامیده‌اند ولی طبق گفتهٔ خود مارلین متزنر (Marlene Metzner) «من هیچ کاری برای این الگوریتم انجام ندادم و اسم من هیچ وقت نباید به آن اضافه می‌شد» نام آن به شِل تغییر یافت.

پیاده سازی

در این الگوریتم از روش مرتب‌سازی درجی استفاده می‌شود. به عبارتی ابتدا لیست را به چند دسته تقسیم می‌کند و هر کدام را جداگانه مرتب می‌کند. برای مثال اگر در ابتدا به ۳ دسته تقسیم کند، هر دسته را جداگانه به روش درجی که گفته شد، مرتب می‌کند. در هر مرحله، تعداد دسته‌ها نصف می‌شود (دسته‌ها بر اساس باقی مانده شان یا همان دسته‌های هم نهشتی). این عمل را ادامه می‌دهد تا سرانجام، تنها یک دسته شامل کل لیست داشته باشیم.

به عنوان مثال رشته f d a c b e را تحت این الگوریتم مرتب می‌کنیم.
کد: F d a c b e  : شروع

          c     b   a    f    d    e            : مرحله اول
          a     b   c    e    d    f            : مرحله دوم
          a     b   c    d    e    f            : نتیجه

در مرحله اول داده‌های با فاصله ۳ از یکدیگر، مقایسه و مرتب شده، در مرحله دوم داده‌های با فاصله ۲ از یکدیگر، مقایسه و مرتب می‌شوند و در مرحله سوم داده‌ها با فاصله یک از یکدیگر مقایسه و مرتب می‌شوند.

منظور از فاصله سه این است که عنصر اول با عنصر چهارم(۳+۱)، عنصر دوم با عنصر پنجم(۵=۳+۲) و عنصر سوم با عنصر ششم(۶=۳+۳) مقایسه شده در جای مناسب خود قرار می‌گیرد.

برای انتخاب فاصله در اولین مرحله، تعداد عناصر لیست بر ۲ تقسیم می‌شود(n/۲) و فاصله بعدی نیز با تقسیم فاصله فعلی بر ۲ حاصل می‌گردد و الگریتم تا زمانی ادامه پیدا می‌کند که این فاصله به صفر برسد. برای نمونه اگر تعداد عناصر برابر با ۱۰ باشد، فاصله در مرحله اول برابر با ۵، در مرحله دوم برابر با ۲ ور در مرحله سوم برابر با ۱ و در نهایت برابر با صفر خواهد بود.

حال به عنوان یک مثال عددی، مثال زیر را در نظر بگیرید :

فرض کنید لیستی مانند لیست روبرو داریم که می‌خواهیم با استفاده از این الگوریتم آنرا مرتب کنیم : [ ۱۳ ۱۴ ۹۴ ۳۳ ۸۲ ۲۵ ۵۹ ۹۴ ۶۵ ۲۳ ۴۵ ۲۷ ۷۳ ۲۵ ۳۹ ۱۰ ]. حال اگر ما با یک گام(دسته بندی) ۵ تایی شروع کنیم، جدولی با ۵ ستون خواهیم داشت که صورت زیر خواهد بود:

۱۳ ۱۴ ۹۴ ۳۳ ۸۲
۲۵ ۵۹ ۹۴ ۶۵ ۲۳
۴۵ ۲۷ ۷۳ ۲۵ ۳۹
۱۰

حال اگر هر ستون را مرتب کنیم، خواهیم داشت :

۱۰ ۱۴ ۷۳ ۲۵ ۲۳
۱۳ ۲۷ ۹۴ ۳۳ ۳۹
۲۵ ۵۹ ۹۴ ۶۵ ۸۲
۴۵

برای اولین فراخوانی لیست رویرو را خواهیم داشت: [ ۱۰ ۱۴ ۷۳ ۲۵ ۲۳ ۱۳ ۲۷ ۹۴ ۳۳ ۳۹ ۲۵ ۵۹ ۹۴ ۶۵ ۸۲ ۴۵ ]. در اینجا عدد ۱۰ که در ابندای لیست بود، به انتهای لیست آورده شده‌است. سپس لیست با استفاده از یک دسته بنده ۳ تایی و پس از آن یک دسته بندی ۱ تایی بوسیله مرتب سازی درجی مرتب خواهد شد.

زمان اجرا

زمان مرتب سازی شل از (O(n پیروی می‌کند که نسبت به n^۲ بهبود خوبی پیدا کرده‌است لذا سرعت عمل روش مرتب سازی شل از روش‌های انتخابی، درجی و حبابی بیشتر است.

شبه کد الگوریتم

ورودی : آرایه a به طول n :

inc ← round(n/2)
while inc > ۰ do:
    for i = inc.. n − 2 do:
        temp ← a[i]
        j ← i
        while j ≥ inc and a[j − inc] > temp do:
            a[j] ← a[j − inc]
            j ← j − inc
        a[j] ← temp
    (inc ← round(inc / 2٫2

منابع

• Introduction to Algorithms (CLRS)-Second Edition - The MIT Press
• Babylon dictionary (Persian Computer Encyclopedia) - Computer and IT dictionary for Persian
• [۱]http://en.wikipedia.org/wiki/Shell_sort

پیوندهای خارجی

• [۲]http://www.csse.monash.edu.au/~lloyd/tildeAlgDS
• [۳]http://www.itl.nist.gov/div897/sqg/dads
• [۴]http://www.bgbm.org/CDEFD/CollectionModel/dsd.htm
• [۵]http://en.wikipedia.org/wiki/Data_structure