/* 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 #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 は、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--; } /* 基準値の位置より左側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */ if( i - begin >= 2 ){ quick_sort_rec( array, begin, i - 1 ); } /* 基準値の位置より右側に要素が2つ以上あれば、その部分についてクイックソートを再帰させる */ 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; /* 要素が1つしかなければ終了 */ if( begin >= end ){ return; } /* 2つのデータ列に分割して、それぞれを再帰的に処理 */ 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; /* 左の子の位置 */ /* 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 ); } }