C言語 アルゴリズムを覚える クイックソートを覚えるぞ、基本情報技術者試験、午後問題対策

C言語 アルゴリズムを覚える クイックソートを覚えるぞ、基本情報技術者試験、午後問題対策

現在、基本情報技術者試験を勉強中です。
午後問題の対策がなかなか進まず。

現在の学習方法は、
過去問を解いていき、問題に慣れることはできました。
しかし、基本情報技術者試験の午後問題は、ほぼ同じ内容の問題は出てきませんので過去問題を完璧に解いても新しい問題に対応できません。

そこでプログラムの作成の基本に返り、アルゴリズムを覚えようと思います。
基本情報技術者試験の午後試験問題のアルゴリズムとC言語対策は、アルゴリズムを覚えるから始めようと思います。

本来は、アルゴリズムは覚えるのではなく、その解法を理解することなのですが、
理解すると時間ばかりが掛かりそうなので、まずは代表的なアルゴリズムを覚えてから理解しようと思います。

まずは慣れろです。

最初はクイックソートから始めます。

http://www1.cts.ne.jp/~clab/hsample/Sort/Sort9.htmlこのサイトを参考にする

ヒープソートのC言語コード

XCODEで作成しました。
以下は出力の例です。
ヒープソートは二分木になっていて、子供は2n,2n+1とか2n+1,2n+2のように並び順になっていて、1個次の配列が大きいように並びます。

例1 ヒープソート

Hello, World!
初期の数字の並び 10個
a[ 1] = 49 , a[ 2] = 73 , a[ 3] = 58 , a[ 4] = 30 , a[ 5] = 72 ,
a[ 6] = 44 , a[ 7] = 78 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 40 ,

ソート開始
a[ 1] = 49 , a[ 2] = 73 , a[ 3] = 58 , a[ 4] = 30 , a[ 5] = 72 ,
a[ 6] = 44 , a[ 7] = 78 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 40 ,

a[ 1] = 49 , a[ 2] = 73 , a[ 3] = 58 , a[ 4] = 30 , a[ 5] = 72 ,
a[ 6] = 44 , a[ 7] = 78 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 40 ,

a[ 1] = 49 , a[ 2] = 73 , a[ 3] = 78 , a[ 4] = 30 , a[ 5] = 72 ,
a[ 6] = 44 , a[ 7] = 58 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 40 ,

a[ 1] = 49 , a[ 2] = 73 , a[ 3] = 78 , a[ 4] = 30 , a[ 5] = 72 ,
a[ 6] = 44 , a[ 7] = 58 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 40 ,

a[ 1] = 78 , a[ 2] = 73 , a[ 3] = 58 , a[ 4] = 30 , a[ 5] = 72 ,
a[ 6] = 44 , a[ 7] = 49 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 40 ,

root
a[ 1] = 78 , a[ 2] = 73 , a[ 3] = 58 , a[ 4] = 30 , a[ 5] = 72 ,
a[ 6] = 44 , a[ 7] = 49 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 40 ,

a[ 1] = 73 , a[ 2] = 72 , a[ 3] = 58 , a[ 4] = 30 , a[ 5] = 40 ,
a[ 6] = 44 , a[ 7] = 49 , a[ 8] = 23 , a[ 9] = 9 , a[10] = 78 ,

a[ 1] = 72 , a[ 2] = 40 , a[ 3] = 58 , a[ 4] = 30 , a[ 5] = 9 ,
a[ 6] = 44 , a[ 7] = 49 , a[ 8] = 23 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 58 , a[ 2] = 40 , a[ 3] = 49 , a[ 4] = 30 , a[ 5] = 9 ,
a[ 6] = 44 , a[ 7] = 23 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 49 , a[ 2] = 40 , a[ 3] = 44 , a[ 4] = 30 , a[ 5] = 9 ,
a[ 6] = 23 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 44 , a[ 2] = 40 , a[ 3] = 23 , a[ 4] = 30 , a[ 5] = 9 ,
a[ 6] = 49 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 40 , a[ 2] = 30 , a[ 3] = 23 , a[ 4] = 9 , a[ 5] = 44 ,
a[ 6] = 49 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 30 , a[ 2] = 9 , a[ 3] = 23 , a[ 4] = 40 , a[ 5] = 44 ,
a[ 6] = 49 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 23 , a[ 2] = 9 , a[ 3] = 30 , a[ 4] = 40 , a[ 5] = 44 ,
a[ 6] = 49 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 9 , a[ 2] = 23 , a[ 3] = 30 , a[ 4] = 40 , a[ 5] = 44 ,
a[ 6] = 49 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

a[ 1] = 9 , a[ 2] = 23 , a[ 3] = 30 , a[ 4] = 40 , a[ 5] = 44 ,
a[ 6] = 49 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

Result 結果 昇順に並び替えられました
a[ 1] = 9 , a[ 2] = 23 , a[ 3] = 30 , a[ 4] = 40 , a[ 5] = 44 ,
a[ 6] = 49 , a[ 7] = 58 , a[ 8] = 72 , a[ 9] = 73 , a[10] = 78 ,

Program ended with exit code: 0

例2 別のヒープソートのソースコード

