مرتب‌سازی شل

مرتب‌سازی درجی روی عضوهایی که gap خانه از هم فاصله دارند، با gapهای کوچک‌شونده تا ۱؛ عضوهای دور زود به جای درستشان نزدیک می‌شوند.

مرتب‌سازی درجی روی آرایه‌ی تقریباً مرتب خیلی سریع است، ولی عضوی که از جای درستش دور است باید یکی‌یکی خانه‌ها را طی کند. شل این مشکل را با gap حل می‌کند: اول عضوهایی را که gap خانه از هم فاصله دارند با مرتب‌سازی درجی مرتب می‌کند، تا عضوها با جهش‌های بلند به جای تقریبی‌شان برسند. بعد gap را نصف می‌کند و دوباره، تا gap = 1 که همان مرتب‌سازی درجی معمولی است، ولی روی آرایه‌ای که تقریباً مرتب شده.

ادامه‌ی توضیح ↓

زمان: O(n²) with gaps n/2, n/4, …; better with other gap sequences
حافظه: O(1)
هوروویتز–ساهنی، فصل ۷

ورودی:

n=8خروجی PDF

هشت عدد درهم: gapها ۴، ۲ و ۱.

def shell_sort(a):
gap = len(a) // 2
while gap > 0:
for j in range(gap, len(a)):
key = a[j]
i = j - gap
while i >= 0:
if a[i] <= key:
break
a[i + gap] = a[i]
i = i - gap
a[i + gap] = key
gap = gap // 2
return a

ناوردا: بعد از دوری که با gap = g انجام شد، هر زیردنباله‌ی a[k], a[k+g], a[k+2g], … مرتب است.

شروع اجرا

متغیرهای محلی

نارنجی = در همین گام عوض شد

`a` list

3533421014192744

Call stack

shell_sort()خط 1

گام ۱ از ۱۵۰

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

comparisons
shift
insert
ورودی فعلی (n=8)

نمایش به شکل جدول

n	comparisons	shift	insert
4	6	2.8	5
6	11.6	5.9	8
8	21.1	7	17
10	29.1	11.3	22
12	37.8	16.7	26
14	44	19.4	31
16	68.7	26.8	49

توضیح

ایده

هزینه

با gapهای n/2, n/4, …, 1 بدترین حالت O(n²) است، ولی در عمل خیلی بهتر از مرتب‌سازی درجی کار می‌کند.
با دنباله‌های بهتر (مثلاً 1, 4, 13, 40, …) زمان به حدود O(n^1.5) می‌رسد.
حافظه‌ی اضافه O(1)؛ پایدار نیست.

در trace به چه چیزی نگاه کنی

با سطح جزئیات «هر دور حلقه» فقط تغییر gap را ببین.
ورودی «برعکس مرتب» را با مرتب‌سازی درجی روی همان ورودی مقایسه کن (شمار shift).