ソートについて

//バブルソート
void BubbleSort(int Data[], int n)
{
	int BeginPlace, ComparePlace;
	//比較を始める位置を最初からn-1まで変えていく
	for(BeginPlace = 0;BeginPlace < n;BeginPlace++)
	{
		//n - BeginPlaceまで比較する
		for(ComparePlace = 1;ComparePlace < n - BeginPlace;ComparePlace++)
		{
			//右のほうが小さかったら交換する
			if(Data[ComparePlace - 1] > Data[ComparePlace])
			{
				Swap(&(Data[ComparePlace - 1]), &(Data[ComparePlace]));
			}
		}
	}

	return;
}
//バブルソート改良版
void BubbleSortImprovedVersion(int Data[], int n)
{
	int BeginPlace, ComparePlace, LastSwapPlace = n, Temp = n;
	//比較を始める位置を最初からn-1まで変えていく
	for(BeginPlace = 0;BeginPlace < n;BeginPlace++)
	{
		//最後に交換した場所まで比較する
		for(ComparePlace = 1;ComparePlace < LastSwapPlace;ComparePlace++)
		{
			//右のほうが小さかったら交換する
			if(Data[ComparePlace - 1] > Data[ComparePlace])
			{
				Swap(&(Data[ComparePlace - 1]), &(Data[ComparePlace]));
				//交換した場所を覚える
				Temp = ComparePlace;
			}
		}
		//最後に交換した場所を覚える
		LastSwapPlace = Temp;
	}
	return;
}

//シェーカーソート/双方向バブルソート
void ShakerSort(int *Data, int n)
{
	int ComparePlace, LastSwapPlace;
	int LeftBeginPlace, RightBeginPlace;

	LeftBeginPlace = 0;
	RightBeginPlace = n - 1;
	LastSwapPlace = n - 1;
	//比較を始める場所が交差するまで
	//左右から交互にソートを繰り返す
	while(LeftBeginPlace  < RightBeginPlace)
	{
		//右からのソートで最後に交換した場所から
		//左からのソートで最後に交換した場所まで
		//右側の要素と比較していく
		for(ComparePlace = LeftBeginPlace;ComparePlace < RightBeginPlace;ComparePlace++)
		{
			//右のほうが小さかったら交換する
			if(Data[ComparePlace] > Data[ComparePlace + 1])
			{
				Swap(&(Data[ComparePlace]), &(Data[ComparePlace + 1]));
				LastSwapPlace = ComparePlace;
			}
		}
		//次の右からのソートの開始位置を左からのソートで最後に交換した場所にする
		RightBeginPlace = LastSwapPlace;
		//左からのソートで最後に交換した場所から
		//右からのソートで最後に交換した場所まで
		//左側の要素と比較していく
		for(ComparePlace = RightBeginPlace;ComparePlace > LeftBeginPlace;ComparePlace--)
		{
			//左のほうが大きかったら交換する
			if(Data[ComparePlace - 1] > Data[ComparePlace])
			{
				Swap(&(Data[ComparePlace - 1]), &(Data[ComparePlace]));
				LastSwapPlace = ComparePlace;
			}
		}
		//次の左からのソートの開始位置を右からのソートで最後に交換した場所にする
		LeftBeginPlace = LastSwapPlace;
	}
	return;
}

//選択ソート/馬鹿ソート/セレクションソート
void SelectionSort(int Data[], int n)
{
	int BeginPlace, ComparePlace, min;
	//比較を始める位置を0番目から(n - 1)番目まで動かしていく
	for(BeginPlace = 0;BeginPlace < n;BeginPlace++)
	{
		min = BeginPlace;
		//最小の要素を探す
		for(ComparePlace = BeginPlace + 1;ComparePlace < n;ComparePlace++)
		{
			//今まで見つかった最小のものよりも
			//小さいものが見つかったら交換する
			if(Data[min] > Data[ComparePlace])
			{
				Swap(&(Data[min]), &(Data[ComparePlace]));
			}
		}
	}
	return;
}

//挿入ソート
void InsertionSort(int Data[], int n)
{
	int BeginPlace, ComparePlace;
	//比較を始める位置を1から順番にn - 1まで動かしていく
	for(BeginPlace = 1;BeginPlace < n;BeginPlace++)
	{
		//BeginPlace番目の要素から1番目の要素まで順番に左の要素と比較していく
		for(ComparePlace = BeginPlace;ComparePlace > 0;ComparePlace--)
		{
			//左のほうが大きかったら交換する
			if(Data[ComparePlace - 1] > Data[ComparePlace])
			{
				Swap(&(Data[ComparePlace - 1]), &(Data[ComparePlace]));
			}
		}
	}
}

//コムソート
void CombSort(int Data[], int n)
{
	int Gap, i;
	BOOL IsSwap;

	Gap = n;
	IsSwap = 1;
	//Gapが1より大きくてループの中で一回以上交換が行われている間
	while(Gap > 1 || IsSwap)
	{
		//1.3で割る
		Gap = (Gap * 10) / 13;
		//Gapが9か10なら収束するように11にする
                //これにより高速化が図れる
		if(Gap == 9 || Gap == 10)
		{
			Gap = 11;
		}
		IsSwap = 0;
		//間隔Gapでバブルソート
		for(i = 0;i < n - Gap;i++)
		{
			//右のほうが小さかったら交換する
			if(Data[i] > Data[i + Gap])
			{
				Swap(&(Data[i]), &(Data[i + Gap]));
				IsSwap = 1;
			}
		}
	}
	return;
}

//ヒープソート
void HeapSort(int Data[], int n)
{
	int Count, Son, Parent;
	int Number;//ヒープの要素数
	int *Heap;
	Heap = (int*)malloc(sizeof(int) * n);//ヒープに見立てた配列を作る
	Number = 0;//ヒープを空にする
	//Data[]から一つずつ順番に取り出して
	//根元に加えてヒープを作っていく
	for(Count = 0;Count < n;Count++)
	{
		Heap[Number] = Data[Count];//ヒープの一番後ろに加える
		Number++;//ヒープの要素数を一つ増やす
		Son = Number;//加えた要素を子とする
		Parent = Son / 2;//その親
		//入れ替えが起こらなくなるか、根元に到達するまで
		//加えた要素とその親とを比較していく
		while(Son > 1 && Heap[Son - 1] < Heap[Parent - 1])
		{
			//親のほうが大きかったら入れ替える
			Swap(&(Heap[Son - 1]), &(Heap[Parent - 1]));
			//一つ上に移る
			Son = Parent;//今回の親を次回の子にする
			Parent = Son / 2;//次回の親を決める
		}
	}
	//ツリーから要素を根元から順番に空になるまで
	//取り出していく
	for(Count = 0;Number > 0;Count++)
	{
		Data[Count] = Heap[0];//根元を取り出す
		Number--;//ヒープの要素数を一つ減らす
		Heap[0] = Heap[Number];//ヒープの最後の要素を根元に持ってくる
		Parent = 1;//根元を親とする
		Son = Parent * 2;//その子
		//入れ替えが起こらなくなるか、最後に到達するまで
		//親と二つの子の内小さいほうとを比較していく
		while(Son <= Number)//最後に到達していない間
		{
			//まだ次があって左の子の方が大きかったら
			if(Son + 1 <= Number && Heap[Son - 1] > Heap[Son])
			{
				Son++;//Sonを右の子にする
			}
			//子より親が大きかったら入れ替える
			if(Heap[Parent - 1] > Heap[Son - 1])
			{
				Swap(&(Heap[Parent - 1]), &(Heap[Son - 1]));
			}
			//一つ下に移る
			Parent = Son;//今回の子を次回の親にする
			Son = Parent * 2;//次回の子を決める
		}
	}
	free(Heap);//ヒープを削除する
	return;
}

