LogoENEnglish

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

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

الگوریتم Quicksortروش PartitionQuicksort تصادفی

~6 دقیقه مطالعه · آخرین به‌روزرسانی ۱۶ شهریور ۱۴۰۵

ساختار تقسیم‌و‌غلبه 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 تصادفی را به انتخاب استاندارد در بیشتر پیاده‌سازی‌های کتابخانه مرتب‌سازی دنیای واقعی تبدیل می‌کند.

نوشته و پژوهش‌شده توسط دکتر شاهین صیامی

مقالات مرتبط

ساختارهای داده ابتدایی: پشته‌ها، صف‌ها، لیست‌های پیوندی، و درخت‌ها

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

ادامه

یافتن میانه بدون مرتب‌سازی کامل: الگوریتم‌های انتخاب زمان-خطی

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

ادامه

شکستن مانع n log n: توضیح الگوریتم‌های مرتب‌سازی زمان-خطی

هر الگوریتم مرتب‌سازی مبتنی بر مقایسه در بدترین‌حالت حداقل به زمان Ω(n log n) نیاز دارد، اما الگوریتم‌هایی که کاملاً از مقایسه اجتناب می‌کنند می‌توانند تحت شرایط درست در زمان خطی مرتب کنند. این راهنمای جامع کران پایین مرتب‌سازی مبتنی‌بر‌مقایسه را با استدلال درخت تصمیم اثبات می‌کند، سپس سه الگوریتم زمان-خطی — counting sort، radix sort، و bucket sort — را همراه با فرضیات ورودی خاصی که هرکدام نیاز دارند توضیح می‌دهد.

ادامه

Heapsort و صف‌های اولویت: راهنمای کامل هیپ دودویی

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

ادامه

