برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: در مرتب‌سازی جزئی ما نیاز به یک لیست مرتب شده از 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 یا بعد از آن قرار گیرد، ما تنها بر روی قسمت چپ بازگشتی می‌زنیم. این الگوریتم مرتب‌سازی سریع جزئی نیز نامیده می‌شود و تنها به o (n + k log k) زمان نیاز دارد، و در عمل نسبتا بهینه می‌باشد. به خصوص اگر هنگامی‌که k در مقایسه با n کوچک باشد، برای انتخاب پایه از مرتب‌سازی انتخابی استفاده شود. با این حال در بدترین حالت، که مربوط به انتخاب پایه بد است، هم پیچیدگی زمان رخ می‌دهد و زمان آن بسیار بد است. 
برداشت:
در علوم کامپیوتر ، مرتب‌سازی جزئی حالت ساده‌شده‌ای از مسئله مرتب‌سازی است . مرتب‌سازی عبارتست از مسئله بازگرداندن یک لیست از عناصر به طوری که عناصر آن همه مرتب شده‌اند ، در حالی که مرتب‌سازی جزئی عبارتست از بازگرداند یک لیست از k تا از کوچکترین عناصر (یا k تا از بزرگترین عناصر) که به ترتیب قرار گرفته‌اند . عناصر دیگر (عناصر بزرگتر از k تا عنصر ابتدایی) نیز ممکن است ذخیره بشوند ، یا ممکن است در نظر گرفته نشودند . یک مثال رایج مرتب‌سازی جزئی محاسبه ۱۰۰ تای اول یک لیست می‌باشد .