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

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

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

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

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

まずは慣れろです。

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

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

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

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

例１　ヒープソート

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

//
//  main.c
//  heapSort
//ヒープソートプログラム　二分木
//  Created by 間世田 俊朗 on 2017/10/26.
//  Copyright © 2017年 maseda. All rights reserved.
//

#include 
#include 
#define NUM_DATA 10
int a[NUM_DATA+1];

void setData()
{
    int i;
    for(i=0; i<= NUM_DATA; i++){
        a[i] = rand() % 100;
    }
}
void showData(int a[], int n)
{
    int i;
    for(i = 1; i<= n; i++){
        printf("a[%2d] = %2d , ",i,a[i]);
        if(!(i%5)){
            printf("\n");
        }
    }
    printf("\n");
}
void swap(int a[],int first,int last){
    int i;
    i = a[first];
    a[first] = a[last];
    a[last] = i;
}
void downHeap(int a[],int leaf,int root){
    int i;
    i = root*2;
    while (i<= leaf) {
        if(i a[i]){
/*a[i+1]のときに配列数を越えてアクセスすることがあるので
この記述「if(i a[i])」は参考すべきではありません。
エラーにならないのですが、バグの源になります。後で書き換えます。
例えば、leaf = 10, root = 5 i= root*2 -> i= 10とすると
 a[i+1]ならa[11]にアクセスしますが、配列は0-10の11個までしかなくて、a[11]は存在しません。
しかし、このIF文ではコンパイルエラーにもならず、実行してもインデックスエラーになりません。
数が存在しないので、条件には合っていますがプログラム的に元から想定していない添字にアクセする
ことは好ましくないのでこの現時点でのコードは間違いと考えたほうが良いです。
少なくとも添字の数が配列数を越えていない場合にこのIF文を通過するように書き換えます。2017/10/28
*/
            i++;
        }
        if (a[root]>=a[i]) {
            break;
        }
        swap(a,root,i);
        root = i;
        i = root*2;
    }
}
void hpSort(int a[],int n){
    int leaf,root;
    leaf = n;
    root = n/2;
    while( root > 0){
        downHeap(a,leaf,root);
        root--;
        showData(a,NUM_DATA);
    }
    printf("root\n");
    showData(a,NUM_DATA);
    while(leaf>0){
        swap(a,1,leaf);
        leaf--;
        downHeap(a,leaf,1);
        showData(a,NUM_DATA);
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    setData();
    showData(a,NUM_DATA);
    hpSort(a, NUM_DATA);
    printf("Result\n");
    showData(a,NUM_DATA);
    return 0;
}

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

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

実行出力プリント例

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

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

//
//  main.c
//  heapsort_type2
//
//  Created by 間世田 on 2017/10/28.
//  Copyright © 2017年 maseda. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static void array_random_number(int *array,unsigned int size,unsigned int digit){
    int i;
    srand((unsigned int)time(NULL));
    for(i = 0;i<size;i++){
        array[i] = rand() % digit;
    }
}
static void array_print(int *array, unsigned int size){
    int i=0;
    for(i = 0;i<size; i++){
        printf("%d,",array[i]);
    }
    putchar('\n');
}
static void swap(int *i,int *j){
    int temp;
    temp = *i;
    *i = *j;
    *j = temp;
}
static void down_heap(int *array,int left,int right){
    int child;
    int parent = left;
    int temp = array[left];
    int cl,cr;
    while(parent < (right + 1)/2){
        cl = parent*2 + 1;
        cr = cl + 1;
        if((cr<= right) && (array[cr] > array[cl])){
            child = cr;
        }else{
            child = cl;
        }
        if(temp >= array[child]){
            break;
        }
        array[parent] = array[child];
        parent = child;
    }//while
    array[parent] = temp;
}

void heap_sort(int *array,unsigned int size){
    int i;
    for(i= (size-1)/2;i>=0;i--){
        down_heap(array,i,size-1);
        array_print(array, i);
    }
    printf("[heap]:");
    array_print(array, size);
    for(i = size-1;i>0;i--){
        swap(&array[0], &array[i]);
        down_heap(array, 0, i-1);
        printf("[heap]:");
        array_print(array, i);
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    int data[10];
    array_random_number(data, sizeof(data)/4, 100);
    printf("[before]");
    array_print(data, sizeof(data)/4);//int は4バイトなのでこれで割ると配列の数になる
    heap_sort(data, sizeof(data)/4);
    printf("[after]");
    array_print(data, sizeof(data)/4);
    return 0;
}