ソートのアルゴリズムおまけ

まあ要は必要になったから，勉強がてらソートのアルゴリズムを実装しまくっているんですね．
というわけでおまけ．

template<class T>
void Sort<T>::insertion_sort(T target[], int length)
{
	T key = 0;

	for(int i=1; i<length; ++i)
	{
		key = target[i];
		int j=i-1;

		while(j>=0 && target[j] > key)
		{
			target[j+1] = target[j--];
		}
		target[j+1] = key;
	}
}

template<class T>
void Sort<T>::shell_sort(T target[], int length, int distance)
{
	T key;

	while(distance > 0)
	{
		for(int i=distance; i<length; ++i)
		{
			key = target[i];
			int j=i;
			while(j>=distance && target[j-distance] > target[j])
			{
				swap(target[j], target[j-distance]);
				j-=distance;
			}
		}
		distance/=2;
	}
}



template<class T>
void Sort<T>::selection_sort(T target[], int length)
{
	for(int i=0, min; i<length-1; ++i)
	{
		min = i;
		for(int j=i+1; j<length; ++j)	
		{
			if(target[min] > target[j] )
			{
				min = j;
			}
		}
		swap(target[i], target[min]);
	}
}

何の変哲も無い挿入ソートと選択ソート．
あとシェルソート．シェルソートって挿入ソートの改良版だったんですね．知らなかった．
このアルゴリズムってなんだか直感に反して効率的といわれているので，なんでやねん！とか思ってたのですが，
挿入ソートを効率よくするために…とか言われると分かる気がします．

相変わらず動作保障は無いです．要素20の配列で動いたよ，程度．

ネットを徘徊していると，3-wayのquick sortの実装って余り見当たりませんな．
前にJavaで実装したものがあるので，気が向いたらn-wayにしてここに張ります．