/*
	ppps_int_sort.c
	[サンプルライブラリ] int型の各種ソートアルゴリズム
	
	author:  K.Y (Programming Place Plus)
	
	version 1.0.2   '2013/2/9
	                  ・ヒープソートの関数を追加。
	
	        1.0.1   '2013/1/26
	                  ・マージソートの関数を追加。
	
	        1.0.0   '2013/1/19
*/

#include "ppps_int_sort.h"
#include <stdlib.h>

#define SWAP(type,a,b)          { type work = a; a = b; b = work; }
#define MEDIAN3(x,y,z)   \
	(x < y)              \
	  ? (y < z)          \
	      ? (y)          \
	      : (z < x)      \
	          ? (x)      \
	          : (z)      \
	  : (z < y)          \
	      ? (y)          \
	      : (x < z)      \
	          ? (x)      \
	          : (z)
#define MIN(a, b)  (a < b) ? (a) : (b)


/* ヒープ */
struct Heap_tag {
	int*   data;           /* データ本体 */
	int    capacity;       /* 最大容量 */
	int    first_empty;    /* 空になっている最初の位置 */
};
typedef struct Heap_tag Heap;


static void quick_sort_rec(int* array, int begin, int end);
static int select_pivot(int* array, int begin, int end);
static void merge_sort_rec(int* array, int begin, int end, int* work);
static void merge(int* array, int begin, int end, int mid, int* work);
static void merge_sort_bottomup(int* array, int begin, int end, int* work);
static void init_heap(Heap* heap, int* array, size_t size);
static void down_heap(Heap* heap, int root, int end);
static void sort_heap(Heap* heap);


/*
	単純ソート (昇順)
*/
void ppps_simple_sort(int* array, size_t size)
{
	size_t i, j;

	for(i = 0; i < size - 1; ++i){
		for(j = i + 1; j < size; ++j){
			if(array[i] > array[j]){
				SWAP(int, array[i], array[j]);
			}
		}
	}
}

/*
	選択ソート (昇順)
*/
void ppps_selection_sort(int* array, size_t size)
{
	size_t i, j;
	int min_index;

	for(i = 0; i < size - 1; ++i){
		min_index = i;
		for(j = i + 1; j < size; ++j){
			if(array[min_index] > array[j]){
				min_index = j;
			}
		}
		SWAP(int, array[i], array[min_index]);
	}
}

/*
	バブルソート (昇順)
*/
void ppps_bubble_sort(int* array, size_t size)
{
	size_t i, j;

	for( i = 0; i < size - 1; ++i ){
		for( j = 1; j < size - i; ++j ){
			if( array[j-1] > array[j] ){
				SWAP(int, array[j-1], array[j]);
			}
		}
	}
}

/*
	挿入ソート (昇順)
*/
void ppps_insertion_sort(int* array, size_t size)
{
	size_t i, j;
	int tmp;

	for( i = 1; i < size; ++i ){
		tmp = array[i];
		for( j = i; j > 0 && array[j-1] > tmp; --j ){
			array[j] = array[j-1];
		}
		array[j] = tmp;
	}
}

/*
	改良版挿入ソート (昇順)
*/
void ppps_insertion_sort_ex(int* array, size_t size)
{
	size_t i, j;
	int tmp;

	for( i = 1; i < size; ++i ){
		tmp = array[i];

		if( array[i-1] > tmp ){  /* 挿入が必要か先に調べる */
			j = i;

			/* 初回の j > 0 は必ず真(i=1; であり j=i; をしたのだから) であるし、
			   array[j-1] > tmp も先ほどチェックしたところなので、
			   do-while文にして条件判定を後に回す方が効率的。
			   for( j = i; j > 0 && array[j-1] > tmp; --j ); としていることはまったく同じで、
			   単に do-while文に書き換えただけ。
			*/
			do {
				array[j] = array[j-1];
				--j;
			} while( j > 0 && array[j-1] > tmp );

			array[j] = tmp;  /* ここで行えば、挿入が不要ならば通過しなくて済む */
		}
	}
}

/*
	二分挿入ソート (昇順)
*/
void ppps_binary_insertion_sort(int* array, size_t size)
{
	size_t i, j;
	int tmp;
	size_t lower, upper, mid;

	for( i = 1; i < size; ++i ){
		tmp = array[i];

		/* 挿入位置を二分探索で探す */

		lower = 0;
		upper = i;
		while( lower < upper ){
			mid = (lower + upper) / 2;

			if( array[mid] < tmp ){
				lower = mid + 1;
			}
			else{
				upper = mid;
			}
		}

		/* 発見した挿入位置へ挿入 */
		for( j = i; j > lower; --j ){
			array[j] = array[j-1];
		}
		array[j] = tmp;
	}
}

