質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.92%

ヒープソートを作っているのですが動かなくなってしまいます。

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 280

GAKU_SAY

score 16

したいこと

配列array_intをヒープ条件に合うように並び替えたい。

条件

なるべく関数を書き換えたくないです。(名称は絶対に)
xcode
c++

欲しい情報

解決方法に関する情報

結果

1
0
0
0
1886912525
1835627109
1635020389
1634557804
1701535600
121

コード

#include<iostream>

int *array_int;//{1,13,14,60,15,91,24,71,80,63};
double *array_dob;
int mode = 0;

int size = 3;

using namespace std;

template <class X>void swap(X *a, X *b){
    X box = *a;
    *a = *b;
    *b = box;
}

int check_heap(){

    int j=0;

    for (int i=1; i<size; i++) {

        if (i%2 == 1) {
            j = (i-1)/2;
        }else{
            j=i/2-1;
        }

        if (mode == 0) {
            if (array_int[i] < array_int[j]) {
                return 0;
            }
        }else if (mode == 1){
            if (array_dob[i] < array_dob[j]) {
                return 0;
            }
        }

    }

    return 1;
}

void shift_down(){

    int i=0,j=0;

    if (mode == 0) {


        while (!check_heap()) {

            if (array_int[2*i+1] > array_int[2*i+2]) {
                j = 2*i+2;
            }else{
                j = 2*i+1;
            }

            swap(&array_int[i],&array_int[j]);

            i = 2*i+1;
        }


    }else if (mode == 1){

        while (!check_heap()) {

            if (array_dob[2*i+1] > array_dob[2*i+2]) {
                j = 2*i+2;
            }else{
                j = 2*i+1;
            }

            swap(&array_dob[i],&array_dob[j]);

            i = 2*i+1;
        }
    }

}

template<typename var>void insert(var val){

    ///メモリ確保&代入
    size++;

    if (mode == 0) {

        if ((array_int = (int*)realloc(array_int, sizeof(int)*size))==NULL) {
            cout << "I can't get enough size memory. SORRY" << endl;
        }

        array_int[size-1] = val;

    }else if (mode == 1){

        if ((array_dob = (double*)realloc(array_dob, sizeof(double)*size))==NULL) {
            cout << "I can't get enough size memory. SORRY" << endl;
        }

        array_dob[size-1] = val;

    }
    ///メモリ確保終了&代入

    int i=size-1,j = 0;

    while (!check_heap()) {

        if (i%2 == 1) {
            j = (i-1)/2;
        }else{
            j=(i-2)/2;
        }

        if (mode == 0) {
            swap(&array_int[i], &array_int[j]);
        }else if (mode == 1){
            swap(&array_dob[i], &array_dob[j]);
        }

        shift_down();

        i=j;
    }

}

template <typename var>var deletemin(){

    var returner = 0.0;

    if (mode == 0) {
        reterner = array_int[0];
        swap(&array_int[0],&array_int[size-1]);
    }else if(mode == 1){
        reterner = array_dob[0];
        swap(&array_dob[0],&array_dob[size-1]);
    }
    size--;

    array_int = (int*)realloc(array_int, sizeof(int)*size);

    shift_down();

    return returner;
}

int HeapSort(){

    int *aps = (int*)malloc(sizeof(int)*size);
    int i=0;
    int past = size;

    size = 1;
    aps[0] = array_int[0];

    for (i=size; i<past; i++) {
        insert(aps[i]);
    }

    free(array_int);
    array_int = aps;

    return 0;
}

int main(){

    size = 10;

    array_int = (int *)malloc(sizeof(int)*size);
    array_int[0] = 1;
    array_int[1] = 13;
    array_int[2] = 14;
    array_int[3] = 60;
    array_int[4] = 15;
    array_int[5] = 91;
    array_int[6] = 24;
    array_int[7] = 71;
    array_int[8] = 80;
    array_int[9] = 63;

    HeapSort();

    for (int i=0; i<size; i++) {
        printf("%d\n",array_int[i]);
    }


    free(array_int);

    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • y_waiwai

    2020/07/02 07:35

    提示のコードではどういう動作になるんでしょうか。
    エラーが出るならエラーメッセージを提示しましょう

    キャンセル

回答 1

checkベストアンサー

0

いろいろいろいろツッコミどころはありますが、とりあえずこれだけ。

free(array_int);
array_int = aps;

apsのナカミがどうなってるのか見てみよう。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/07/02 08:10

    中身を見てみようのアドバイスで解決しました。ありがとうございます。このコードは別のコードをもとに試作のような形で作ったのでわざと突っ込みどころのあるようになってたりします。

    キャンセル

  • 2020/07/02 08:15

    後学のために、ツッコミどころを教えていただけるとありがたいです。変数の書く位置や引数の過不足以外の内容でお願いします。

    キャンセル

  • 2020/07/02 08:59

    確認ですけど、標準C++に出来合いのヒープ関数群が用意されているんですが、あえてそれらを使わないって選択をしたんですよね?

    キャンセル

  • 2020/07/02 09:01

    それで間違い無いです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る