Quicksort: راهنمای کامل توصیف، کارایی، و تصادفی‌سازی

ساختار تقسیم‌و‌غلبه Quicksort

Quicksort از الگوی تقسیم‌و‌غلبه معرفی‌شده پیش‌تر در این مجموعه پیروی می‌کند، اما با یک پیچش متمایز: برخلاف merge sort، که کار برابری در تقسیم و ترکیب انجام می‌دهد، quicksort تمام کار واقعی‌اش را در طول گام تقسیم انجام می‌دهد، و گام ترکیب بدیهی است.

QUICKSORT(A, p, r):
  اگر p < r:
      q = PARTITION(A, p, r)
      QUICKSORT(A, p, q - 1)
      QUICKSORT(A, q + 1, r)

کل منطق الگوریتم روی رویه PARTITION استوار است، که زیرآرایه A[p..r] را حول یک عنصر Pivot (محور) انتخاب‌شده بازچینی می‌کند، به‌گونه‌ای که هر عنصری در سمت چپ محور کمتر یا مساوی آن باشد، و هر عنصری در سمت راست بزرگ‌تر یا مساوی آن باشد. پس از افرازبندی، دو زیرآرایه حاصل به‌طور بازگشتی و مستقل مرتب می‌شوند، و از آنجا که محور از قبل در موقعیت نهایی مرتب‌شده‌اش است، هیچ گام ترکیب صریحی مورد نیاز نیست.

رویه Partition با جزئیات

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

PARTITION(A, p, r):
  x = A[r]           // محور
  i = p - 1
  برای j = p تا r - 1:
      اگر A[j] ≤ x:
          i = i + 1
          A[i] را با A[j] جابه‌جا کن
  A[i + 1] را با A[r] جابه‌جا کن
  i + 1 را برگردان

ردیابی یک مثال این را ملموس می‌کند. افراز [2, 8, 7, 1, 3, 5, 6, 4] با مقدار محور ۴ (آخرین عنصر) را در نظر بگیرید.

اولیه: [2, 8, 7, 1, 3, 5, 6, 4]   محور = 4، i = -1 (با ایندکس‌گذاری صفرمبنا p=0)

j=0: A[0]=2 ≤ 4 → i=0، جابه‌جایی A[0],A[0]: [2, 8, 7, 1, 3, 5, 6, 4]
j=1: A[1]=8 > 4 → بدون اقدام
j=2: A[2]=7 > 4 → بدون اقدام
j=3: A[3]=1 ≤ 4 → i=1، جابه‌جایی A[1],A[3]: [2, 1, 7, 8, 3, 5, 6, 4]
j=4: A[4]=3 ≤ 4 → i=2، جابه‌جایی A[2],A[4]: [2, 1, 3, 8, 7, 5, 6, 4]
j=5: A[5]=5 > 4 → بدون اقدام
j=6: A[6]=6 > 4 → بدون اقدام

جابه‌جایی نهایی: A[3] را با A[7] جابه‌جا کن: [2, 1, 3, 4, 7, 5, 6, 8]
q = 3 را برگردان — محور 4 اکنون در موقعیت نهایی‌اش است

پس از افرازبندی، عناصر [2, 1, 3] در سمت چپ همگی ≤ ۴ هستند، و عناصر [7, 5, 6, 8] در سمت راست همگی ≥ ۴ هستند، با خود محور که به‌درستی در ایندکس ۳ قرار گرفته. این رویه در زمان Θ(n) برای یک زیرآرایه به اندازه n اجرا می‌شود، چون یک عبور واحد از آرایه انجام می‌دهد.

بدترین‌حالت: ورودی از‌قبل‌مرتب‌شده یا معکوس‌مرتب‌شده

کارایی quicksort کاملاً به این بستگی دارد که افرازها چقدر متوازن باشند. بدترین حالت وقتی رخ می‌دهد که افراز به‌طور حداکثری نامتوازن باشد — یک زیرآرایه به اندازه n-1 و یکی به اندازه 0 — که با استفاده از طرح لوموتو بالا، هروقت آرایه ورودی از قبل مرتب یا معکوس‌مرتب باشد رخ می‌دهد.

رابطه بازگشتی بدترین‌حالت: T(n) = T(n-1) + T(0) + Θ(n)
                              = T(n-1) + Θ(n)