/*
	改良版二分挿入ソート (昇順)
*/
void ppps_binary_insertion_sort_ex(int* array, size_t size)
{
	size_t i, j;
	int tmp;
	size_t lower, upper, mid;

	for( i = 1; i < size; ++i ){
		tmp = array[i];

		if( array[i-1] > tmp ){  /* 挿入が必要か先に調べる */
			/* 挿入位置を二分探索で探す */

			lower = 0;
			upper = i;
			while( lower < upper ){
				mid = (lower + upper) / 2;

				if( array[mid] < tmp ){
					lower = mid + 1;
				}
				else{
					upper = mid;
				}
			}

			/* 発見した挿入位置へ挿入 */
			for( j = i; j > lower; --j ){
				array[j] = array[j-1];
			}
			array[j] = tmp;
		}
	}
}

/*
	シェルソート (昇順)
*/
void ppps_shell_sort(int* array, size_t size)
{
	size_t i, j;
	size_t h, h_tmp;
	int tmp;


	/* 最初の間隔 h を決める */
	/* 1,4,13,40,121... のように、1 から始めて h=h*3+1 を満たす値を使う。
	   これらの値の中で、size / 9 を超えない一番大きい値を最初の h とする。*/
	h = 1;
	for( h_tmp = 1; h_tmp < size / 9; h_tmp = h_tmp * 3 + 1 ){
		h = h_tmp;
	}

	while( h > 0 ){
		for( i = h; i < size; ++i ){
			tmp = array[i];
			for( j = i; j >= h && array[j-h] > tmp; j -= h ){
				array[j] = array[j-h];
			}
			array[j] = tmp;
		}
		h /= 3;  /* 間隔を縮める */
	}
}

/*
	クイックソート (昇順)
*/
void ppps_quick_sort(int* array, size_t size)
{
	/* 配列全体を対象にする */
	quick_sort_rec( array, 0, size - 1 );
}

/*
	非再帰版クイックソート (昇順)
*/
void ppps_quick_sort_no_recursive(int* array, size_t size)
{
	#define STACK_SIZE  (sizeof(int) * 8 * 2)  /* 必要なスタックサイズ。最後の * 2 は、２つの値をセットで格納するため */

	int begin = 0;
	int end = size - 1;
	int pivot, i, j;
	int stack[STACK_SIZE];
	int sp = 0;
	
	stack[sp++] = begin;
	stack[sp++] = end;

	/* スタックが空になるまで繰り返す */
	while( sp > 0 ){

		/* 範囲の情報をスタックから取り出す */
		/* スタックは後入れ先出しの構造なので、積んだときとは逆の順序で取り出さなければならない点に注意 */
		end = stack[--sp];
		begin = stack[--sp];

		while( 1 ){

			/* 範囲が逆転していたら何もすることはない */
			if( begin >= end ){
				break;
			}
			
			pivot = select_pivot( array, begin, end );
			i = begin;
			j = end;

			while( 1 ){
				while( array[i] < pivot ){ ++i; }  /* 基準値以上の値が見つかるまで右方向へ進めていく */
				while( array[j] > pivot ){ --j; }  /* 基準値以下の値が見つかるまで左方向へ進めていく */

				if( i >= j ){ break; }  /* 左右から進めてきたiとjがぶつかったらループを終える */
		
				/* 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
				   基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
				   位置関係を交換する。
				*/
				SWAP( int, array[i], array[j] );
				
				/* 次回に備えて、注目点をずらす */
				i++;
				j--;
			}
		
			/* 左右の配列のうち、要素数が少ない方を先に処理する
			 後で処理する側は、その範囲をスタックへ積んでおく */
			if( i - begin < end - j ){
				/* 左側の配列を次のソート処理の対象にする */
				stack[sp++] = j + 1;
				stack[sp++] = end;
				end = i - 1;
			}
			else{
				/* 右側の配列を次のソート処理の対象にする */
				stack[sp++] = begin;
				stack[sp++] = i - 1;
				begin = j + 1;
			}
		}
	}

	#undef STACK_SIZE
}

/*
	クイックソート (再帰部分、昇順)
*/
void quick_sort_rec(int* array, int begin, int end)
{
	int pivot = select_pivot( array, begin, end );
	int i = begin;
	int j = end;

	while( 1 ){
		while( array[i] < pivot ){ ++i; }  /* 基準値以上の値が見つかるまで右方向へ進めていく */
		while( array[j] > pivot ){ --j; }  /* 基準値以下の値が見つかるまで左方向へ進めていく */

		if( i >= j ){ break; }  /* 左右から進めてきたiとjがぶつかったらループを終える */
		
		/* 基準値位置よりも左側にあり、基準値よりも大きい値 (array[i]) と、
		   基準値位置よりも右側にあり、基準値よりも小さい値 (array[j]) の
		   位置関係を交換する。
		*/
		SWAP( int, array[i], array[j] );
		
		/* 次回に備えて、注目点をずらす */
		i++;
		j--;
	}


	/* 基準値の位置より左側に要素が２つ以上あれば、その部分についてクイックソートを再帰させる */
	if( i - begin >= 2 ){
		quick_sort_rec( array, begin, i - 1 );
	}

	/* 基準値の位置より右側に要素が２つ以上あれば、その部分についてクイックソートを再帰させる */
	if( end - j >= 2 ){
		quick_sort_rec( array, j + 1, end );
	}
}

