مرتب‌سازی شل
مرتب‌سازی شِل یا مرتب سازی صدفی یکی از قدیمی‌ترین الگوریتم‌های مرتب‌سازی و تعمیمی از مرتب‌سازی درجی با در نظر گرفتن دو نکته زیر است: مرتب‌سازی صدفی، الگوریتمی سریع و کارآمد و در عین حال یادگیری و پیاده‌سازی آن ساده است.
البته این نکته قابل توجه است که مرتب‌سازی صدفی درحقیقت به تنهایی داده‌ها را مرتب نمی‌کند بلکه به نوعی از سایر مرتب‌سازی‌ها استفاده کرده و با یک دسته‌بندی مناسب که موجب می‌شود تعداد دفعاتی که هر داده بررسی می‌شود کاهش یابد، کارایی آن‌ها را افزایش می‌دهد.
formula_1
این مرتب‌سازی به نام مخترعش، دونالد شِل که این الگوریتم را در سال 1995 منتشر کرد نام‌گذاری شده‌است. برخی کتاب‌ها و منابع قدیمی تر این الگوریتم را «شل- مِتزنِر» نیز نامیده‌اند ولی طبق گفتهٔ خود مارلین متزنر (Marlene Metzner) «من هیچ کاری برای این الگوریتم انجام ندادم و اسم من هیچ وقت نباید به آن اضافه می‌شد» نام آن به شِل تغییر یافت.
در روش مرتب‌سازی درجی در بدترین حالت الگوریتم از (O("n" است درحالی که با مرتب‌سازی صدفی این زمان به ("O("n" log کاهش یافته‌است.
در مرتب‌سازی صدفی، ابتدا داده‌ها در گام‌های بزرگتری جابه جا می‌شوند اما در هر مرحله فاصله این جابه جایی‌ها کم تر شده و به جابه جایی‌های جزئی می‌رسد.
در این الگوریتم از روش مرتب‌سازی درجی استفاده می‌شود. به عبارتی ابتدا لیست را به چند دسته تقسیم می‌کند و هر کدام را جداگانه مرتب می‌کند. برای مثال اگر در ابتدا به ۳ دسته تقسیم کند، هر دسته را جداگانه به روش درجی که گفته شد، مرتب می‌کند. در هر مرحله، تعداد دسته‌ها نصف می‌شود (دسته‌ها بر اساس باقی‌مانده شان یا همان دسته‌های هم نهشتی). این عمل را ادامه می‌دهد تا سرانجام، تنها یک دسته شامل کل لیست داشته باشیم.
به عنوان مثال رشته f d a c b e را تحت این الگوریتم مرتب می‌کنیم. کد: F d a c b e: شروع در مرحله اول داده‌های با فاصله ۳ از یکدیگر، مقایسه و مرتب شده، در مرحله دوم داده‌های با فاصله ۲ از یکدیگر، مقایسه و مرتب می‌شوند و در مرحله سوم داده‌ها با فاصله یک از یکدیگر مقایسه و مرتب می‌شوند.
منظور از فاصله سه این است که عنصر اول با عنصر چهارم(۳+۱)، عنصر دوم با عنصر پنجم(۵=۳+۲) و عنصر سوم با عنصر ششم(۶=۳+۳) مقایسه شده در جای مناسب خود قرار می‌گیرد.
برای انتخاب فاصله در اولین مرحله، تعداد عناصر لیست بر ۲ تقسیم می‌شود(n/۲) و فاصله بعدی نیز با تقسیم فاصله فعلی بر ۲ حاصل می‌گردد و الگوریتم تا زمانی ادامه پیدا می‌کند که این فاصله به صفر برسد. برای نمونه اگر تعداد عناصر برابر با ۱۰ باشد، فاصله در مرحله اول برابر با ۵، در مرحله دوم برابر با ۲ ور در مرحله سوم برابر با ۱ و در نهایت برابر با صفر خواهد بود.
حال به عنوان یک مثال عددی، مثال زیر را در نظر بگیرید:
فرض کنید لیستی مانند لیست روبرو داریم که می‌خواهیم با استفاده از این الگوریتم آن را مرتب کنیم : codice_1. حال اگر ما با یک گام (دسته‌بندی) ۵ تایی شروع کنیم، جدولی با ۵ ستون خواهیم داشت که صورت زیر خواهد بود:
حال اگر هر ستون را مرتب کنیم، خواهیم داشت:
برای اولین فراخوانی لیست رویرو را خواهیم داشت: codice_2. در اینجا عدد ۱۰ که در ابتدای لیست بود، به انتهای لیست آورده شده‌است. سپس لیست با استفاده از یک دسته بنده ۳ تایی و پس از آن یک دسته‌بندی ۱ تایی بوسیله مرتب‌سازی درجی مرتب خواهد شد.
پیاده‌سازی اصلی در بدترین حالت (O("n" مقایسه و جابجایی انجام می‌دهد.نوع دیگری از این الگوریتم با پیچیدگی کمتر نیز پیاده‌سازی شده که آن را به ("O("n" log "n ارتقا داده‌است ولی هنوز هم پیچیدگی این الگوریتم بدتر از بقیه مرتب‌سازی‌های مقایسه‌ای است که در ("O("n" log "n عمل می‌کنند. مرتب‌سازی شِل با مقایسهٔ عناصری که با یک فاصله (gap) از چندین مکان، جدا هستند مرتب‌سازی درجی را ارتقا می‌دهد. این عمل باعث می‌شود که یک عنصر «قدم‌های بزرگ‌تری» به سمت مکان نهایی خود بردارد. گذرهای چند گانه روی اطلاعات با کوچک و کوچک‌تر کردن اندازه‌های فاصله‌ها انجام می‌شوند. آخرین مرحلهٔ مرتب شِل شامل یک مرتب‌سازی درجی ساده‌است ولی بعد از آن می‌توانیم مطمئن باشیم که آرایهٔ داده‌ها تقریباً مرتب شده‌است.
یک مقدار کوچک را که به‌طور اولیه در انتهای غلط آرایه قرار گرفته‌است را در نظر بگیرید.
با استفاده از یک مرتب‌سازی (O("n" مثل مرتب‌سازی حبابی یا درجی، باید n مقایسه و جابجایی انجام دهیم تا این مقدار را روی کل آرایه تا انتهای دیگر آن جابجا کنیم. مرتب‌سازی شِل ابتدا مقادیر را با استفاده از قدم‌های بسیار بزرگ جابجا می‌کند، پس یک عنصر کوچک با چند مقایسه و جابجایی جزئی، مقدار زیادی از مسیر به سمت موقعیت نهایی خود را می‌پیماید. عملکرد مرتب‌سازی شِل را می‌توان به این صورت تصور کرد: تغییر لیست به یک جدول و مرتب کردن ستون‌ها (با استفاده از مرتب‌سازی درجی)، تکرار مرحله قبل، هر دفعه با تعداد کمتری از ستون‌های دراز تر. در نهایت جدول فقط یک ستون خواهد داشت که همان لیست مرتب شده نهایی است. تبدیل لیست به جدول برای راحت تر تصور کردن نحوه انجام مرتب‌سازی است در حالی که خود الگوریتم، مرتب‌سازی را درجا انجام می‌دهد (با افزایش ضریب با استفاده از اندازهٔ گام). برای مثال لیستی از اعداد به صورت codice_3 را در نظر بگیرید. اگر اندازه قدم را ۵ در نظر بگیریم می‌توان این گونه تصور کرد که لیست را به یک جدول با ۵ ستون تبدیل کرده‌ایم؛ که به صورت زیر خواهد بود: سپس هر ستون را مرتب می‌کنیم، که خواهیم داشت:
اگر این جدول را مثل لیستی از اعداد از انتها بخوانیم خواهیم داشت، codice_4 که در آن عدد ۱۰ که در لیست اولیه در انتها قرار داشت به ابتدای لیست آمده‌است. این لیست دوباره با یک مرتب‌سازی سه فاصله‌ای و در نهایت یک مرتب‌سازی یک فاصله‌ای (مرتب‌سازی درجی ساده) مرتب خواهد شد.
ایده و طرز کار این الگوریتم به صورت زیر است: با این کار، دنباله داده‌ها اندکی مرتب می‌شود و سپس عملیات بالا مجدداً تکرار می‌شود ولی این بار با آرایه‌ای کوچک‌تر. تا در نهایت در مرحله آخر به آرایه‌ای تنها با یک ستون می‌رسد.
به عنوان مثال برای مرتب‌سازی داده‌های { ۲ ۸ ۹ ۴ ۳ ۷ ۵ ۱ ۶ ۰ ۲ ۴ ۸ ۶ ۱ ۵ ۰ ۹ ۷ } با این روش، ابتدا داده‌ها در چند ستون (مثلاً در این جا در ۷ ستون) قرار داده می‌شود و سپس هر ستون به صورت مجزا مرتب می‌شود: در مرحله بعد: دنباله فاصله‌ها یک قسمت کامل از مرتب‌سازی شِل می‌باشد. هر دنباله افزایشی ای می‌تواند در آن مورد استفاده قرار بگیرد به شرطی که آخرین عنصر افزاینده آن ۱ باشد. الگوریتم با انجام یک مرتب‌سازی درجی فاصله‌ای شروع به کار می‌کند که فاصله در آن اولین عدد موجود در دنباله فاصله‌ها می‌باشد. سپس با انجام مرتب‌سازی درجی فاصله‌ای با استفاده از هر عدد موجود در دنبالهٔ فاصله‌ها به کار خود ادامه می‌دهد تا آنجا که فاصله به مقدار ۱ برسد. وقتی که مقدار فاصله ۱ باشد مرتب‌سازی فاصله‌ای به سادگی یک مرتب‌سازی درجی معمولی است که ضمانت می‌کند که لیست نهایی مرتب شده‌است. دنباله فاصله‌ای اصلی که توسط خود دونالد شِل پیشنهاد شد از formula_2 شروع می‌شود و همین طور آنقدر عدد را نصف می‌کند تا به ۱ برسد. این دنباله کارایی فوق‌العاده‌ای برای الگوریتم‌های چهارتایی مثل مرتب‌سازی درجی فراهم می‌کند، ولی به کمی تغییر می‌توان زمان اجرای متوسط و بدترین حالت آن را باز هم بهبود بخشید. درکتاب مرجع وایس (Weiss) نشان داده شده‌است که اگر داده اولیه یک آرایه به صورت {کوچک اول، بزرگ اول، کوچک دوم، بزرگ دوم و...} باشد که در آن نیمهٔ بالایی اعداد در موقعیت مرتب شده در خانه‌های زوج و نیمهٔ پایینی اعداد به همین صورت در خانه‌های فرد قرار گرفته باشند، این دنباله یک مرتب‌سازی با بدترین زمان اجرای formula_3 را تولید خواهد کرد. شاید مهم‌ترین ویژگی مرتب‌سازی شِل این باشد که حتی با کم و کم تر شدن فاصله‌ها عناصر به صورت k- مرتب شده باقی می‌مانند. برای مثال اگر لیستی در ابتدا ۵- مرتب شده باشد و آن را ۳- مرتب‌سازی کنیم آنگاه لیست نه تنها ۳- مرتب شده‌است، بلکه ۳ و ۵- مرتب شده نیز می‌باشد. اگر این درست نبود الگوریتم عملیاتی که در تکرارهای قبلی انجام داده‌است را خنثی می‌کند و دوباره از اول شروع به کار می‌کند و چنین زمان اجرای پایینی نخواهد داشت. بسته به نوع دنباله فاصله انتخاب شده، ثابت شده‌است که مرتب‌سازی شِل دارای بدترین زمان اجرایformula_3 (با استفاده از افزاینده‌های شِل که ۱/۲ اندازه آرایه هستند و هر بار نصف می‌شوند)، formula_5 (با استفاده از افزاینده‌های هیباردِ formula_6)، formula_7 (با استفاده از افزاینده‌های سِدگِویکِ formula_8 یاformula_9)، یا formula_10 (با استفاده از افزاینده‌های پرَتِ formula_11)، و احتمالاً زمان‌های اجرای بهتر و اثبات نشده‌ای، می‌باشد. همچنین توسط پونن (Poonen)، پلکستون(Plaxton) و سوئل(Suel) اثبات شد که بدترین حالت مرتب‌سازی شِل به صورت formula_12 وجود ندارد. بهترین دنباله با استناد به تحقیقات Marcin Ciura دنبالهٔ codice_5 می‌باشد. این تحقیقات همچنین نتیجه می‌دهند که در مرتب‌سازی شِل مقایسه‌ها، به جای جابجایی، باید عملکرد غالب در نظر گرفته شوند. مرتب‌سازی شِل با استفاده از این دنباله از مرتب‌سازی درجی، یا هیپ سریع تر اجرا می‌شود و با این حال که در آرایه‌های کوچک، از مرتب‌سازی‌سازی سریع نیز سریع تر عمل می‌کند، در آرایه‌های به قدر کافی بزرگ از آن باز می‌ماند. بعد از ۱۷۵۰ در دنباله بالا، فاصله‌هایی با پیشروی هندسی می‌توانند مورد استفاده قرار بگیرند. مثل: nextgap = round(gap * ۲٫۲) یک دنبالهٔ دیگر که به صورت تجربی بهتر عمل می‌کند دنبالهٔ اعداد فیبوناچی (بدون یکی از ۱های اولیه) دو بار به توان عدد طلایی است، که دنبالهٔ زیر را ناشی می‌شود:
استفاده از دنبالهٔ فاصله‌های Marcin Ciura با یک مرتب‌سازی درجی داخلی:
استفاده از روش حل و تقسیم در مورد الگوریتم مرتب‌سازی صدفی به خوبی جواب می‌دهد.
در هر مرحله از مرتب‌سازی، می‌توان آرایه اصلی را به چند زیر آرایه که با یکدیگر تداخل نداشته باشند تقسیم کرد و هرکدام را به‌طور مجزا مرتب نمود و در نهایت این آرایه‌های مرتب شده را در هم ادغام کرد.