AlgoVerse

مرتب‌سازی سریع

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

مرتب‌سازی سریع هم «تقسیم و حل» است، ولی کار اصلی را قبل از بازگشت انجام می‌دهد:

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

هشت عدد درهم با محور ۴ در دور اول؛ ۱۵ مقایسه.

  1. def quick_sort(a):
  2. sort(a, 0, len(a) - 1)
  3. return a
  6. def sort(a, lo, hi):
  7. if lo >= hi:
  8. return
  9. p = partition(a, lo, hi)
  10. sort(a, lo, p - 1)
  11. sort(a, p + 1, hi)
  14. def partition(a, lo, hi):
  15. pivot = a[hi]
  16. i = lo - 1
  17. for j in range(lo, hi):
  18. if a[j] <= pivot:
  19. i = i + 1
  20. a[i], a[j] = a[j], a[i]
  21. a[i + 1], a[hi] = a[hi], a[i + 1]
  22. return i + 1

ناوردا: در حلقه‌ی partition: a[lo..i] همه ≤ pivot و a[i+1..j−1] همه > pivot هستند.

شروع اجرا

2081721334556647

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

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

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

a list

28713564

Call stack

  1. quick_sort()خط 1
گام ۱ از ۱۲۴
خط سیاه = pivot · خط نارنجی = گام کلیدیcompare: 0/15 · swap: 0/9 · pivot: 0/5 · place: 0/5

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

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

    • comparisons
    • swaps
    • place
    • ورودی فعلی (n=8)
    020406046810121416n = تعداد عضوهای آرایهcomparisonsswapsplace
    نمایش به شکل جدول
    ncomparisonsswapsplace
    44.72.52.3
    69.84.43.6
    817.48.35.1
    1025.514.26.6
    1232.417.87.5
    1441.324.38.8
    1652.529.210.6
    توضیح

    ایده

    مرتب‌سازی سریع هم «تقسیم و حل» است، ولی کار اصلی را قبل از بازگشت انجام می‌دهد:

    1. یک عضو را محور (pivot) بگیر؛ اینجا آخرین عضو بازه، a[hi].
    2. بازه را افراز کن: عضوهای ≤ pivot به چپ و بقیه به راست بروند، و محور بین آن‌ها در جای نهایی‌اش بنشیند.
    3. دو طرف محور را به‌صورت بازگشتی مرتب کن. ترکیب لازم نیست، چون آرایه درجا مرتب شده است.

    افراز (روش لوموتو)

    i مرز بخش «کوچک‌ترها» است. j از lo تا hi − 1 جلو می‌رود؛ هر جا a[j] ≤ pivot بود، i یکی جلو می‌رود و a[i] و a[j] جابه‌جا می‌شوند. در پایان، محور با a[i + 1] جابه‌جا می‌شود.

    هزینه

    • اگر محور هر بار بازه را تقریباً نصف کند، عمق بازگشت log n و زمان O(n log n) است. این حالت متوسط هم هست.
    • اگر محور همیشه بزرگ‌ترین یا کوچک‌ترین باشد (مثلاً روی آرایه‌ی مرتب)، یک طرف خالی می‌ماند و زمان O(n²) می‌شود.
    • عضوهای تکراری هم با این روش افراز نامتوازن می‌سازند؛ ورودی «همه برابر» را ببین.
    • انتخاب تصادفی محور این خطر را کم می‌کند، ولی اینجا برای اینکه هر اجرا یکسان باشد، محور ثابت (آخرین عضو) است.

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

    • pivot بالای آرایه نوشته شده و نوار آبی بازه‌ی lo..hi است. فلش‌های i و j مرزهای افرازند.
    • در «درخت فراخوانی‌های بازگشتی»، شکل درخت را برای «بهترین حالت» و «بدترین حالت» مقایسه کن: یکی پهن و کوتاه، دیگری یک زنجیر بلند.