ソート・アルゴリズムの性質をおさえておきたい。
頭の中のイメージではなく言葉で理解しておく必要がある。
ヒープソートとは？
ヒープソートとは何ですか？
回答は…
AP試験の問題によれば「未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。」とある。
ヒープとは木構造のことである。また、木構造における順序木とは、木の左よりも右の方が大きい性質がある。まとめると、木構造における順序木を利用したソートがヒープソートである。
ヒープと言われた時に「木構造なんだな」「木構造における順序木なんだな」と思い出せるようにしておきたい。
シェルソートとは？
シェルソートとは何ですか？
回答は…
AP試験の問題によれば「ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。」
挿入ソートを改良したソートである。
ちなみに、アルゴリズムの過程で二枚貝のような姿を表すからシェル（貝）ソートと言う人がいる（というか、そういうふうに先生に教えてもらったことがあるが）、アルゴリズムの考案者がドナルド・シェルだから…というのが正しい。
クイックソートとは？
クイックソートとは何ですか？
回答は…
AP試験の問題によれば「中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様な処理を繰り返す。」
なお、このように配列の部分ごとに処理を分割して再帰処理をしていくことを、分割統治法(divide-and-conquer method)という。
バブルソートとは？
バブルソートとは何ですか？
回答は…
AP試験の問題によれば「隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。」
データが徐々に浮かび上がってくる様子が”泡”のようなのでバブルと名付けられたそうである。
コメント