مرتب‌سازی جزئی

الگوریتم بر مبنای انتخاب قسمت بندی

در مرتب‌سازی جزئی ما نیاز به یک لیست مرتب شده از k عنصر کوچکتر داریم. در نگاه ساده‌تر ما ابتدا نیاز داریم که این kعنصر را داشته باشیم، سپس آنها را مرتب کنیم. قسمت اول یعنی پیدا کردن k عنصر کوچکتر، معادل انتخاب قسمت بندی است. پس برای مرتب‌سازی جزئی، از این روش باید O(n) برای قسمت بندی و O(k log k) برای مرتب‌سازی سریع k عنصر، هزینه کنیم که در مجموع برابر O(n + k log k) می‌باشد. یک انتخاب خوب و رایج برای اجرای این الگوریتم ترکیب کردن روش‌های انتخاب سریع و مرتب‌سازی سریع می‌باشد که گاهی این روش را “quickselsort” نیز می‌نامند.

الگوریتم بر مبنای هرم

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

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

این الگوریتم بهینه تر از الگوریتم‌های قبلی است. این الگوریتم بر اساس مرتب‌سازی سریع و مرتب‌سازی ادغامیمی‌باشد. در مرتب‌سازی سریع، دیگر نیازی به قسمت بازگشتی مرتب بر اساس قسمت بندی نیست. یعنی زمانی که قسمت بندی در موقعیت k یا بعد از آن قرار گیرد، ما تنها بر روی قسمت چپ بازگشتی می‌زنیم.

 function partial_quicksort(A, i, j, k)
 if i <j
 p ← pivot(A, i, j)
 p ← partition(A, i, j, p)
 partial_quicksort(A, i, p-1, k)
 if p <k-1
 partial_quicksort(A, p+1, j, k)

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

• زبان برنامه‌نویسی سی++ : std::partial_sort
• زبان برنامه‌نویسی پایتون : nlargest و nsmallest