مرتب سازی شل (Shell Sort) – به زبان ساده

«مرتب سازی شل» (Shell Sort) یکی از انواع «مرتب‌سازی درجی» (Insertion Sort) است. در مرتب‌سازی درجی، عناصر تنها یک موقعیت، رو به جلو جا به جا می‌شوند. هنگامی که یک عنصر به تعداد زیادی خانه به جلوتر جا به جا می‌شود، حرکات زیادی باید انجام شود.

مرتب سازی شل

ایده مرتب سازی شل آن است که امکان جا به جایی عناصر دور را فراهم کند. در مرتب سازی شل، آرایه برای مقادیر بزرگ h، به صورت h-sort مرتب‌سازی می‌شود. کاهش مقدار h تا هنگامی که ۱ شود، ادامه خواهد داشت. یک آرایه h-sorted گفته می‌شود اگر همه زیرلیست‌های h‌اُمین عنصر، مرتب‌سازی شده باشند. در ادامه، پیاده‌سازی مرتب سازی شل در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java) و «پایتون» (Python) انجام شده است. ولی ابتدا، برای درک بهتر مفهوم، یک مثال از مرتب سازی شل ارائه شده است.

فیلم آموزش الگوریتم های مرتب سازی در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

آرایه اولیه به صورتی است که در تصویر مشاهده می‌کنید. بنابراین، کار از $$gap=\frac{n}{2}$$ آغاز می‌شود (در این مثال، ۲ است).

۵۴ را به Temp منتقل کن.

عناصر سمت چپ ۵۴، کوچک‌تر از آن هستند و بنابراین، نیازی به تغییر نیست. لذا ۵۴ را به جای خود بازگردان. اکنون باید یکی یکی عناصر سمت راست شکاف را انتخاب کرد و آن‌ها را در موقعیت مناسب قرار داد.

ابتدا ۲ را به Temp ببر. ۲ را با arr[3-2]=34‎ مقایسه و به arr[gap+1 = 3]‎ جا به جا کن.

اکنون، شکاف به $$1(\frac{n}{4})$$ کاهش پیدا می‌کند. همه عناصر را با شروع از arr[1]‎ انتخاب و آن‌ها را عناصر در فاصله شکاف، مقایسه کن.

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

مرتب سازی شل در ++C

مرتب سازی شل در جاوا

مرتب سازی شل در پایتون ۳

مرتب سازی شل در #C

خروجی قطعه کد بالا در ادامه آمده است.

Array before sorting:
12 34 54 2 3
Array after sorting:
2 3 12 34 54

پیچیدگی زمانی پیاده‌سازی بالا برای مرتب سازی شل از درجه (O(n² است. در پیاده‌سازی بالا، شکاف در هر تکرار به نیم کاهش پیدا می‌کند.

فیلم مجموعه آموزش برنامه نویسی – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

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

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• آموزش ساختمان داده‌ها با C و ++C (همراه با حل نمونه سوالات کنکور ارشد)
• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• ساختمان داده (Data Structure) — راهنمای جامع و کاربردی
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
• مرتب‌سازی درجی (Insertion Sort) — به زبان ساده
• معرفی تکنیک‌های مرتب‌سازی (Sorting Techniques) — ساختار داده و الگوریتم ها

^^