ここでは高速に処理ができるアルゴリズムを紹介する。ここで高速と呼んでいるものは、O(nlogn)に分類できるものである。
入力データ 45 56 13 43 95 18 7 68 ステップ1分割の幅をskip=4とし、上記データをいくつかのブロックに分割する。
45 56 13 43 95 18 7 68 ^ ^ ^ ^ ^ ^ ^ ^ | | | | | | | | B1 B2 B3 B4 B1 B2 B3 B4 <--- 便宜上ブロックに名前を付けた このブロック内で並べ替えをおこなう。 B1ブロック 45 95 ----> 45 95 B2ブロック 56 18 ----> 18 56 B3ブロック 13 7 ----> 7 13 B4ブロック 43 68 ----> 43 68 よって、 45 18 7 43 95 56 13 68 となる。ステップ2 分割の幅を1/2にする。skip=2としてブロックに分割する。
45 18 7 43 95 56 13 68 ^ ^ ^ ^ ^ ^ ^ ^ | | | | | | | | B1 B2 B1 B2 B1 B2 B1 B2 このブロック内で並べ替えを行なう。 B1ブロック 45 7 95 13 ----> 7 13 45 95 B2ブロック 18 43 56 68 ----> 18 43 56 68 よって、 7 18 13 43 45 56 95 68 となる。ステップ3 分割の幅をさらに1/2にする。skip=1となり、全データを一つのブロック として考える。 よって、
7 13 18 43 45 56 68 95となり、並べ替えが完了する。 上記分割の幅の取り方は任意でよいが、ステップを増すごとに幅が減少していなければならない。最後のステップでは、skip=1として必ず全データを一つのブロックとして並べ替えを行なわなければならない。
1: void ShellSort(int data[], int n) { 2: int i, skip; 3: 4: skip = n / 2; 5: while( skip > 0 ) { 6: Insertionsort( data, skip, n ); 7: skip = skip / 2; 8: } 9: } 10: 11: void Insertionsort(int data[], int skip, int n) { 12: int tmp, i, j; 13: 14: for (i=skip; i < n; i=i+skip) 15: for (j=i-skip; j >= 0; j=j-skip) 16: if(data[j] > data[j+skip]) { 17: tmp = data[j]; 18: data[j] = data[j+skip]; 19: data[j+skip] = tmp; 20: } 21: }11〜21は、単純挿入法のメソッドである。単純挿入ソートで紹介したメソッドと別なものをここでは紹介した。一見バブルソートに外観が似ているが、基本的な考え方は単純挿入法であることに注意しよう。ただし、変数skipを用いて1次元的なデータをskip個おきに取っていくことによって、ブロックに分割しているように扱っている。
上記シェルソートでは、分割の幅を1/2にして求めているが、任意でよいが、なるべく互いに素(割り切れない)の数を選ぶとよい。この幅の取り方によってデータの入れ替え回数が変わることが知られている。
D.E.Knuthは、以下のような数列で分割の幅を採用すると効率がよいことを示した。
1、4、13、40、121、..一般的に、Si+1 = 3*Si +1, S1=1 で得られる数列を逆順にとるものとする。これらの数値は、互いに素ではないが、より効率的であることが知られている。 次のプログラムは、上記Knuthが推奨する数列で得られた数値を分割幅に採用した例である。
1: void ShellSort(int data[], int n) { 2: int i, skip[] = {121,40,13,4,1}; 3: 4: for ( i=0; i < 5; i++ ) 5: Insertionsort( data, skip[i], n ); 6: } 7: 8: void Insertionsort(int data[], int skip, int n) { 9: int tmp, i, j; 10: 11: for (i=skip; i < n; i=i+skip) 12: for (j=i-skip; j >= 0; j=j-skip) 13: if(data[j] > data[j+skip]) { 14: tmp = data[j]; 15: data[j] = data[j+skip]; 16: data[j+skip] = tmp; 17: } 18: }シェルソートの計算時間量は、分割の幅の取り方によりO(n^1.2)からO(n^2)であることが、知られている。証明については、難しいため省略する。