AlgoVerse

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

به‌جای جابه‌جا کردن رکوردهای بزرگ، جدولی از اندیس‌ها را مرتب می‌کند و بعد هر رکورد را فقط یک بار، با دنبال کردن دورهای جایگشت، سر جایش می‌برد.

اگر هر رکورد بزرگ باشد (مثلاً پرونده‌ی یک دانشجو)، جابه‌جا کردنش گران است. مرتب‌سازی جدولی دو گام دارد:

ادامه‌ی توضیح ↓
ورودی:
n=6خروجی PDF

شش رکورد؛ جدول اندیس‌ها مرتب می‌شود و بعد یک دور چهارتایی دنبال می‌شود (۱۴ و ۵۰ از قبل سر جایشان‌اند).

  1. def table_sort(a):
  2. n = len(a)
  3. # 1. Sort a table of indices instead of the (large) records themselves.
  4. t = list(range(n))
  5. for i in range(1, n):
  6. j = i
  7. while j > 0 and a[t[j - 1]] > a[t[j]]:
  8. t[j - 1], t[j] = t[j], t[j - 1]
  9. j = j - 1
  10. # 2. Move each record once, following the cycles of the permutation t.
  11. for i in range(n):
  12. if t[i] == i:
  13. continue
  14. temp = a[i]
  15. j = i
  16. while t[j] != i:
  17. k = t[j]
  18. a[j] = a[k]
  19. t[j] = j
  20. j = k
  21. a[j] = temp
  22. t[j] = j
  23. return a

ناوردا: در گام ۲، هر اندیسی که t[j] = j شده، رکورد نهایی‌اش را دارد و دیگر جابه‌جا نمی‌شود.

شروع اجرا

350141122423264505

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

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

a list

351412422650

Call stack

  1. table_sort()خط 1
گام ۱ از ۷۳
خط سیاه = open_cycle · خط نارنجی = گام کلیدیswap_index: 0/5 · open_cycle: 0/1 · move: 0/3 · close_cycle: 0/1

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

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

    • swap_index
    • move
    • ورودی فعلی (n=6)
    01020304681012n = تعداد عضوهای آرایهswap_indexmove
    نمایش به شکل جدول
    nswap_indexmove
    43.32.2
    67.64.1
    8125
    1021.36.3
    1229.49.3
    توضیح

    ایده

    اگر هر رکورد بزرگ باشد (مثلاً پرونده‌ی یک دانشجو)، جابه‌جا کردنش گران است. مرتب‌سازی جدولی دو گام دارد:

    1. مرتب کردن جدول اندیس‌ها: آرایه‌ی t از اندیس‌ها را طوری مرتب می‌کنیم که a[t[0]] ≤ a[t[1]] ≤ …. رکوردها اصلاً تکان نمی‌خورند؛ فقط عددهای کوچک t جابه‌جا می‌شوند. (گاهی همین کافی است: رکوردها را به ترتیب t بخوان.)
    2. جابه‌جایی فیزیکی: t یک جایگشت است و هر جایگشت از چند دور ساخته شده. در هر دور، یک رکورد را کنار می‌گذاریم، بقیه را هر کدام یک بار سر جای نهایی‌شان می‌بریم و رکورد کنارگذاشته را در آخرین جای خالی می‌گذاریم.

    هزینه

    گام ۲ هر رکورد را حداکثر یک بار جابه‌جا می‌کند: O(n) جابه‌جایی رکورد، در برابر O(n²) در مرتب‌سازی درجی معمولی.

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

    • در گام ۱ میله‌ها ثابت‌اند و فقط t در پنل حافظه عوض می‌شود؛ در گام ۲ میله‌ها دور به دور سر جایشان می‌روند.