ソートには色々ありますね。
アルゴリズムに必要なのはソートかなと思い
いくつか見てみました。
今年出たヒープソートは出ないとしても
他にこんなにあるんですね。
簡単に言うと
選択ソートは
最小から順にを探していくソート。
1-2,1-3,…,1-n,2-3,2-4,…2-n,…,(n-1)-n
と比較し、
左が小さければそのまま。
右が小さければ左右スワップです。
バブルソートは
1-2,2-3,…,(n-1)-n
,1-2,2-3,…,(n-2)-(n-1)
,…
,1-2
と比較するソート。
左が小さければそのまま。
右が小さければスワップ。
マージソートは
n/2,n/4,…と分割し
ブロックが2以下になったらソート開始。
ソートは左が小さければそのまま。
右が小さければスワップ。
各々のブロックが2以上では
1-1'で比較し小さい方を1番左へ
次に小さい方を+1して比較
小さい方を2番目に。
ここでは+1して比較のみで小さい順になる。
要素が1つで終了。
また2倍の要素でと繰り返す。
クイックソートは
中心を軸に取り
軸より小さければ軸より左に置き、
軸より大きければ軸より右に置く。
比較順は左から1番目、右から1番目、左から2番目、右から2番目、…
置き方は左に置いた場合は左から置き、
右から置いた場合は、右から置く。
比較終了で、軸より左のみで同様のソート、
軸より右のみで同様のソート。
要素が2で比較し確定。
文字だとわけわかんないですが
こんな感じかな。
ちなみにヒープソートは
まだ答え見ていません。
再帰を理解してから出直しです。
クイックソートでも再帰あるみたいだけどね。
アルゴリズムに必要なのはソートかなと思い
いくつか見てみました。
今年出たヒープソートは出ないとしても
他にこんなにあるんですね。
簡単に言うと
選択ソートは
最小から順にを探していくソート。
1-2,1-3,…,1-n,2-3,2-4,…2-n,…,(n-1)-n
と比較し、
左が小さければそのまま。
右が小さければ左右スワップです。
バブルソートは
1-2,2-3,…,(n-1)-n
,1-2,2-3,…,(n-2)-(n-1)
,…
,1-2
と比較するソート。
左が小さければそのまま。
右が小さければスワップ。
マージソートは
n/2,n/4,…と分割し
ブロックが2以下になったらソート開始。
ソートは左が小さければそのまま。
右が小さければスワップ。
各々のブロックが2以上では
1-1'で比較し小さい方を1番左へ
次に小さい方を+1して比較
小さい方を2番目に。
ここでは+1して比較のみで小さい順になる。
要素が1つで終了。
また2倍の要素でと繰り返す。
クイックソートは
中心を軸に取り
軸より小さければ軸より左に置き、
軸より大きければ軸より右に置く。
比較順は左から1番目、右から1番目、左から2番目、右から2番目、…
置き方は左に置いた場合は左から置き、
右から置いた場合は、右から置く。
比較終了で、軸より左のみで同様のソート、
軸より右のみで同様のソート。
要素が2で比較し確定。
文字だとわけわかんないですが
こんな感じかな。
ちなみにヒープソートは
まだ答え見ていません。
再帰を理解してから出直しです。
クイックソートでも再帰あるみたいだけどね。