<h2>Why Randomness Enters Algorithm Analysis</h2> <p>The worst-case, best-case, and average-case running times discussed earlier in this series all assume the algorithm itself behaves deterministically, and any variation comes purely from the input. A different situation arises when either the input distribution is unknown or an algorithm deliberately makes random choices during its own execution. Both situations require the tools of <code>Probabilistic Analysis</code>.</p> <h2>The Hiring Problem: A Motivating Example</h2> <p>Consider a company interviewing candidates one at a time for a position, always hiring the current best candidate seen so far and firing the previous hire. Each interview costs a small amount, but each hire costs significantly more, since it involves paperwork, onboarding, and severance for the person being replaced. The question is: what is the expected total hiring cost across the entire process?</p> <pre class="code-block"><code>HIRE-ASSISTANT(n): best = candidate 0 (a placeholder, ranked worst) for i = 1 to n: interview candidate i if candidate i is better than best: best = candidate i hire candidate i</code></pre><br> <p>If candidates arrive in the worst possible order — already sorted from worst to best — every single candidate is hired, resulting in <code>n</code> hires, a costly worst case. But if the order of candidates is random, far fewer hires are expected on average, since a random arrival order makes it unlikely that many consecutive candidates each set a new record.</p> <h2>Two Approaches to Handling the Order of Inputs</h2> <p>There are two distinct ways to reason about this randomness, and it is important not to confuse them.</p> <ul> <li><code>Probabilistic Analysis of a Deterministic Algorithm</code>: assume the input itself comes from some probability distribution (such as a uniformly random ordering of candidates), and analyze the expected running time of a fixed, non-random algorithm over that input distribution.</li> <li><code>Randomized Algorithms</code>: the algorithm itself makes random choices during execution (such as randomly shuffling the candidate order before processing them, regardless of the order they actually arrived in), guaranteeing good expected performance for any input, since the randomness comes from the algorithm rather than an assumption about the input.</li> </ul> <p>The second approach is generally more powerful and reliable in practice, since it removes any dependence on assumptions about how inputs are distributed in the real world, which may not hold. A <code>Randomized Algorithm</code> for the hiring problem simply permutes the candidates randomly before running the same procedure, guaranteeing the same good expected cost regardless of the input's original order.</p> <h2>Indicator Random Variables: A Powerful Analytical Tool</h2> <p>Computing an expected value directly can be complicated when many interacting events are involved. <code>Indicator Random Variables</code> provide an elegant technique that dramatically simplifies such calculations, especially when combined with the linearity of expectation.</p> <p>For an event <code>A</code>, define the indicator random variable:</p> <pre class="code-block"><code>I{A} = 1 if A occurs I{A} = 0 if A does not occur Key property: E[I{A}] = Pr{A}</code></pre><br> <p>The expected value of an indicator variable simply equals the probability of the event it indicates. This becomes powerful when combined with <code>Linearity of Expectation</code>, which states that the expected value of a sum of random variables equals the sum of their expected values, regardless of whether the variables are independent.</p> <pre class="code-block"><code>E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn] This holds even when the Xi are NOT independent — a crucial and often surprising fact</code></pre><br> <h2>Applying Indicator Variables to the Hiring Problem</h2> <p>Let <code>Xi</code> be the indicator random variable for the event that candidate <code>i</code> is hired. The total number of hires is <code>X = X1 + X2 + ... + Xn</code>. By linearity of expectation:</p> <pre class="code-block"><code>E[X] = E[X1] + E[X2] + ... + E[Xn] = Σ Pr{candidate i is hired}</code></pre><br> <p>Candidate <code>i</code> is hired precisely when candidate <code>i</code> is the best among the first <code>i</code> candidates seen so far. If the candidates arrive in a uniformly random order, candidate <code>i</code> is equally likely to be the best, second-best, or any rank among the first <code>i</code> candidates, so:</p> <pre class="code-block"><code>Pr{candidate i is hired} = 1/i Therefore: E[X] = Σ (i=1 to n) 1/i = H(n) This is the Harmonic Series, and H(n) = Θ(ln n)</code></pre><br> <p>This remarkable result shows that, despite there being <code>n</code> candidates, the expected number of hires grows only logarithmically with <code>n</code>, a dramatic improvement over the worst-case scenario of <code>n</code> hires. This calculation, made simple through indicator variables, would be considerably more complex using direct probability calculations involving joint distributions.</p> <h2>Why This Technique Generalizes So Widely</h2> <p>The indicator random variable technique is not specific to the hiring problem; it is a general tool applicable whenever a quantity of interest can be expressed as a sum of simpler zero-or-one outcomes, even when those outcomes are correlated with each other. This makes it one of the most broadly useful techniques in the probabilistic analysis of algorithms, and it reappears throughout later topics in this series wherever expected running time needs to be computed.</p> <h2>Why Randomization Matters for Real-World Algorithm Design</h2> <p>Randomized algorithms are used throughout computer science specifically because they can guarantee good expected performance without needing any assumption about the distribution of real-world inputs, protecting against adversarial or unusually structured inputs that could otherwise trigger an algorithm's worst case. A prominent example, explored in depth later in this series, is randomized quicksort, where randomly shuffling the input before sorting protects against the specific input orderings that would otherwise trigger quicksort's quadratic worst case.</p>

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

ادامه

حل رابطه‌های بازگشتی: Substitution، Recursion-Tree، و روش استاد

زمان اجرای هر الگوریتم تقسیم‌و‌غلبه توسط یک رابطه بازگشتی توصیف می‌شود، و حل آن رابطه برای درک کارایی الگوریتم ضروری است. این راهنمای جامع سه تکنیک استاندارد برای حل رابطه‌های بازگشتی را پوشش می‌دهد: روش substitution برای اثبات یک کران حدس‌زده‌شده، روش recursion-tree برای تولید یک حدس، و روش استاد به‌عنوان یک میان‌بر سریع برای یک دسته رایج از رابطه‌های بازگشتی.

ادامه
مقاله‌ی قبلیمقاله‌ی بعدی