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

در علوم کامپیوتر، مرتب‌سازی جزئی حالت ساده‌شده‌ای از مسئله مرتب‌سازی است.

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

یک مثال رایج مرتب‌سازی جزئی محاسبه ۱۰۰ تای اول یک لیست می‌باشد.

در یک لیست مرتب شده جزئی، از نظر شماره خانهٔ آرایه، برای هر شماره خانه i از ۱ تا k، عنصر i ام در همان محلی که در لیست مرتب شده قرار می‌گیرد، قرار دارد: عنصر i از لیست مرتب شده جزئی، شامل آماره ترتیبی i از لیست ورودی است.

الگوریتم‌ها

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

در مرتب‌سازی جزئی ما نیاز به یک لیست مرتب شده از 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