حل این رابطه بازگشتی (یک سری حسابی):
T(n) = Θ(n) + Θ(n-1) + ... + Θ(1) = Θ(n²)

این بدترین‌حالت Θ(n²) یک نگرانی عملی واقعی است: quicksort پیاده‌سازی‌شده به‌طور ساده، روی داده از‌قبل‌مرتب‌شده به‌طور فاجعه‌باری عمل می‌کند، سناریویی که به‌طور آزاردهنده‌ای مکرر با داده دنیای واقعی، مانند فایل‌های لاگ یا ورودی پیش‌پردازش‌شده، رخ می‌دهد.

بهترین‌حالت: افرازهای کاملاً متوازن

در انتهای مخالف، اگر افراز همیشه آرایه را به دو نیمه برابر تقسیم کند، رابطه بازگشتی از نظر ساختار با ساختار merge sort یکسان می‌شود:

رابطه بازگشتی بهترین‌حالت: T(n) = 2T(n/2) + Θ(n)

با استفاده از روش استاد که پیش‌تر در این مجموعه پوشش داده شد:
T(n) = Θ(n log n)

یک بینش حیاتی: افرازهای متوازن رایج‌تر از انتظار هستند

یک بینش کلیدی رفتار میانگین quicksort را بسیار بهتر از آنچه بدترین‌حالت بدبینانه پیشنهاد می‌کند می‌سازد: حتی یک تقسیم به‌طور پیوسته نامتوازن، مانند نسبت ۹-به-۱ در هر سطح، همچنان زمان اجرای کلی Θ(n log n) تولید می‌کند، چون عمق بازگشت لگاریتمی باقی می‌ماند و کار هر-سطح خطی باقی می‌ماند. فقط تقسیم‌هایی که به‌اندازه یک مقدار ثابت در هر تک سطح نامتوازن باشند، مانند همیشه جدا کردن فقط یک عنصر، بدترین‌حالت درجه‌دوم واقعی را تولید می‌کنند.

Quicksort تصادفی: محافظت در برابر بدترین‌حالت

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

RANDOMIZED-PARTITION(A, p, r):
  i = RANDOM(p, r)
  A[r] را با A[i] جابه‌جا کن
  PARTITION(A, p, r) را برگردان

RANDOMIZED-QUICKSORT(A, p, r):
  اگر p < r:
      q = RANDOMIZED-PARTITION(A, p, r)
      RANDOMIZED-QUICKSORT(A, p, q - 1)
      RANDOMIZED-QUICKSORT(A, q + 1, r)

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

تحلیل زمان اجرای مورد انتظار با استفاده از متغیرهای نشانگر

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

فرض کن Xij = نشانگر اینکه عناصر zi و zj
         (i-امین و j-امین کوچک‌ترین عناصر) هرگز مقایسه می‌شوند

تعداد کل مقایسه‌های مورد انتظار این است:
E[X] = Σ Σ (i

این به‌طور دقیق تأیید می‌کند quicksort تصادفی به زمان اجرای مورد انتظار O(n log n) روی هر ورودی دست می‌یابد، با استفاده از همان تکنیک‌های متغیر نشانگر و سری هارمونیک که برای مسئله استخدام که پیش‌تر در این مجموعه بحث شد مفید ثابت شدند.

چرا Quicksort با وجود بدترین‌حالتش محبوب باقی مانده

با وجود اینکه merge sort و heapsort، هر دو در جای دیگری در این مجموعه بحث شده‌اند، کارایی Θ(n log n) تضمین‌شده در بدترین‌حالت ارائه می‌دهند، quicksort در عمل به چند دلیل بسیار محبوب باقی می‌ماند: فاکتورهای ثابت آن معمولاً کوچک‌تر از merge sort است، برخلاف merge sort درجا مرتب می‌کند، و الگوی دسترسی‌اش محلیت کش عالی نشان می‌دهد، که پیش‌تر در این مجموعه در زمینه معماری کامپیوتر بحث شد، چون گام partition حافظه را به‌صورت پی‌درپی اسکن می‌کند. تصادفی‌سازی ریسک عملی بدترین‌حالت را حذف می‌کند، که quicksort تصادفی را به انتخاب استاندارد در بیشتر پیاده‌سازی‌های کتابخانه مرتب‌سازی دنیای واقعی تبدیل می‌کند.