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

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

新規登録して質問してみよう
ただいま回答率
86.02%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

Q&A

解決済

ヒープソートの実装に失敗します

Cas9bah
Cas9bah

総合スコア2

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

1回答

0グッド

0クリップ

249閲覧

投稿2022/11/20 09:13

前提

ヒープソートを実装したいです。

実現したいこと

発生している問題・エラーメッセージ

535 725 649 643 963 393 279 188 166 163

該当のソースコード

C++

1#include<bits/stdc++.h> 2using namespace std; 3#include<time.h> 4 5void pushdown(vector<int>&A, int first, int last){ 6 int i = first; 7 while(i <= (last-1) / 2){ 8 int j; 9 if(A[(2*i+1)] < A[(2*i+2)]){ //小さいほうの子の番号 10 j = (2*i+1); 11 } 12 else j = (2*i+2); 13 if(A[j] < A[i]){ //子が親より小さかった場合 14 swap(A[i], A[j]); 15 i = j; 16 } 17 else return; 18 } 19} 20 21void HeapSort(vector<int>&A){ 22 int n = A.size(); 23 vector<int> B; 24 for(int irev = 0; irev <= n/2; irev++) { 25 int i = n/2 - irev; 26 pushdown(A, i, n-1); 27 } 28 for(int irev = 1; irev <= n-1; irev++){ 29 int i = n - irev; 30 swap(A[0], A[i]); 31 pushdown(A, 0, i-1); 32 } 33} 34 35int main(){ 36 vector<int> a = {963,643,163,535,725,188,649,279,393,166}; 37 HeapSort(a); 38 for (int i = 0; i< 10; i++){ 39 cout << a[i] << " "; 40 } 41}

試したこと

サンプルコードを参照しながら怪しい部分を書き換えました。

補足情報(FW/ツールのバージョンなど)

以下のような質問にはグッドを送りましょう

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

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

気になる質問をクリップする

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

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

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

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

適切な質問に修正を依頼しましょう。

Zuishin

2022/11/20 10:51

アップヒープが無く、私の知っているヒープソートとは違うように見えますが、元にしたサンプルコードはどこにありますか?

回答1

0

ベストアンサー

問題点が3つあります。

1つ目は、pushdownが、子供が1つしかない場合に対応していないことです。
例えば、firstが0、lastが1の場合、最初のループでiが0となり、A[(2*i+2)]lastより後ろへのアクセスとなってしまいます。

2つ目は、pushdownfirst,lastがともに0の場合も子要素にアクセスしていることです。
while(i <= (last-1) / 2)の条件を考えると、(last-1)が-1、(last-1)/2が0となるため、初回のループが実行されてしまいます。

3つ目は、ヒープで最大値を求めなければならないのに、最小値を求めていることです。
ヒープで最小値を求めているため、各々のswapで最小値を一番後ろに移動していくことになります。その結果、昇順ではなく降順にソートされてしまいます。

前回もそうでしたが、vectorの添え字の範囲外アクセスに気づかないケースが多いように思います。コンパイルにg++を使っているなら、ソースの先頭に#define _GLIBCXX_DEBUGと入れることで、範囲外アクセスをチェックしてエラーにしてくれるようになるので、利用を検討してください。


プログラムが意図通りに動かない場合にやるべきことは、「サンプルコードを参照しながら怪しい部分を書き換えました。」ではなく「デバッグ」です。意図通りの動作にならない原因を調査しないまま修正すると、かえって正解から離れていく恐れがあります。変数の値が意図通りになっているか確認しつつ、1行ずつ実行していけば、どこで想定外の事象が発生しているか原因がはっきりします。デバッグ環境の整え方は検索すれば見つかると思います。

投稿2022/11/20 13:25

編集2022/11/26 06:19
actorbug

総合スコア1769

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

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

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。