[ Median-of-Medians Algorithm ] 中位數演算法

這是一個可以在保證線性時間(c++ std::nth_element是隨機演算法)找出一個序列中第k大元素的演算法，網路上已經有不少教學，但是很多人都認為常數太大因此缺乏實作。

教學文在此：http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median

其實我高中時就想要試著去時做看看，但是因為那時的程式能力太差的關係，做出來的東西一直有bug，後來去忙其他事情後就被我忘掉了。最近因為學長面試有被問到一樣的問題跑來問我，才慢慢想起來有一份沒寫完的code，於是今天抱著不管怎樣都要寫出來的精神把他寫完了：

	#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);
	}

view raw kth.cpp hosted with ❤ by GitHub

	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);
	}

view raw SM_sort.cpp hosted with ❤ by GitHub

[ C++ std::sort python implement ] C++std::sort Python實作

最近有一個很靠北的課需要用python寫一些C++很容易做到的東西。
這次我們被要求寫一個quick sort，但是他要求的做法實在太糟糕了，於是我就參考了C++ std::sort來實做了一個quick sort(不包含heap sort的部分)：

	import random
	def quick_sort_implace(s):
	'''C++ std::sort implement without heap_sort'''
	first=0
	last=len(s)
	if(first!=last):
	__introsort_loop(s,first,last)
	__final_insertion_sort(s,first,last)
	def __final_insertion_sort(s,first,last):
	if(last-first>16):
	__insertion_sort(s,first,first+16)
	__unguarded_insertion_sort(s,first+16,last);
	else:
	__insertion_sort(s,first,last)
	def __insertion_sort(s,first,last):
	if(first==last):
	return
	for i in range(first+1,last):
	if(s[i]<s[first]):
	val=s[i]
	copy_backward(s,first,i,i+1)
	s[first]=val
	else:
	__unguarded_linear_insert(s,i)
	def copy_backward(s,first,last,result):
	while(first!=last):
	result-=1
	last-=1
	s[result]=s[last]
	return result
	def __unguarded_insertion_sort(s,first,last):
	for i in range(first,last):
	__unguarded_linear_insert(s,i)
	def __unguarded_linear_insert(s,last):
	val=s[last]
	__next=last
	__next-=1
	while(val<s[__next]):
	s[last]=s[__next]
	last=__next
	__next-=1
	s[last]=val
	def __introsort_loop(s,first,last):
	while(last-first>16):
	cut=__unguarded_partition_pivot(s,first,last)
	__introsort_loop(s,cut,last)
	last=cut
	def __unguarded_partition_pivot(s,first,last):
	mid=random.randint(first,last-1)
	__move_median_first(s,first,mid,last-1)
	return __unguarded_partition(s,first+1,last,s[first])
	def __move_median_first(s,a,b,c):
	if(s[a]<s[b]):
	if(s[b]<s[c]):
	s[a],s[b]=s[b],s[a]
	elif(s[a]<s[c]):
	s[a],s[c]=s[c],s[a]
	elif(s[a]<s[c]):
	return
	elif(s[b]<s[c]):
	s[a],s[c]=s[c],s[a]
	else:
	s[a],s[b]=s[b],s[a]
	def __unguarded_partition(s,first,last,pivot):
	while(True):
	while(s[first]<pivot):
	first+=1
	last-=1
	while(pivot<s[last]):
	last-=1
	if(not(first<last)):
	return first
	s[first],s[last]=s[last],s[first]
	first+=1
	# 以下為測試程式的部分
	def is_sorted(s):
	'''檢測序列s是否已排序'''
	n=len(s)
	i=1
	while(i<n):
	if(s[i]<s[i-1]):
	return False
	i+=1
	return True
	if __name__ == '__main__':
	import time
	s=[3 for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)
	s=[random.randint(0,1000000) for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)
	s=[random.randint(0,100) for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)
	s=[n for n in range(1000000)]
	start=time.time()
	quick_sort_implace(s)
	end=time.time()
	print(is_sorted(s),end-start)

view raw quick_sort.py hosted with ❤ by GitHub