### 前提・実現したいこと
配列の要素に重複がある場合でもヒープソートを実現したい.
発生している問題・エラーメッセージ
配列の要素に重複がある場合, 以下のような結果になります.
$ 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}
試したこと
ヒープをつくることは正常にできました.
回答2件
あなたの回答
tips
プレビュー