42の課題であるpush_swapについて簡単に解説したいと思います。アルゴリズムは基数(radix)ソートを使用しました。また、bonusなどは取り組んでいません。
基数ソート(Radix sort)
このような記事で色々紹介されているので、簡単に説明する。
全部の数字を２進数に直して一番右のビットから、0なら左のリスト（rotate）、1なら右のリストに移動して、終わったら左のリストに全部戻す（一番上に戻す）。その後また左のビットに１ずらしてまた、0なら左のリストのまま、1なら右のリストに移す。こうすることで、最終的には一番上に一番左のビットが1でその中でも左から2ビット目が大きいものが来る。
例えば001 110 101 010などがあった場合
001
110
101
010
→1ビット目見る
110 001
010 101
→戻す
001
101
110
010
→2ビット目みる
001 110
101 010
→戻す
110
010
001
101
→3ビット目見る
010 110
001 101
→戻す
110
101
010
001
→完成
こんな感じで一番上に一番大きいビットのものが来る
座標圧縮
これをする前に下処理として座標圧縮をする。
これは
100 10 1000
と並んでた時に
1 0 2
とする、ということ（小さい方から0, 1, ,,,とする）
なぜ座標圧縮するかについてだが、2進数で - (マイナス)の値を扱うときは
10001001 (10進数で-119)
となり、一番左の位で正か負を表すため（0が正で1が負を表す）
なので今回のように0と1で分けていくと一番左のビットに行った時に1なのにマイナスとなってしまって正しくソートできない。また、10と1000000などを2進数に直すとビットの位の差が大きすぎて容量が無駄になり時間がかかるのでよくない。
なので
-100 2 -11 200
などを
0 2 1 3
などとして、それをビットごとに0と1で分けていくと完成する
全体の流れ
座標圧縮→ビット演算で0と1を分けてソート
これだけでできる
座標圧縮は
リストの中身の値を配列にコピー(listの長さをmallocして配列を作成し、そこに値を一つずつ入れるだけ)
→配列をソート（bubbleソートとかで、なんでもいい）
→リストの中身を一つずつ見て配列との対応を見る
リスト： 100 10 1000
配列 ： 1 0 2
このような場合は
リストの1つ目の値に対応する、配列の1つ目の値は1なので100 → 1 に変更
2つ目に対応する10 → 0 に変更
3つ目も同様に1000 → 2 に変更
これで座標圧縮は完成
あとは0と1で分けるというのを各ビットごとにやる
void radix_sort(t_stack *a, t_stack *b)
{
int i;
int j;
int size;
int max_bits;
i = 0;
size = a->size;
max_bits = get_max_bit(a);
while (i < max_bits)
{
j = 0;
while (j < size)
{
if ((a->top->value >> i) & 1)
ra(a);
else
pb(a, b);
j++;
}
while (b->size > 0)
pa(a, b);
i++;
}
}
アルゴリズムとしては本当にこれだけだ。
get_max_bitという自作関数で、最大の値のビット数がいくつか(何桁か)を数えて、その回数分ひたすら交換を繰り返す、という単純なアルゴリズムだ。
あとはエラーハンドリング(重複やすでにソートされているかなどの確認)さえ行えば簡単に出来る！