問題
｛5, 10, 7, 8, 3, 1, 9, 2｝の数値配列を昇順にソートするプログラムを作りなさい。
ソート方法はクイックソートを使いなさい。
そもそもクイックソートがわからない方はヒント１を参照してください。
なるべくヒント２以降見ないように、自力で解いてください。
答えはこちら
ヒント
ヒント１：クイックソートとは
閾値は数字配列にある数字ならどれでもいいのですが、
今回は数字配列の真ん中の数字でクイックソートを行います。
引用：http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html
上記のようにクイックソートは閾値まで
左からは大きい値、右からは小さい値を探して値を交換していきます。
閾値にたどり着くと、そこから右配列、左配列に分かれて
同様に値交換をしていきます。
これは配列の数が多くなれば多くなるほど複雑になっていきます。
ヒント２：ロジックの考え方
①if分岐：すでに比べた値を重複して比べないIF分を作る
閾値を設定する
左カーソル位置を設定
右カーソル位置を設定
ループ処理：左のカーソル位置が右のカーソル位置と交差しない間処理を繰り返す
ループ処理：左カーソル値が閾値より大きい値がない間、カーソル位置を右にずらしていく
ループ処理：右カーソル値が閾値より小さい値がない間、カーソル位置を左にずらしていく
if分岐：すでに比べた値を重複して比べないIF分を作る
左カーソルの値と右カーソルの値を交換する
左カーソル位置を右にずらす
右カーソル位置を左にずらす
閾値位置より左側の配列を切り分けして「①if分岐」からの処理を行う
閾値位置より右側の配列を切り分けして「①if分岐」からの処理を行う
答えはこちら
コメント