Skip to content

Instantly share code, notes, and snippets.

@jacky860226
Created October 18, 2017 15:46
Show Gist options
  • Save jacky860226/ccea3b5d21a0fab7c695f546ab128bc6 to your computer and use it in GitHub Desktop.
Save jacky860226/ccea3b5d21a0fab7c695f546ab128bc6 to your computer and use it in GitHub Desktop.
medians of medians
#include<algorithm>
template<typename IT,typename CMP>
inline IT find_mid(const IT first,const IT last,CMP cmp){
std::sort(first,last,cmp);
return first+(last-first)/2;
}
template<typename IT,typename CMP>
inline IT partition(IT first,IT last,IT pivot,CMP cmp){
if(last-first<1)return pivot;
std::iter_swap(--last,pivot);
pivot=last;
for(;;){
while(cmp(*first,*pivot))++first;
--last;
while(cmp(*pivot,*last))--last;
if(!(first<last)){
std::iter_swap(first,pivot);
return first;
}
std::iter_swap(first,last);
++first;
}
}
template<typename IT,typename CMP>
IT kth(const IT first,const IT last,int k,CMP cmp){
if(k==0||k>last-first) return last;
IT mid_e=first,i=first;
for(;i+5<last;i+=5){
std::iter_swap(mid_e++,find_mid(i,i+5,cmp));
}
std::iter_swap(mid_e++,find_mid(i,last,cmp));
int five_mid=mid_e-first;
mid_e=(five_mid==1)?first:kth(first,mid_e,five_mid/2,cmp);
IT pos=partition(first,last,mid_e,cmp);
if(pos-first==k-1) return pos;
if(pos-first<k) return kth(pos+1,last,k-(pos-first+1),cmp);
return kth(first,pos,k,cmp);
}
template<typename IT,typename CMP>
void SM_sort(IT first,IT last,CMP cmp){ // 幫他寫了一個sort做測試
if(last-first<=1)return;
IT mid=kth(first,last,(last-first)/2,cmp);
SM_sort(first,mid,cmp);
SM_sort(mid+1,last,cmp);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment