میانه میانه‌ها

زمان لازم برای انتحاب سریع به طور میانگین به صورت خطی رشد می‌کند، اما با انتخاب نامناسب عنصر محوری می‌تواند به صورت درجهٔ دو رشد کند. دلیل این امر این است که انتخاب سریع، یک الگوریتم تقسیم و حل است که هر مرحلهٔ آن زمانی از ${\displaystyle O(n)}$

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

الگوریتم میانه میانه‌ها، میانه را نه به صورت دقیق، بلکه به صورت تقریبی محاسبه می‌کند. اما این تضمین را می‌دهد که مقدار محاسبه شده بین ۳۰امین و ۷۰امین صدک قرار گرفته باشد؛ بنابراین در هر مرحله تعداد داده‌ها حداقل ۳۰٪ کاهش می‌یابد.

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

function select(list, left, right, n)
    if left = right
        return left
    loop
        pivotIndex := pivot(list, left, right)
        pivotIndex := partition(list, left, right, pivotIndex)
        if n = pivotIndex
            return n
        else if n < pivotIndex
            right := pivotIndex - 1
        else
            left := pivotIndex + 1

همانند انتخاب سریع در الگوریتم میانه میانه‌ها نیز یک زیر رَویه به نام «تقسیم کننده» وجود دارد که می‌تواند یک لیست را به دو بخش (اعضای کوچکتر از یک عنصر خاص و اعضای بزرگتر از آن) تقسیم کند. شبه کد یک تقسیم‌کننده که یک تقسیم بر پایهٔ [list[pivotindex انجام می‌دهد را در زیر می‌توانید مشاهده کنید:

 function partition(list, left, right, pivotIndex)
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  // Move pivot to end
     storeIndex := left
     for i from left to right-1
         if list[i] < pivotValue
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  // Move pivot to its final place
     return storeIndex

تابع pivot بخش اصلی الگوریتم میانه میانه‌هاست. این تابع ورودی (یک لیست به طول n) را به گروه‌هایی با پنج عضو تقسیم کرده و میانهٔ هر گروه را محاسبه می‌کند. سپس به صورت بازگشتی میانهٔ اصلی n/5 میانه‌های بدست آمده در قسمت قبل را بدست می‌آورد:

  function pivot(list, left, right)
     // for 5 or less elements just get median
     if right - left < 5:
         return partition5(list, left, right)
     // otherwise move the medians of five-element subgroups to the first n/5 positions
     for i from left to right in steps of 5
         // get the median of the i'th five-element subgroup
         subRight := i + 4
         if subRight > right:
             subRight := right

         median5 := partition5(list, i, subRight)
         swap list[median5] and list[left + floor((i - left)/5)]

     // compute the median of the n/5 medians-of-five
     return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10)

تابع partition5 میانهٔ یک گروه با حداکثر پنج عضو را انتخاب می‌کند. یک راه ساده برای پیاده‌سازی این تابع استفاده از مرتب‌سازی درجی است.

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

مرحله ۱: تمامی n عضو به گروه‌های ۵ تایی دسته بندی می‌شوند. (در صورتی که تعداد عضو‌ها به ۵ قابل قسمت نباشد گروه آخر کمتر از ۵ عضو را در خود جای می‌دهد.)

مرحله ۲: میانه هر یک از n/5 گروه‌های ایجاد شده پیدا می‌شوند. (ابتدا هر یک از این گروه ها در ${\displaystyle o(1)}$

مرحله ۳: به صورت بازگشتی میانه n/5 داده ها انتخاب می‌شود.

مرحله ۴: با استفاده از تابع پارتیشن که میانۀ انتخابی را به عنوان عنصر محوری در ورودی دریافت می‌کند، با فرض اینکه میانۀ انتخابی k امین کوچکترین عضو باشد، داده ها به دو دستۀ k - 1 تایی و n - k تایی تقسیم می‌شوند که تمامی اعضای آنها به ترتیب کوچکتر و بزرگتر از میانۀ انتخابی است.

مرحله ۵: در این مرحله ۳ حالت وجود دارد:

اگر اندیس میانۀ انتخابی برابر i باشد: این عضو به عنوان جواب بازگردانده می‌شود.

اگر اندیس میانۀ انتخابی بزرگتر از i باشد: i امین کوچکترین عضو در بین داده‌های کوچکتر از میانه به عنوان جواب بازگردانده می‌شود.

اگر اندیس میانۀ انتخابی کوچکتر از i باشد: i - k امین کوچکترین عضو در بین داده‌های بزرگتر از میانه به عنوان جواب بازگردانده می‌شود.

از n/۵ گروه‌ها، نیمی از آنها (n/۱۰=n/۵×½) میانه‌هایی کمتر از میانهٔ واقعی (میانه میانه‌ها) و نیمی دیگر از آنها میانه‌هایی بیشتر از آن دارند. در هر یک از n/۱۰ گروه‌ها با میانهٔ کمتر از میانهٔ واقعی، ۲ عضو کوچکتر از میانهٔ گروه خود هستند؛ بنابراین در n/۱۰ از گروه‌ها حداقل ۳ عضو کوچکتر از میانهٔ اصلی هستند. به صورت مشابه در n/۱۰ دیگر از گروه‌ها با میانهٔ بزرگتر از میانهٔ اصلی حداقل ۲ عضو وجود دارند که از میانهٔ گروه خود بزرگتر هستند و در نتیجه n/۱۰ از گروه‌ها دارای حداقل ۳ عضو بزرگتر از میانهٔ اصلی هستند؛ بنابراین میانهٔ اصلی حداقل از n/۱۰×۳ داده‌ها بیشتر و از n/۱۰×۳ آنها کمتر است؛ بنابراین میانهٔ انتخاب شده بین ۳۰٪ تا ۷۰٪ داده‌ها است:

عنصر قرمز رنگ: میانه میانه‌ها، عناصر خاکستری: اعداد کوچکتر از میانه میانه‌ها، عناصر سفید: عناصر بزرگتر از میانه میانه‌ها

۵ تایی‌های بالا برای وضوح بیشتر به صورت مرتب شده نمایش داده شده‌اند. اما در واقع، از آنجایی که ما تنها به دنبال میانهٔ این ۵ تایی‌ها هستیم مرتب بودن آنها اهمیتی ندارد.

توجه کنید که تمامی عناصر بالا-راست عنصر قرمز رنگ(۳۰٪ کل عناصر) کوچکتر از آن و تمامی عناصر پایین-چپ این عنصر(۳۰٪ کل عناصر)، بزرگتر از آن هستند.

همانطور که در تصویر بالا مشاهده می‌کنید، به جز گروهی که شامل میانۀ انتخابی (x) است و گروه آخر، در نیمی دیگر از گروه‌ها حداقل ۳ عضو وجود دارد که از x کوچکتر هستند. (این ۳ عضو شامل میانه‌های کوچکتر از x و دو عضو کوچکتر از هر میانه، در هر یک از n/5 گروه‌ها است) بنابراین:

به صورت مشابه حداقل 6 - 3n/10 عضو بزرگتر از x هستند. بنابراین مرحله‌ ۵ام حداکثر روی 6 + 3n/10 از داده‌ها بازگشت می‌کند. از طرفی، مراحل ۱، ۲ و ۴ برای اجرا شدن احتیاج به زمانی از ${\displaystyle O(n)}$

با در نظر گرفتن ${\displaystyle T(n)\le c\cdot n}$

در صورتی که جملۀ ${\displaystyle (-\frac{cn}{10}+7c+an)}$

• M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, "Time bounds for selection," J. Comput. System Sci. 7 (1973) 448-461.
• توماس اچ کورمن، Charles E. Leiserson, رونالد ریوست، and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp. 183–196. Section 14.1: Dynamic order statistics, pp. 302–308.

• "Lecture notes for January 30, 1996: Deterministic selection", ICS 161: Design and Analysis of Algorithms, David Eppstein