//マージソート/併合ソート
void MergeSort(int Data[], int n)
{

	int Center, Left, Right, TempIndex;
	int *Temp;
	//要素が一つしかないならすでにソートされているのでそのまま戻る
	if(n == 1)
	{
		return;
	}
	//そうでなければ二つに分割してそれぞれをソートしてマージ(併合)する
	else
	{
		//二つに分けてそれぞれをソートする
		{
			Center = n / 2;
			MergeSort(Data, Center);
			MergeSort(Data + Center, n - Center);
		}
		//ソートされた二つの配列をマージ(併合)する
		{
			Left = Right = TempIndex = 0;
			Temp = (int*)malloc(sizeof(int) * n);
			//両方の配列にまだ比較していない要素がある間
			//両方の配列の同じ位置の要素の内小さいほうをTemp[]に入れていく
			while(Left < Center && Right < n - Center)
			{
				if(Data[Left] > (Data + Center)[Right])
				{
					Temp[TempIndex++] = (Data + Center)[Right++];
				}
				else
				{
					Temp[TempIndex++] = Data[Left++];
				}
			}
			//片方の配列を全て比較してしまったら
			//もう片方の配列の残りの要素を全てTemp[]に入れる
			{
				//左側の要素が余ったとき
				while(Left < Center)
				{
					Temp[TempIndex++] = Data[Left++];
				}
				//右側の要素が余ったとき
				while(Right < n - Center)
				{
					Temp[TempIndex++] = (Data + Center)[Right++];
				}
			}
			//Temp[]の要素をData[]に移す
			memcpy(Data, Temp, sizeof(int) * n);
			free(Temp);
		}
	}
	return;
}

//クイックソート
void QuickSort(int Data[], int n)
{
	int Pivot, LeftComparePlace, RightComparePlace;

	//要素が一つしかないならすでにソートされているのでそのまま戻る
	if(n == 1)
	{
		return;
	}
	//そうでなければ分割値を決めて分割以上と未満の二つの配列に分割して
	//それぞれをソートする
	else
	{
		//配列の中央の要素を分割値とする
		Pivot = Data[n / 2];
		LeftComparePlace = 0;
		RightComparePlace = n - 1;

		//分割値以上と未満の二つの配列に分割する
		for(;;)
		{
			//左から分割値以上の要素を探す
			while(Data[LeftComparePlace] < Pivot)
			{
				LeftComparePlace++;
			}
			//右から分割値未満の要素を探す
			while(Data[RightComparePlace] >	Pivot)
			{
				RightComparePlace--;
			}
			//探す場所場交差していたら分割を終える
			if(LeftComparePlace >= RightComparePlace)
			{
				break;
			}
			//見つかった二つの要素を交換する
			Swap(&(Data[LeftComparePlace]), &(Data[RightComparePlace]));
			//比較する場所を一つ進める
			LeftComparePlace++;
			RightComparePlace--;
		}
		//分割した二つの配列をそれぞれソートする
		QuickSort(Data, LeftComparePlace);
		QuickSort(Data + LeftComparePlace, n - LeftComparePlace);
	}
	return;
}

//バケツソート/バケットソート/分布数えソート/ビンソート
//要素の範囲 0〜n
void BucketSort(int Data[], int n)
{
	int BucketIndex, Count, PutPlace;
	int *Bucket;
	Bucket = (int*)malloc(sizeof(int) * n);//n個のバケットを作る
	//バケットを全て空にする
	for(BucketIndex = 0;BucketIndex < n;BucketIndex++)
	{
		Bucket[BucketIndex] = 0;
	}
	//順番に数えていく
	for(BucketIndex = 0;BucketIndex < n;BucketIndex++)
	{
		Bucket[Data[BucketIndex]]++;
	}
	//先頭のバケットからバケットに入っている数だけ
	//配列に入れていく
	PutPlace = 0;//入れる場所を先頭にしておく
	for(BucketIndex = 0;BucketIndex < n;BucketIndex++)//バケットの数だけ繰り返す
	{
		//バケットに入っている数だけ入れる
		for(Count = 0; Count < Bucket[BucketIndex];Count++)
		{
			Data[PutPlace + Count] = BucketIndex;
		}
		PutPlace += Bucket[BucketIndex];//入れる場所を入れた数だけ進める
	}
	free(Bucket);//バケットを削除する
	return;
}

