مرتب‌سازی درجی

ایده

مرتب‌سازی درجی مثل مرتب کردن کارت‌های بازی در دست است. سمت چپ آرایه همیشه مرتب است. در هر دور، عضو بعدی (key) برداشته می‌شود، عضوهای بزرگ‌تر از آن در بخش مرتب یک خانه به راست می‌روند، و key در جای خالی قرار می‌گیرد.

گام‌ها

1. از خانه‌ی j = 1 شروع کن؛ بخش a[0..0] به‌تنهایی مرتب است.
2. key = a[j] را بردار.
3. با i از j − 1 به عقب برو. تا وقتی a[i] > key است، a[i] را یک خانه به راست ببر.
4. وقتی به عضوی رسیدی که ≤ key است (یا به ابتدای آرایه)، key را در a[i + 1] بگذار.
5. j را یکی زیاد کن و تکرار کن.

هزینه

• بهترین حالت (آرایه‌ی مرتب): هر key فقط یک مقایسه دارد، پس O(n).
• بدترین حالت (آرایه‌ی برعکس): key شماره‌ی j باید از کنار j عضو رد شود، پس روی هم n(n − 1)/2 جابه‌جایی و O(n²).
• حافظه‌ی اضافه فقط O(1) است: مرتب‌سازی درجا انجام می‌شود.

پایداری

چون شرط توقف a[i] ≤ key است، عضوهای برابر هیچ‌وقت از کنار هم رد نمی‌شوند. پس ترتیب نسبی عضوهای برابر حفظ می‌شود و مرتب‌سازی پایدار است. در ورودی «عضوهای تکراری» این را ببین.

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

• فلش‌های i و j زیر میله‌ها جای دو اندیس را نشان می‌دهند و key بالای آرایه نوشته شده است.
• میله‌ی نارنجی خانه‌ای است که در همین گام نوشته شد. میله‌ی با حاشیه‌ی نارنجی همان است که با key مقایسه می‌شود.
• شمار shift را در «بهترین حالت» و «بدترین حالت» مقایسه کن.