مرتب‌سازی شل

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

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

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

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

به عنوان مثال رشته 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 مقایسه و جابجایی انجام می‌دهد.
نوع دیگری از این الگوریتم با پیچیدگی کمتر نیز پیاده‌سازی شده که آن را به (O(n log n ارتقا داده‌است ولی هنوز هم پیچیدگی این الگوریتم بدتر از بقیه مرتب‌سازی‌های مقایسه‌ای است که در (O(n log n عمل می‌کنند.
مرتب‌سازی شِل با مقایسهٔ عناصری که با یک فاصله (gap) از چندین مکان، جدا هستند مرتب‌سازی درجی را ارتقا می‌دهد. این عمل باعث می‌شود که یک عنصر «قدم‌های بزرگ‌تری» به سمت مکان نهایی خود بردارد. گذرهای چند گانه روی اطلاعات با کوچک و کوچک‌تر کردن اندازه‌های فاصله‌ها انجام می‌شوند. آخرین مرحلهٔ مرتب شِل شامل یک مرتب‌سازی درجی ساده‌است ولی بعد از آن می‌توانیم مطمئن باشیم که آرایهٔ داده‌ها تقریباً مرتب شده‌است.

یک مقدار کوچک را که به‌طور اولیه در انتهای غلط آرایه قرار گرفته‌است را در نظر بگیرید.

با استفاده از یک مرتب‌سازی (O(n مثل مرتب‌سازی حبابی یا درجی، باید n مقایسه و جابجایی انجام دهیم تا این مقدار را روی کل آرایه تا انتهای دیگر آن جابجا کنیم. مرتب‌سازی شِل ابتدا مقادیر را با استفاده از قدم‌های بسیار بزرگ جابجا می‌کند، پس یک عنصر کوچک با چند مقایسه و جابجایی جزئی، مقدار زیادی از مسیر به سمت موقعیت نهایی خود را می‌پیماید. عملکرد مرتب‌سازی شِل را می‌توان به این صورت تصور کرد: تغییر لیست به یک جدول و مرتب کردن ستون‌ها (با استفاده از مرتب‌سازی درجی)، تکرار مرحله قبل، هر دفعه با تعداد کمتری از ستون‌های دراز تر. در نهایت جدول فقط یک ستون خواهد داشت که همان لیست مرتب شده نهایی است. تبدیل لیست به جدول برای راحت تر تصور کردن نحوه انجام مرتب‌سازی است در حالی که خود الگوریتم، مرتب‌سازی را درجا انجام می‌دهد (با افزایش ضریب با استفاده از اندازهٔ گام).
برای مثال لیستی از اعداد به صورت {۱۳, ۱۴, ۹۴, ۳۳, ۸۲, ۲۵, ۵۹, ۹۴, ۶۵, ۲۳, ۴۵, ۲۷, ۷۳, ۲۵, ۹۳, ۱۰} را در نظر بگیرید. اگر اندازه قدم را ۵ در نظر بگیریم می‌توان این گونه تصور کرد که لیست را به یک جدول با ۵ ستون تبدیل کرده‌ایم؛ که به صورت زیر خواهد بود:

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

سپس هر ستون را مرتب می‌کنیم، که خواهیم داشت:

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

اگر این جدول را مثل لیستی از اعداد از انتها بخوانیم خواهیم داشت، {۱۰, ۱۴, ۷۳, ۲۵, ۲۳, ۱۳, ۲۷, ۹۴, ۳۳, ۳۹, ۲۵, ۵۹, ۹۴, ۶۵, ۸۲, ۴۵} که در آن عدد ۱۰ که در لیست اولیه در انتها قرار داشت به ابتدای لیست آمده‌است. این لیست دوباره با یک مرتب‌سازی سه فاصله‌ای و در نهایت یک مرتب‌سازی یک فاصله‌ای (مرتب‌سازی درجی ساده) مرتب خواهد شد.

ایده و طرز کار این الگوریتم به صورت زیر است:

• چیدن دنباله داده‌ها در یک آرایه دو بعدی
• مرتب‌سازی ستون‌های آرایه

با این کار، دنباله داده‌ها اندکی مرتب می‌شود و سپس عملیات بالا مجدداً تکرار می‌شود ولی این بار با آرایه‌ای کوچک‌تر. تا در نهایت در مرحله آخر به آرایه‌ای تنها با یک ستون می‌رسد.

به عنوان مثال برای مرتب‌سازی داده‌های { ۲ ۸ ۹ ۴ ۳ ۷ ۵ ۱ ۶ ۰ ۲ ۴ ۸ ۶ ۱ ۵ ۰ ۹ ۷ } با این روش، ابتدا داده‌ها در چند ستون (مثلاً در این جا در ۷ ستون) قرار داده می‌شود و سپس هر ستون به صورت مجزا مرتب می‌شود:

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

در مرحله بعد:

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

دنباله فاصله‌ها یک قسمت کامل از مرتب‌سازی شِل می‌باشد. هر دنباله افزایشی ای می‌تواند در آن مورد استفاده قرار بگیرد به شرطی که آخرین عنصر افزاینده آن ۱ باشد. الگوریتم با انجام یک مرتب‌سازی درجی فاصله‌ای شروع به کار می‌کند که فاصله در آن اولین عدد موجود در دنباله فاصله‌ها می‌باشد. سپس با انجام مرتب‌سازی درجی فاصله‌ای با استفاده از هر عدد موجود در دنبالهٔ فاصله‌ها به کار خود ادامه می‌دهد تا آنجا که فاصله به مقدار ۱ برسد. وقتی که مقدار فاصله ۱ باشد مرتب‌سازی فاصله‌ای به سادگی یک مرتب‌سازی درجی معمولی است که ضمانت می‌کند که لیست نهایی مرتب شده‌است.
دنباله فاصله‌ای اصلی که توسط خود دونالد شِل پیشنهاد شد از ${\displaystyle N/2}$

استفاده از دنبالهٔ فاصله‌های 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
    }

}

استفاده از روش حل و تقسیم در مورد الگوریتم مرتب‌سازی صدفی به خوبی جواب می‌دهد.

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

• Introduction to Algorithms (CLRS)-Second Edition - The MIT Press
• Babylon dictionary (Persian Computer Encyclopedia) - Computer and IT dictionary for Persian
• [۱]

• [۲]http://www.csse.monash.edu.au/~lloyd/tildeAlgDS
• [۳]http://www.itl.nist.gov/div897/sqg/dads
• [۴]http://www.bgbm.org/CDEFD/CollectionModel/dsd.htm
• Shell Sort
• shell sort
• [۵]