مرتب‌سازی شکیبانه

مرتب‌سازی شکیبانه

کلاس	مرتب سازی درجی
داده ساختار	آرایه
بدترین زمان اجرا	$O(n \cdot \log n)$

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

کارت بازی

بازی با یک دسته بر زده شده شروع می‌شود که $1, \ldots, n$ شماره گذاری شده‌است.ابتدا کارت‌ها 1 به 1 مقدار دهی و توزیع می‌شوند که البته این مقدار دهی و توزیع در کپه‌های متوالی و جدا از هم روی میز قرار دارد

• 1. در ابتدا هیچ کپه‌ای از کارت وجود ندارد و اولین کارت که مقدار دهی و توزیع می‌شود یک کپهٔ جدید به وجود می‌آورذ که تنها دارای یک کارت است.
     
  2. هر کارت جدید ممکن است در یکی از دسته های(کپه‌های) موجود قرار بگیرد که در هر کدام از این کپه‌ها کارت با مقدار بیشتر در آغاز قرار دارد. بنابر این با افزوده شدن پی در پی کارت‌ها، تعداد کارت‌های آن کپه یا همهٔ دسته‌های موجود افزایش پیدا می‌کند که در نتیجهٔ آن یک دسته جدید شکل می‌گیرد.
     
  3. وقتی که دیگر کارتی وجود ندارد باقی مانده‌ها را بررسی و محاسبه کنید.(پایان بازی)

یک مساله مهم و اساسی در این بازی به اتمام رساندن آن با کمترین تعداد کپه‌های ممکن است.

الگوریتم مرتب‌سازی

آرایه با یک روش مرتب سازی به عنوان ورودی مرتب سازی داده شده‌است. به این مساله به دید جمع آوری کارت بنگرید که باید با مرتب سازی آماری هر عنصر بر اساس نمایه (index) خود مرتب شود.
نکته:

• این بازی از مقدار واقعی کارت‌ها فقط برای مقایسه بین دو کارت استفاده می‌نماید که با این کار ارتباط هر دو عنصر دلخواه از آرایه بررسی می‌شود.
  

حال بازی مرتب سازی صبورانه را شبیه سازی کنید وهر کارت جدید را در چپ‌ترین کپه با رعایت قانون قرار دهید. در هر مرحله از این بازی با این استراتژی برچسب‌های (label) کارت‌های سر (top) از چپ به راست به طور صعودی هستند. حال توالی مرتب شده را بازیابی کنید و کارت با کمترین مقدار از سر ستون در هر مرحله جمع آوری کنید.

پیچیدگی

اگر تعداد کارت‌ها در محدودهٔ $1, \ldots, n$، باشد یک پیاده سازی کارآمد با $O(n \cdot \log \log n)$ در بدترین حالت برای قرار دادن کارت‌ها در کپه‌ها وجود دارد(که برای یک مرتب سازی کامل در بدترین حالت $O(n \cdot \log n)$ است و $O(1 \cdot n)$ ) فضا برای پشتیبانی ساختارها صرف می‌شود .با توجه به گفتهٔ van Emde Boas tree تعدادی از این گفته‌ها به حقیقت پیوسته است .وقتی که هیچ فرضی در مورد مقادیر نداریم استراتژی حریصانه Greedy algorithm در بدترین حالت در$O(n \cdot \log n)$ پیاده سازی می شود.
در حقیقت یک روش پیاده سازی آن این است که با یک آرایه ای از پشته‌ها که بوسیلهٔ مقادیر کارت‌های سر(top) مرتب شده اند کار می کنیم که در این روش برای وارد کردن کارت جدید(insert) می توان از جستجوی باینری استفاده کرد که در حالت بدبینانه دارای $O(1\cdot \log p)$ است که P در این جا تعداد کپه‌ها است.
برای کامل کردن مرتب سازی در بدترین حالت $O(n \cdot \log n)$ می شود.در هر مرحله کارتی که کمترین مقدار را در top‌های سمت چپ کپه مورد نظر دارد بازیابی می‌شود و بعد دوباره تعدادی از کارها باید انجام شود.پیدا کردن کارت بعدی بوسیلهٔ جستجوی آن در میان همهٔ top‌های کپه‌ها در هر مرحله انجام شود مثل wikibooks‌ها که در بهترین حالت $O(1 \cdot n^2 )$ . با وجود این وارد کردن اولین کپه در لیست کپه‌ها ی باقیمانده با مراجعه به کارت‌های مرتب شدهٔ سر (top) انجام شود که در هر مرحله هزینهٔ دارد که در کل با توجه بهn مرحله دارای پیچیدگی زمانی $O(n \cdot \log n)$ است.

الگوریتم برای پیدا کردن بزرگترین زیر دنبالهٔ صعودی

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

تاریخچه

با توجه به گفته یD. Aldous and P. Diaconis مرتب سازی صبورانه اولین الگوریتم بود برای محاسبه بزرگترین زیر دنباله صعودی که توسط Hammersley پیاده سازی شده است و بوسیله A.S.C. Ross وBob Floyd مقدمات الگوریتم پیاده سازی شد.

منابع

ویکی‌پدیا انگلیسی

PreciseCodevilleMerge

Longest increasing subsequences:from patience sorting to the Baik-Deift-Johansson theorem

C.L. Mallows. Patience sorting. Bull. Inst. Math. Appl., 9:216–224, 1973.