ヒープソート

このソート、今年の4月の試験に出て惨敗したアルゴリズムの課題です。
試験直前のお昼休みに見ていたにもかかわらず
できなかったという史上最悪な課題です。
ですからさすがに2度連続では出ないし
今度の試験対策にもなりませんが
暇に任せて考えてみることにします。
まず1つの根に2つの節があるようなヒープを作成します。
すると節を2で割った商が根になることが分かります。
(ここでの商は余りを抜いた数とします。以下も同様とします)
まだ実際のプログラムを見ていないので分かりませんが
ヒープを比較し始める根は
最大の並びの数を2で割った商からとなります。
そして根と右の節と比較し
(もしヒープの比較の最初で奇数の場合はこの後で出て来る根と左の節の比較からとなります)
節が大きい場合(等しい場合を含みません)は
根とその節を交換します。
さらにこの場合において節が並びの最大値より大きくなった場合は
その節との比較はスキップし、比較は終了します
また左右いずれの比較でも根が大きくなったら並びの最大値でなくとも比較は終了します。
上記2つ以外の場合は
交換した節を根とし、その根と2つの節を比較します。
(ここは再起呼び出しにより行います)
再起呼び出しを全て終了したら
今度は根と左の節で比較します。
そのやり方は根と右の節の場合と同様です。
上記終了後、根を1つ減らし根が1以上なら比較を続行します。
根が配列1の比較を終了したら
その配列1の値が最大値と確定します。
そしてその配列1の値を取りだし
配列2以上の配列の値を1つずつ減らしたヒープを作成します。
(実際には配列1を配列0にコピー、配列2を配列1にコピー…配列最大値を配列最大値-1にコピーとし最後に配列0を配列最大値にすれば配列は1つでよくなると思います)
そして最大値-1にてヒープを再度実行します。
最大値が1になったら置き換えソート終了です。
さぁこれから実際にプログラムを作成しないとですが
それは次回になりそうです。
しかしヒープソートより簡単な
バブルソートやクイックソートも再確認した方がよいのかもですね。