Created
October 18, 2017 15:46
-
-
Save jacky860226/ccea3b5d21a0fab7c695f546ab128bc6 to your computer and use it in GitHub Desktop.
medians of medians
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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