این کد با (O(n هست که داخل ویژوال استودیو و پیاده سازی std::nth_element وجودداره و میشه ازش برای پیدا کردن میانه استفاده کرد .
template<class _RanIt,
class _Pr> inline
void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
{ // order Nth element, using _Pred
for (; _ISORT_MAX < _Last - _First; )
{ // divide and conquer, ordering partition containing Nth
pair<_RanIt, _RanIt> _Mid =
_Unguarded_partition(_First, _Last, _Pred);
if (_Mid.second <= _Nth)
_First = _Mid.second;
else if (_Mid.first <= _Nth)
return; // Nth inside fat pivot, done
else
_Last = _Mid.first;
}
_Insertion_sort(_First, _Last, _Pred); // sort any remainder
}
نحوه کار:
ورودی :
-
اشاره گر به شروع آرایه _First
-
اشاره گر به عنصر n ام _Nth
-
اشاره گر به پایان آرایه _Last
خروجی :
-
عنصری از آرایه که از n عنصر بزرگ تر هست .
الگوریتم :
-
یک عنصر راندوم از بازه _First تا _Last انتخاب می کنیم .
-
عملیات پارتیشن رو بر روی این عنصر انجام میدیم (یعنی همه ی عناصر کوچک تر رو قبل از این عنصر قرار میدیم ( داخل این تاپیک هم کدش رو گذاشته بودم ))
-
محل جدید این عنصر رو _Mid میزاریم حالا 3 حالت ممکنه پیش میاد :
-
اگر محل _Mid از _Nth کمتر بود مرحله 1 رو دوباره از بازه _First تا _Mid تکرار می کنیم .
-
اگر محل _Mid از _Nth بیشتر بود مرحله 1 رو اینبار از بازه _Mid تا _Last تکرار می کنیم .
-
اگر _Mid با _Nth برابر بود یعنی میانه پیدا شده .
البته داخل پیاده ساز ی بالا برای سرعت بیشتر در صورتی که سایز آرایه کوچیک باشه (کمتر از 32 ) از insertation sort استفاده می کنه و عنصر n ام رو بعد از sort کردن بر می گردونه .(چون insertation sort بدلیل cache friendly بودن و cache prefetching برای سایز های کوچیک فوق العاده سریع هست )
این الگوریتم در حالت میانگین با (O(n میانه رو پیدا می کنه .