C言語、アルゴリズム 別のヒープソートのソースコードを参考にした

基本情報技術者試験の午後試験対策に、アルゴリズムを勉強中です。
ヒープソートは二分木のアルゴリズムです。
実際にコードを書くとかなり面倒なアルゴリズムです。
覚えるならクイックソートが楽ですしわかりやすい。
しかし、基本情報技術者試験の午後試験に出すならややこしい問題を選びそうなので、
ヒープソートを勉強してみます。

http://capm-network.com/?tag=C%E8%A8%80%E8%AA%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0-%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88

前回参考にしたヒープソートのソースコードは、一部エラーになりそうなコードが含まれていたので、別のヒープソートのC言語のソースコードを探しました。しかし、こちらも配列の総数よりも大きな数にアクセスしていました。
気づかないうちにそのままにしておくと、実際のプログラムでは問題になりそうなので、気をつけましょう。

XCODEで実際に実行します。

以下がヒープソートのソースコードです。

実際に実行しました。
また、最初に参考にしたヒープソートのソースコードの実行と比較してみました。
多少書き方によって実行順や処理回数、効率が変わるかもしれません。

結果は
少し変わりました。
同じアルゴリズムでも書く人によって実行処理効率が変わる感じですね。

Hello, World!
[before]58,90,8,50,97,65,64,39,34,95,
58,90,8,50,
58,90,8,
58,90,
58,

[heap]:97,95,65,50,90,8,64,39,34,58,
[heap]:95,90,65,50,58,8,64,39,34,
[heap]:90,58,65,50,34,8,64,39,
[heap]:65,58,64,50,34,8,39,
[heap]:64,58,39,50,34,8,
[heap]:58,50,39,8,34,
[heap]:50,34,39,8,
[heap]:39,34,8,
[heap]:34,8,
[heap]:8,
[after]8,34,39,50,58,64,65,90,95,97,
Program ended with exit code: 0

実行出力プリント例

ヒープソート タイプ2の実行例
紙面上でトレースをしてなかなかソートできないと思ったら、
ノートに書き写して参考にしたコードが間違っていて、なかなかプログラムの計算結果にならず、ずっと悩んでた。なんのことはないノートの書き間違いのバグのプログラムを使って間違った計算結果に悩んでいた。

Hello, World!
[before]78,2,65,66,6,96,43,77,62,25, ソート前の状態
i = 4
[down]:78,2,65,66,25,96,43,77,62,25,
[calc]:78,2,65,66,25,96,43,77,62,6,
i = 3
[down]:78,2,65,77,25,96,43,77,62,6,
[calc]:78,2,65,77,25,96,43,66,62,6,
i = 2
[down]:78,2,96,77,25,96,43,66,62,6,
[calc]:78,2,96,77,25,65,43,66,62,6,
i = 1
[down]:78,77,96,77,25,65,43,66,62,6,
[down]:78,77,96,66,25,65,43,66,62,6,
[calc]:78,77,96,66,25,65,43,2,62,6,
i = 0
[down]:96,77,96,66,25,65,43,2,62,6,
[calc]:96,77,78,66,25,65,43,2,62,6,
[heap]:96,77,78,66,25,65,43,2,62,6,
[swap]:6,77,78,66,25,65,43,2,62,96,
[down]:78,77,78,66,25,65,43,2,62,96,
[down]:78,77,65,66,25,65,43,2,62,96,
[heap]:78,77,65,66,25,6,43,2,62,96,
[swap]:62,77,65,66,25,6,43,2,78,96,
[down]:77,77,65,66,25,6,43,2,78,96,
[down]:77,66,65,66,25,6,43,2,78,96,
[heap]:77,66,65,62,25,6,43,2,78,96,
[swap]:2,66,65,62,25,6,43,77,78,96,
[down]:66,66,65,62,25,6,43,77,78,96,
[down]:66,62,65,62,25,6,43,77,78,96,
[heap]:66,62,65,2,25,6,43,77,78,96,
[swap]:43,62,65,2,25,6,66,77,78,96,
[down]:65,62,65,2,25,6,66,77,78,96,
[heap]:65,62,43,2,25,6,66,77,78,96,
[swap]:6,62,43,2,25,65,66,77,78,96,
[down]:62,62,43,2,25,65,66,77,78,96,
[down]:62,25,43,2,25,65,66,77,78,96,
[heap]:62,25,43,2,6,65,66,77,78,96,
[swap]:6,25,43,2,62,65,66,77,78,96,
[down]:43,25,43,2,62,65,66,77,78,96,
[heap]:43,25,6,2,62,65,66,77,78,96,
[swap]:2,25,6,43,62,65,66,77,78,96,
[down]:25,25,6,43,62,65,66,77,78,96,
[heap]:25,2,6,43,62,65,66,77,78,96,
[swap]:6,2,25,43,62,65,66,77,78,96,
[heap]:6,2,25,43,62,65,66,77,78,96,
[swap]:2,6,25,43,62,65,66,77,78,96,
[heap]:2,6,25,43,62,65,66,77,78,96,
[after]2,6,25,43,62,65,66,77,78,96,
Program ended with exit code: 0

こちらの記事もどうぞ