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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

1413閲覧

ヒープソートを行う際、要素に重複があるとダウンヒープがうまくいかない

wassho1

総合スコア5

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

1クリップ

投稿2018/05/12 05:04

編集2018/05/12 07:17

### 前提・実現したいこと
配列の要素に重複がある場合でもヒープソートを実現したい.

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

配列の要素に重複がある場合, 以下のような結果になります.

$ cat data1.txt 9 4 2 3 4 9 7 5 3 4 $ ./heap input filename:data1.txt 4 2 3 4 9 7 5 3 4 2 3 4 4 3 5 4 7 9

data1.txtの1行目は要素の個数を表しているので関係はございません. 2行目以降がヒープソートを実行したい配列の要素になります.

該当のソースコード

c

1#include<stdio.h> 2#include<stdlib.h> 3#include<string.h> 4 5int parent(int i); 6int left(int i); 7int right(int i); 8int right(int i); 9void Upheap_sort(int H[],int n); 10void Build_Heap(int H[], int n); 11void Downheap_sort(int H[], int n); 12void heapsort(int H[],int n); 13 14int main(void){ 15 int Data[50];/*数値を格納する配列*/ 16 int N;/*読み込む要素数*/ 17 int i; 18 char fname[128];//読み込むファイルの名前をかくのうする変数 19 FILE *fp; 20 21 printf("input filename:"); 22 fgets(fname,sizeof(fname),stdin);//標準入力からファイル名を取得 23 fname[strlen(fname)-1] = '\0';//最後の行改行コードを削除 24 fflush(stdin);//128文字を超えた入力を標準入力から捨てる 25 fp = fopen(fname, "r");//ファイルを読み込みモードで開く 26 fscanf(fp,"%d",&N); 27 for(i=0;i<N;i++){ 28 fscanf(fp, "%d",&Data[i]); 29 } 30 fclose(fp); 31 32 for(i=0;i<N;i++){ 33 printf("%d ", Data[i]); 34 } 35 printf("\n"); 36 37 heapsort(Data,N); 38 39 for(i=0;i<N;i++){ 40 printf("%d ", Data[i]); 41 } 42 printf("\n"); 43 44 return 0; 45} 46 47int parent(int i){//親を返す関数 48 int ans; 49 ans = (double)(i-1)/2; 50 return ans; 51} 52int left(int i){//左の子を返す関数 53 int ans; 54 ans = 2*i+1; 55 return ans; 56} 57 58int right(int i){//右に子を返す関数 59 int ans; 60 ans =2*i+2; 61 return ans; 62} 63 64void Upheap_sort(int H[], int i){//一番後ろの要素をheapの性質を満たすように並べ替える関数. 65 int u,tmp; 66 u = i; 67 while(u>0 && H[parent(u)]<H[u]){ 68 tmp = H[parent(u)]; 69 H[parent(u)] = H[u]; 70 H[u] = tmp; 71 u = parent(u); 72 } 73} 74 75void Build_Heap(int H[],int n){//heapをつくる関数 76 int i; 77 for(i=1;i<n;i++){ 78 Upheap_sort(H,i); 79 } 80} 81 82void Downheap_sort(int H[],int n){//根の値をheapの性質にしたがって直す関数 83 int u,l,r,tmp; 84 u=0; 85 l=1; 86 r=2; 87 while(l!=u && r!=u){//l=r=uとなれば終了 88 if(left(u)<=n){//左の子がいるかいないかで場合分け 89 l = left(u); 90 } 91 else{ 92 l = u; 93 } 94 if(right(u)<=n){//右も同様 95 r = right(u); 96 } 97 else{ 98 r = u; 99 } 100 if(H[l]>H[u] || H[r]>H[u]){//H[l]もしくはH[r]のどちらかの値がH[u]の値を超えていたらこの操作に入る 101 if(H[l]>=H[r]){//H[l]がH[r]以上ならば左の子とH[u]の値を交換 102 tmp = H[u]; 103 H[u] = H[l]; 104 H[l] = tmp; 105 u = l; 106 } 107 else{ 108 tmp = H[u]; 109 H[u] = H[r]; 110 H[r] = tmp; 111 u = r; 112 } 113 } 114 else{//H[l], H[r]がともにH[u]以下の場合このループをぬけ出す. 115 l = u; 116 r = u; 117 } 118 } 119} 120 121void heapsort(int H[],int n){//heapsort関数 122 int i,tmp; 123 Build_Heap(H,n); 124 for(i=1;i<n;i++){ 125 tmp = H[n-i]; 126 H[n-i] = H[0]; 127 H[0] = tmp; 128 Downheap_sort(H,n-i-1); 129 } 130}

試したこと

ヒープをつくることは正常にできました.

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

set0gut1

2018/05/12 05:45

内容修正を期待しています
wassho1

2018/05/12 06:32

私がteratailを使い慣れていないことが原因でご不便をお掛けしました. 申し訳ございません.
set0gut1

2018/05/12 06:40

いえいえ、問題ありません。
guest

回答2

0

自己解決

原因がわかり自己解決に至りました。Downheap_sortのwhileの条件文の論理演算子が「&&」ではなく「||」でないと、lもしくはrがuになった時点でwhile文から抜けてしまうためでした

投稿2018/05/12 15:50

wassho1

総合スコア5

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

こんにちは、
ヒープソートをご覧ください。

Java

1#include <stdio.h> 2 3void h_down(int *ar,int size,int root); 4void h_sort(int *ar,int size); 5void swap(int *a, int *b); 6 7int main(void){ 8 9 int ar[]={9,4,2,3,4,9,7,5,3,4}; 10 int ar_size = sizeof(ar) / sizeof(int) - 1; 11 int i; 12 h_sort(ar,ar_size); 13 14 for(i = 0;i <= ar_size;i++){ 15 printf("%d ",ar[i]); 16 } 17 printf("\n"); 18 return 0; 19} 20 21void swap(int*a, int*b){ //入れ替え 22 int c; 23 c = *a; 24 *a = *b; 25 *b = c; 26} 27 28void h_sort(int*ar,int size){ 29 //ヒープ作成 30 int i; 31 for(i = (size / 2);i >= 0;i--){ 32 h_down(ar,size,i); 33 } 34 //ヒープソート 35 while(1){ 36 swap(&ar[0],&ar[size--]); 37 if(!size) break; 38 h_down(ar,size,0); 39 } 40 return; 41} 42 43void h_down(int*ar,int size,int root) 44{ 45 int max; 46 while(1){ 47 //値の大きい方の枝を調べる 48 max=root * 2 + 1; 49 if(root * 2 + 2 <= size){//2の枝が存在する 50 if(ar[root * 2 + 1]<ar[root * 2 + 2]){//1の枝と比較して 51 max=root * 2 + 2; 52 } 53 } 54 else if(!(root * 2 + 1 <= size)){ 55 break;//1の枝が存在しないため終了 56 } 57 //値の大きいほうの枝と根を比べて、値を交換する 58 if(ar[root]<ar[max]){ 59 swap(&ar[root],&ar[max]); 60 root = max;//交換できたため、枝←根にする 61 } 62 else{ 63 break;//根の方が大きいため終了 64 } 65 } 66 return; 67}

データ
9 4 2 3 4 9 7 5 3 4
結果
2 3 3 4 4 4 5 7 9 9

投稿2018/05/12 10:37

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問