シェルソートとクイックソート
→ソートを高速化する
シェルソート
適当な間隔を決めてその間隔だけ離れた要素同士で挿入ソート
間隔を1になるまで狭めて繰り返す
間隔は4→2→1みたいなものだと違うセットでソートされないので
を利用するといい(1,4,13,40,121…)
要素数/9を超えないくらいを目安にするといい
感覚的には挿入ソートを何度かやるということになるが、実装では挿入する対象を飛び飛びにする
void shellsort( recordtype a[], int n ){
int i, j, h; recordtype v;
// 間隔hの初期値を決める (h_{n+1} = 3h_n + 1)
// h*3+1 <= n/9 になるまで広げる (遠すぎると効果が薄い)
for( h=1; h*3+1 <= n/9; h = h*3+1 );
// 間隔hを3で割って狭めていく (h=1 で通常の挿入ソート)
for( ; h > 0; h /= 3){
// h+1 から開始 (添字1始まり、h個目の要素の次から)
for( i = h+1; i <= n; i++ ){
v = a[i]; // 挿入する対象を保存
j = i;
// h個飛ばしで挿入ソート (番兵: j > h で範囲チェック)
while( j > h && a[j-h].key > v.key ){
a[j] = a[j ‒ h]; // h個左の要素を右にずらす
j -= h;
}
a[j] = v; // 挿入
}
}
}以下に収まる
に比べるとかなりマシ
クイックソート
分割統治法による(再帰)
- 列を２つに分割してそれぞれを分割
- ピボットより小さいものは前に、大きいものは後ろに
- ピボットの前と後ろを再度分割してクイックソート(再帰)
void quicksort( recordtype a[], int l, int r ){
int i;
if ( l < r ){
i = partition( a, l, r ); // pivot の位置 i を決定
quicksort( a, l, i-1 ); // 左部分列を再帰ソート
quicksort( a, i+1, r ); // 右部分列を再帰ソート
}
}こうでいい
partitionを実装する
partition の考え方（Hoare の方法）
左端を pivot とし、i（左→右）と j（右→左）を同時に進める。
[ pivot より小さい ] pivot [ わからない ] [ pivot より大きい ]
↑ i が pivot より大きい値を見つける ↑ j が pivot より小さい値を見つける
手順：
- i を右へ進めて pivot より大きい値を探す（交換候補）
- j を左へ進めて pivot より小さい値を探す（交換候補）
- i < j なら入れ替え
- i と j が交差したら（i > j）入れ替え終了
- pivot を j と入れ替え（pivot より小さい値の右端と交換）
最終的に配列はこうなる：
[ pivot より小さい ] pivot [ pivot より大きい ]
↑ j (= i の位置)
flowchart TD A["v = a[l] ← pivot を保存"] --> B["i = l, j = r + 1"] B --> C["do-while ループ開始"] C --> D["i++ : a[i] < v なら右へ進める"] D --> E["j-- : a[j] > v なら左へ進める"] E --> F{"i < j ?"} F -->|Yes| G["swap(a[i], a[j])"] --> C F -->|No| H["do-while 終了（交差）"] H --> I["swap(a[l], a[j]) ← pivot を正しい位置に"] I --> J["return j"] style A fill:#f9f,stroke:#333 style I fill:#f9f,stroke:#333 style J fill:#bbf,stroke:#333
※ここでは左端と pivot を別途選んで入れ替えるが、今回は簡略化して左端を pivot としている
int partition( recordtype a[], int l, int r ){
int i, j; recordtype v;
v = a[l]; // 左端を pivot として保存
i = l; // 左から探索開始
j = r + 1; // 右から探索開始 (j-- で最初に r になる)
do {
// pivot より大きい値を見つけるまで i を右へ進める
do { i++; } while( a[i].key < v.key );
// pivot より小さい値を見つけるまで j を左へ進める
do { j--; } while( a[j].key > v.key );
// 交差していなければ入れ替え
if ( i < j ){
swap( &a[i], &a[j] );
}
} while ( j > i ); // i と j が交差するまで繰り返し
// pivot を正しい位置 j に入れる (j は pivot より小さい値の右端)
a[l] = a[j];
a[j] = v;
return j; // pivot の最終位置を返す
}※範囲チェック or 番兵が本当は必要（今回の実装では省略）
quicksort2（Lomuto の方法）
番兵を必要としない、a[0]からデータが入っているときの方法
手順：
- ランダムにピボットを選択
- ピボットを先頭に
- ピボットより小さいものを先頭に詰める
- 小さいものの末尾とピボットを入れ替える
void quicksort2( recordtype a[], int n ){
int i, last;
if( n <= 1 ) return; // 要素数1以下なら終了 (終端条件)
swap( &a[0], &a[ rand() % n ] ); // pivot を乱数で選んで先頭に
last = 0; // pivot より小さい値の右端を追跡
for( i = 1; i < n; i++ ){
if ( a[i].key < a[0].key ){ // pivot より小さい値を見つけた
swap( &a[++last], &a[i] ); // last の次に詰めて入れ替え
}
}
swap( &a[0], &a[last] ); // pivot を正しい位置に
quicksort2( a, last ); // 左部分列を再帰ソート (pivot の手前まで)
quicksort2( a + last + 1, n - last - 1 ); // 右部分列を再帰ソート (pivot の後ろから末尾まで)
}a[0]が pivot になる（添字0から使う）lastで pivot より小さい値の右端を追跡- 配列末まで探索するので番兵不要
ヒープソート
ヒープというデータ構造では最大値や最小値を抽出できる
→選択ソートを高速にできる
ヒープとは
- 半順序集合を二分木で表現したデータ構造
- 親ノードは子ノードよりも小さいか等しい
- n段のヒープはn-1段はすべて埋まっていて、n段目は左詰めの構造
ヒープは配列添字を1から開始する場合、親ノードは、子ノードはやでアクセス可能