シェルソート – 定義

 ギャップ:= 701 ;隙間の間 (リスト) doギャップ:=ラウンド(ギャップ* 2.3 ) ; 

 ギャップ:=ラウンド(ギャップ/ 2.3 ) ;

 PROCEDURE Tri_Shell(N As Int, ByRef E() As Int) Local Int D, LIMIT, INTERVERSION, J, ID = Div(N, 2) ' D = 比較距離Do ' 距離の細分化のメインループLIMIT = Sub ( N , D) ' 比較を制限または停止しますDo ' 介入の場合の二次再比較ループINTERVERSION = 0 ' 事前に反転なし (=0) J = D ' J%= 比較の 2 番目の要素の番号For I = 1 To LIMIT% ' I%=1番目の比較要素でLOOPをソートInc J ' J%は距離を保ちながらI%をたどる D% If E(I) > E(J) ' 反転に該当する場合INTERVERSION = I ' の位置を記憶します相互変換Swap E(I), E(J) ' 2 つの要素を反転しますEndIf Next I% LIMIT = INTERVERSION ' 次のソート ループは最後の 1 つの相互変換で停止しますLoop While INTERVERSION > 0 ' 要素の順序が同じであれば比較を繰り返します要素が変更されましたDiv D, 2 ' それ以外の場合は、距離を 2 で割って再度ループを開始します。距離を減らすことができなくなった場合を除き、D > 0 をループします。 Return

/* *指定された区切りで挿入ソートを実行します。 * ギャップ == 1 の場合、通常のソートを実行します。 * ギャップ >= 長さの場合は何もしません。 */ void shellSortPhase ( int a [ ] , int length , int gap ) { int i ; for ( i =ギャップ; i <長さ; ++ i ) { int値= a [ i ] ; int j ; for ( j = i -ギャップ; j >= 0 && a [ j ] >値; j -=ギャップ) { a [ j +ギャップ] = a [ j ] ; a [ j +ギャップ] =値; } } voidshellSort ( int a [ ] , size_t length ) { /* * ギャップ[] は幾何級数に近似する必要があります。 * 次のシーケンスは、 * 平均比較数の観点から最もよく知られています。参照: * http://www.research.att.com/~njas/sequences/A102549 */ static const int sinners [ ] = { 1 , 4 , 10 , 23 , 57 , 132 , 301 , 701 } ; intサイズインデックス; for ( sizeIndex = sizeof ( gaps ) / sizeof ( gaps [ 0 ] ) - 1 ; sizeIndex >= 0 ; --sizeIndex ) shellSortPhase ( a , length , Gaps [ sizeIndex ] ) ; }

/*演算子'=='、'<'、および '>' が定義されているあらゆる種類のデータに適応できるテンプレートを使用して、前のコードを C++ で再適応します。 */ template < typename T > void SHELLSRT_phase ( T * a, unsigned int size, unsigned int gap ) { for ( int i = gap ; i < ( int ) size ; ++ i ) { T value = a [ i ] ; int tmp = i-ギャップ; int j = 0 ; for ( j = tmp ; ( ( j >= 0 ) && ( a [ j ] > value ) ) ; j - =ギャップ) a [ j +ギャップ] = a [ j ] ; a [ j +ギャップ] =値; } } template < typename T > void SHELLSRT_make ( T * a, unsigned int size ) { static const unsigned int Cabinet [ 9 ] = { 1, 4, 10, 23, 57, 132, 301, 701, 1750 } ; unsigned int tmp = 9 - 1 ; for ( unsigned int i = tmp ; i ! = - 1 ; -- i ) SHELLSRT_phase ( a, サイズ, ギャップ[ i ] ) ; }

プロシージャTriShell ( n :整数;変数:タブ) ; var p 、 k 、 i 、 j 、 x :整数; begin (* * の結果である最適なギャップを検索します) (* 繰り返しシーケンス: Un = 3.Un-1 + 1 *) (* Un < n (配列要素数) であるように *) p : = 0 ; while ( p < n ) do p := 3 * p + 1 ; while ( p <> 1 ) do begin (* ギャップを徐々に調整します*) (* ギャップ = 1 ==> 通常の挿入ソート *) p := p div 3 ; if ( p = 1 ) then x := 1 else x := n - ( n mod p ) + 1 ; for i := x to n do begin k := t [ i ] ; (* 挿入する値 *) (* 挿入位置の検索 *) j := i; while ( j > = p )と( t [ j - p ] > k )はt [ j ] := t [ j - p ] ;から始まります。 j := j - p;終わり; (* 値をその位置に挿入 *) t [ j ] := k;終わり;終わり;終わり;

public static void sortOfShell ( int [ ] tab, intlogicalsize ) { int step = 1 ; while (ステップ< LogicalSize / 9 ) {ステップ=ステップ* 3 + 1 ; // 最初のステップを修正します} while ( step > 0 ) { // さまざまなステップでループしますfor ( int series = 0 ; series <= step - 1 ; series ++ ) { // シリーズでループしますint PositionEltAInsert =シリーズ+ステップ; // 挿入順に並べ替えwhile ( eltAInsertposition < logicalsize ) { int elementAInsert = tab [ eltAInsertposition ] ; int posElem Compare = PositionEltAInsert -ステップ; while ( ( posElem Compare >= 0 ) && ( elementAInsert < tab [ posElem Compare ] ) ) { tab [ posElem Compare + steps ] = tab [ posElem Compare ] ; posElem Compare -= ではありません。タブ[ posElem Compare +ステップ] = elementAInsert ;位置EltA挿入+=ステップ;ステップ=ステップ/ 3 ; } }

usingSystem ; public class ShellSorter { public void Sort ( int [ ] list ) { int inc ; for ( inc = 1 ; inc <= list.Length / 9 ; inc = 3 * inc + 1 ) ; for ( ; inc > 0 ; inc /= 3 ) { for ( int i = inc + 1 ; i <= list.Length ; i += inc ) { int t = list [ i - 1 ] ; int j = i ; while ( ( j > inc ) && ( list [ j - inc - 1 ] > t ) ) { list [ j - 1 ] = list [ j - inc - 1 ] ; j -=株式会社;リスト[ j - 1 ] = t ; } } } } public class MainClass { public static void Main ( ) { int [ ] iArrary = new int [ ] { 1,5,3,6,10,55,9,2,87,12,34,75,33 ,47 } ;シェルソーター sh =新しいシェルソーター( ) ;しー。ソート( iArrary ) ; ( int m = 0 ; m <= 13 ; m ++ )コンソールの場合。 WriteLine ( "{0}" ,iArrary [ m ] ) ; } }