مرتب‌سازی شل

تاریخچه

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

کارایی زمانی

در روش مرتب‌سازی درجی در بدترین حالت الگوریتم از (O(n ۲ است درحالی که با مرتب‌سازی صدفی این زمان به (O(n log۲ کاهش یافته‌است.
در مرتب‌سازی صدفی، ابتدا داده‌ها در گام‌های بزرگتری جابه جا می‌شوند اما در هر مرحله فاصله این جابه جایی‌ها کم تر شده و به جابه جایی‌های جزئی می‌رسد.

دنباله فاصله‌ها

دنباله فاصله‌ها یک قسمت کامل از مرتب‌سازی شِل می‌باشد. هر دنباله افزایشی ای می‌تواند در آن مورد استفاده قرار بگیرد به شرطی که آخرین عنصر افزاینده آن ۱ باشد. الگوریتم با انجام یک مرتب‌سازی درجی فاصله‌ای شروع به کار می‌کند که فاصله در آن اولین عدد موجود در دنباله فاصله‌ها می‌باشد. سپس با انجام مرتب‌سازی درجی فاصله‌ای با استفاده از هر عدد موجود در دنبالهٔ فاصله‌ها به کار خود ادامه می‌دهد تا آنجا که فاصله به مقدار ۱ برسد. وقتی که مقدار فاصله ۱ باشد مرتب‌سازی فاصله‌ای به سادگی یک مرتب‌سازی درجی معمولی است که ضمانت می‌کند که لیست نهایی مرتب شده‌است.

دنباله فاصله‌ای اصلی که توسط خود دونالد شِل پیشنهاد شد از  شروع می‌شود و همین طور آنقدر عدد را نصف می‌کند تا به ۱ برسد. این دنباله کارایی فوق‌العاده‌ای برای الگوریتم‌های چهارتایی مثل مرتب‌سازی درجی فراهم می‌کند، ولی به کمی تغییر می‌توان زمان اجرای متوسط و بدترین حالت آن را باز هم بهبود بخشید. درکتاب مرجع وایس (Weiss) نشان داده شده‌است که اگر داده اولیه یک آرایه به صورت {کوچک اول، بزرگ اول، کوچک دوم، بزرگ دوم و...} باشد که در آن نیمهٔ بالایی اعداد در موقعیت مرتب شده در خانه‌های زوج و نیمهٔ پایینی اعداد به همین صورت در خانه‌های فرد قرار گرفته باشند، این دنباله یک مرتب‌سازی با بدترین زمان اجرای  را تولید خواهد کرد.

شاید مهم‌ترین ویژگی مرتب‌سازی شِل این باشد که حتی با کم و کم تر شدن فاصله‌ها عناصر به صورت k- مرتب شده باقی می‌مانند. برای مثال اگر لیستی در ابتدا ۵- مرتب شده باشد و آن را ۳- مرتب‌سازی کنیم آنگاه لیست نه تنها ۳- مرتب شده‌است، بلکه ۳ و ۵- مرتب شده نیز می‌باشد. اگر این درست نبود الگوریتم عملیاتی که در تکرارهای قبلی انجام داده‌است را خنثی می‌کند و دوباره از اول شروع به کار می‌کند و چنین زمان اجرای پایینی نخواهد داشت.

بسته به نوع دنباله فاصله انتخاب شده، ثابت شده‌است که مرتب‌سازی شِل دارای بدترین زمان اجرای (با استفاده از افزاینده‌های شِل که ۱/۲ اندازه آرایه هستند و هر بار نصف می‌شوند)،  (با استفاده از افزاینده‌های هیباردِ )،
 (با استفاده از افزاینده‌های سِدگِویکِ
 یا)، یا 
(با استفاده از افزاینده‌های پرَتِ )، و احتمالاً زمان‌های اجرای بهتر و اثبات نشده‌ای، می‌باشد.
همچنین توسط پونن (Poonen)، پلکستون(Plaxton) و سوئل(Suel) اثبات شد که بدترین حالت مرتب‌سازی شِل به صورت
 وجود ندارد.

بهترین دنباله با استناد به تحقیقات Marcin Ciura دنبالهٔ {۱, ۴, ۱۰, ۲۳, ۵۷, ۱۳۲, ۳۰۱, ۷۰۱, ۱۷۵۰} می‌باشد. این تحقیقات همچنین نتیجه می‌دهند که در مرتب‌سازی شِل مقایسه‌ها، به جای جابجایی، باید عملکرد غالب در نظر گرفته شوند. مرتب‌سازی شِل با استفاده از این دنباله از مرتب‌سازی درجی، یا هیپ سریع تر اجرا می‌شود و با این حال که در آرایه‌های کوچک، از مرتب‌سازی‌سازی سریع نیز سریع تر عمل می‌کند، در آرایه‌های به قدر کافی بزرگ از آن باز می‌ماند.

بعد از ۱۷۵۰ در دنباله بالا، فاصله‌هایی با پیشروی هندسی می‌توانند مورد استفاده قرار بگیرند. مثل:

nextgap = round(gap * ۲٫۲)

یک دنبالهٔ دیگر که به صورت تجربی بهتر عمل می‌کند دنبالهٔ اعداد فیبوناچی (بدون یکی از ۱های اولیه) دو بار به توان عدد طلایی است، که دنبالهٔ زیر را ناشی می‌شود:
{۱, ۹, ۳۴, ۱۸۲, ۸۳۶, ۴۰۲۵, ۱۹۰۰۱, ۹۰۳۵۸, ۴۲۸۴۸۱, ۲۰۳۴۰۳۵, ۹۶۵۱۷۸۷, ۴۵۸۰۶۲۴۴, ۲۱۷۳۷۸۰۷۶, ۱۰۳۱۶۱۲۷۱۳, …}

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

استفاده از دنبالهٔ فاصله‌های Marcin Ciura با یک مرتب‌سازی درجی داخلی:
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# Start with the largest gap and work down to a gap of 1 
foreach (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted 
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }

}

مرتب‌سازی صدفی موازی

استفاده از روش حل و تقسیم در مورد الگوریتم مرتب‌سازی صدفی به خوبی جواب می‌دهد.
در هر مرحله از مرتب‌سازی، می‌توان آرایه اصلی را به چند زیر آرایه که با یکدیگر تداخل نداشته باشند تقسیم کرد و هرکدام را به‌طور مجزا مرتب نمود و در نهایت این آرایه‌های مرتب شده را در هم ادغام کرد.