//基数ソート/ラディックスソート
//要素の範囲 0〜n
void RadixSort(int Data[], int n)
{
	int *Temp;
	int Bucket[10];
	int Figure, Digit, Radix, Count;
	Temp = (int*)malloc(sizeof(int) * n);
	//桁数を求める
	Figure = (int)log10(n) + 1;

	//最下位から順番にバケットソートでソートしていく
	for(Digit = 0, Radix = 1;Digit < Figure;Digit++, Radix *= 10)
	{
		//Bucket[]を'0'で埋める
		for(Count = 0;Count < 10;Count++)
		{
			Bucket[Count] = 0;
		}
		//いくつあるか数える
		for(Count = 0;Count < n;Count++)
		{
			Bucket[((Data[Count] / Radix) % 10)]++;
		}

		//そのBucketの一つ前のBucketを加える
		for(Count = 1;Count < 10;Count++)
		{
			Bucket[Count] += Bucket[Count - 1];
		}
		//Dataの要素をTemp[]に入れていく
		for(Count = n - 1;Count >= 0;Count--)
		{
			Temp[--Bucket[((Data[Count] / Radix) % 10)]] = Data[Count];
		}
		//Temp[]の要素を全てData[]へ移す
		for(Count = 0;Count < n;Count++)
		{
			Data[Count] = Temp[Count];
		}
	}
	free(Temp);
	return;
}

//逆写像ソート
void MapSort(int Data[], int n)
{
	int Count, j, x;
	int *Index, *Temp, *OutPut;
	Index = (int*)malloc(sizeof(int) * n);
	Temp = (int*)malloc(sizeof(int) * n);
	OutPut = (int*)malloc(sizeof(int) * n);
	//-1で埋める
	for(Count = 0; Count < n; Count++)
	{
		Index[Count] = -1;
	}
	for(Count = n - 1;Count >= 0;Count--)
	{
		Temp[Count] = Index[Data[Count]];
		Index[Data[Count]] = Count;
	}
	j = 0;
	for(x = 0;x < n;x++)
	{
		Count = Index[x];
		while(Count >= 0)
		{
			OutPut[j] = Data[Count];
			j++;
			Count = Temp[Count];
		}
	}
	//OutPut[]の要素を全てData[]へ移す
	for(Count = 0;Count < n;Count++)
	{
		Data[Count] = OutPut[Count];
	}
	free(Index);
	free(Temp);
	free(OutPut);
	return;
}

//バイトニックソート
//2のn乗個以外でも動く
void BitonicSort(int Data[], int n)
{
	int Count, ComparePlace, BlockSize, Interval, TempSize, Power;
	int Direction;//昇順 = 1 降順 = -1
	int *Temp;
	int MaxNumber = n;
	int DataSize = n;
	int Block;

	//作業用配列の要素数をData[]の要素数以上で最小の2のn乗にする
	for(Count = 1, Power = 0;Count < n;Count *= 2)
	{
		Power++;
	}
	TempSize = (int)pow(2, Power);
	Temp = (int*)malloc(sizeof(int) * TempSize);//作業用の配列Temp[TempSize]を作る
	//作業用配列にデータを移す
	for(Count = 0;Count < n;Count++)
	{
		Temp[Count] = Data[Count];
	}
	//増えた部分に一番大きな数を入れていく
	for(Count = n;Count < TempSize;Count++)
	{
		Temp[Count] = MaxNumber;
	}
	//ブロックサイズを2からnまで大きくしていく
	for(BlockSize = 2;BlockSize <= n;BlockSize *= 2)
	{
		Direction = 1;//最初の向きを昇順にする
		n += n % BlockSize;//要素数をBlockSizeで割り切れるように増やす
		//ブロック(2のn乗)ごとにソートする
		for(Count = 0;Count < n / BlockSize;Count++)//ブロックの数だけ繰り返す
		{
			//BlockSize / 2から1まで間隔を半分に狭めながら並べ替える
			for(Interval = BlockSize / 2;Interval >= 1;Interval = Interval / 2)
			{
				//並べ替える
				for(ComparePlace = 0;ComparePlace + Interval < BlockSize;ComparePlace++)
				{
					//左か右が大きかったら交換する
					if(Temp[BlockSize * Count + ComparePlace] * Direction > Temp[BlockSize * Count + ComparePlace + Interval] * Direction)
					{
						Swap(&(Temp[BlockSize * Count + ComparePlace]), &(Temp[BlockSize * Count + ComparePlace + Interval]));
					}
					//同じ場所を比較しないようにする
					if(Interval == ComparePlace + 1)
					{
						ComparePlace+= Interval;
					}
				}
			}
			//1ブロックソートするごとに
			//ソートする向きを反転する
			Direction *= -1;
		}
	}
	//ソートしたデータをData[]に戻す
	for(Count = 0;Count < DataSize;Count++)
	{
		Data[Count] = Temp[Count];
	}
	free(Temp);//作業用配列を削除する
	return;
}