/*
	基準値を選ぶ
*/
int select_pivot(int* array, int begin, int end)
{
	return MEDIAN3(array[begin], array[(begin + end) / 2], array[end-1]);  /* 中央値を基準値とする */
}


/*
	マージソート (昇順)
*/
void ppps_merge_sort(int* array, size_t size)
{
	int* work;

	/* 作業用領域を確保 */
	work = malloc( sizeof(int) * size );
	
	/* 配列全体を対象にする */
	merge_sort_rec( array, 0, size - 1, work );

	free( work );
}

/*
	マージソート (再帰部分、昇順)
*/
void merge_sort_rec(int* array, int begin, int end, int* work)
{
	int mid;

	/* 要素が１つしかなければ終了 */
	if( begin >= end ){
		return;
	}


	/* ２つのデータ列に分割して、それぞれを再帰的に処理 */
	mid = (begin + end) / 2;
	merge_sort_rec( array, begin, mid, work );
	merge_sort_rec( array, mid + 1, end, work );

	/* マージ */
	merge( array, begin, end, mid, work );
}

/*
	マージ
*/
void merge(int* array, int begin, int end, int mid, int* work)
{
	int i, j, k;

	/* 前半の要素を作業用配列へ */
	for( i = begin; i <= end; ++i){
		work[i] = array[i];
	}

	/* 後半の要素を逆順に作業用配列へ */
	for( i = mid + 1, j = end; i <= end; ++i, --j){
		work[i] = array[j];
	}

	/* 作業用配列の両端から取り出した要素をマージ */
	i = begin;
	j = end;
	for( k = begin; k <= end; ++k) {
		/* 昇順にソートするので、小さい方の要素を結果の配列へ移す。 */
		if( work[i] <= work[j] ){ /* == の場合は先頭を優先すると安定なソートになる */
			array[k] = work[i];
			++i;
		}
		else{
			array[k] = work[j];
			--j;
		}
	}
}

/*
	非再帰版マージソート (昇順)
*/
void ppps_merge_sort_no_recursive(int* array, size_t size)
{
	int* work;

	/* 作業用領域を確保 */
	work = malloc( sizeof(int) * size );
	
	/* 配列全体を対象にする */
	merge_sort_bottomup( array, 0, size - 1, work );

	free( work );
}

/*
	非再帰版マージソート (昇順)
*/
void merge_sort_bottomup(int* array, int begin, int end, int* work)
{
    int i, j;

	for( i = 1; i <= end - begin; i *= 2 ){
		for( j = begin; j <= end - i; j += i * 2 ){
			merge( array, j, MIN(j + i * 2 - 1, end), j + i - 1, work);
		}
	}
}


/*
	ヒープソート（昇順）
*/
void ppps_heap_sort(int* array, size_t size)
{
	Heap heap;

	init_heap( &heap, array, size );
	sort_heap( &heap );
}

/*
	ヒープを初期化
*/
void init_heap(Heap* heap, int* array, size_t size)
{
	int root;

	heap->data = array;
	heap->capacity = size - 1;
	heap->first_empty = size;

	/* ヒープを再構成 */
	for( root = size / 2; root > 0; --root) {
		down_heap( heap, root, heap->first_empty - 1 );
	}
}

/* ヒープの指定要素を適切な位置まで沈める */
void down_heap(Heap* heap, int root, int end)
{
	while( root * 2 <= end ){
		int child = root * 2;  /* 左の子の位置 */

		/* ２つの子があるなら、小さい方を使う */
		/* 右の子の添字は、左の子の添字 + 1 である */
		if( child + 1 <= end ){
			if( heap->data[child] > heap->data[child + 1] ){
				child = child + 1;
			}
		}

		/* 子との大小関係が逆なら、入れ替える */
		if( heap->data[child] < heap->data[root] ){
			SWAP( int, heap->data[child], heap->data[root] );
			root = child;
		}
		else {
			break;
		}
	}
}

/* ヒープ内をソートする */
void sort_heap(Heap* heap)
{
	int end = heap->first_empty - 1;

	while( end > 0 ){
		SWAP(int, heap->data[1], heap->data[end]);
		end--;
		down_heap( heap, 1, end );
	}
}