シェルソート
本日のアルゴリズムは【シェルソート】になります。
別名改良挿入ソートとも呼ばれるソートアルゴリズムですが、基本的な部分は挿入ソートと同じです。
挿入ソートでは「ほぼ整列したデータに対しては高速」という特徴がありましたのでシェルソートでは大雑把にソートをあらかじめ行うことで挿入ソートを高速に行うソート方式です。
#include
/*定数の定義*/
#define ARRAY_DATA 10
/*関数のプロトタイプ宣言*/
void ShellSort( int *array, int array_length );
void main()
{
int array[ARRAY_DATA] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int i;
/*シェルソートを行う*/
ShellSort( array, ARRAY_DATA );
for( i = 0; i < ARRAY_DATA; i++ ) {
printf( "%d\n", array[i] );
}
}
void ShellSort( int *array, int array_length )
{
int gap;
int i;
int j;
int w;
for( gap = array_length / 2; gap > 0; gap /= 2 ) {
for( i = gap; i < array_length; i++ ) {
for( j = i - gap; j >= 0; j -= gap ) {
if( array[j] <= array[ j + gap ] ) {
break;
}else{
w = array[i];
array[i] = array[j+gap];
array[j+gap] = w;
}
}
}
}
}