ソートのアルゴリズム

ちょっと分けあってソートについて調べています．

いやはや，奥が深いんですな．
僕は中の下程度の知識しか無いし，今更そんなもん必要じゃないだろと思って大した勉強をしたことが無いんですが．
これまでbubble, insertion, selection, quick, heap, shell, mergeのような，基本的なものしか知りませんでした．

例えばbubble sortひとつとっても，ソート済みのindexを記憶しておくことで探索範囲を徐々に縮めていく方法とか（名前無いの？），
片一方からのみソートしていくんじゃあバランス悪いから交互に攻めようとかいってshaker sortとかいうのがあったり．

しかし僕は頭が豆腐でできているため，本で読んだだけじゃあよく分かりません．
なのでコーディングします．

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

これが普通のバブルソート．セジウィック本とほぼ同じようなコードになってしまった.
templateになっているのはご愛嬌．

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

これが改良版バブルソート．おおー．こんないい方法があったのか．考えたことなかった．頭いいなぁ．

template<class T>
void Sort<T>::shaker_sort(T target[], int length)
{
	int top = 0, bottom = length-1, sorted = top;
	while(bottom > top)
	{
		for(int j=bottom; j>top; --j)
		{
			if(target[j-1] > target[j])
			{
				swap(target[j-1], target[j]);
				sorted = j-1;
			}
		}
		top = sorted;
		

		if(top == bottom){ break;}

		sorted = top;

		for(int j=top; j<bottom; ++j)
		{
			if(target[j] > target[j+1])
			{
				swap(target[j], target[j+1]);
				sorted = j+1;
			}
		}
		bottom = sorted;

		if(top == bottom){ break;}
	}
}

で，これが最終形態のシェーカーソート．前の2つに比べてコードが長いですが，単に左右左右とバブルソート（２つ目のほう）をしているだけです．
いやあ，すごいなぁ．バブルソートを材料に，こんなこと考える人いるのか．感心しますね．世の中にはあたまがいい人であふれてます．
ちなみに僕は情報科学系の学部を出たわけでないんで，アルゴリズムにしてもプログラミングにしても独学なんですね．
だからこういうことに触れる機会が，その道の人に比べて圧倒的に少なかったのです．

いいですよね，情報系の人は．こういうこと勉強すれば単位になるんですから（酷）
自分，何トチ狂ってヘンテコな学科に行っちゃったんだろうとか思います．ちょっと後悔してますが，よかったこともあるのでそれはそれで．

ちなみにコードは写経したわけでないので，うまく動くかは保障外です．あ，swapは単なる交換ですよ．
そんなこんなで貴重な日曜日は過ぎてゆくのだ．