ヒープソートとは？
- ヒープソートは、要素を二分ヒープと呼ばれるデータ構造に格納し、昇順に並べ替えるソートアルゴリズムです。
- ヒープソートは、大量のデータを効率的にソートすることができる上、安定なソート結果を得ることができます。
- ヒープソートは、アルゴリズムがシンプルで実装しやすいため、プログラミングコンテストなどでよく使用されることもあります。
- ベストアンサー
ヒープソートを教えてください
本を読んで作ってみたのですが、ソートしてくれません。。 void down(int from, int to); void heapsort(char s[][WC],int n); void down(int from, int to){ int i=1, j; char s[NS][WC],val; val = s[from][WC]; i = from; while(i <= to/2){ j = i*2; if(j+1 <= to && strcmp(s[j],s[j+1])>0) j++; if(strcmp(s[j],s[from])>0) break; strcpy(s[i],s[j]); i = j; } s[i][WC] = val; } void heapsort(char s[][WC],int n) { int i; char tmp[WC]; for(i = n/2; i >= 1; i--) down(i, n); for(i = n; i >=2; i--){ strcpy(tmp,s[1]); strcpy(s[1],s[i]); strcpy(s[i],tmp); down(1, i-1); } }
- fortis747
- お礼率40% (2/5)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
ぱっと見で down() が変ですね。 void down(int from, int to){ int i=1, j; char s[NS][WC],val; ← この配列sは何のためにここで宣言しているのでしょう? val = s[from][WC]; ← val に取り出した値は何のためのもの? heapsortでソートを行うためにヒープを作るためのものだと思いますが、 heapsortの引数の s[] がまるきり無視されているので、downで やっていることは何の意味もないことです。 Tacosaonも書かれてますが、先に一次元の整数配列がきちんとできるように したほうがよいと思います。
その他の回答 (1)
関連するQ&A
- ヒープソートがわかりません
以下のようなヒープソートのプログラムを作ったのですが、どうしても動きません。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define NS 3000000 /* 入力の最大数 */ #define WC 64 /* 入力の１行の文字数 */ void down(int from, int to); void heapsort(int s[NS+1][WC], int n); void down(int from, int to){ int i, j; int val; int s[NS+1][WC]; i = from; val = s[from][WC]; while(i <= to/2){ j = i*2; if(j+1 <= to && s[j] > s[j+1]) j++; if(val <= s[j][WC]) break; s[i][WC] = s[j][WC]; i = j; } s[i][WC] = val; } void heapsort(int s[NS+1][WC], int n) { int i; int tmp; for(i = n/2; i >= 1; i--) down(i, n); for(i = n; i >=2; i--){ tmp = s[1][WC]; s[1][WC] = s[i][WC]; s[i][WC] = tmp; down(1, i-1); } } main(int argc, char *argv[]) { FILE *fp; char s[NS][WC], buff[WC]; int i=0,n=0; if ((argc==1) || (argc>=3)) { printf("Input filename\n"); exit(1); } fp=fopen(argv[1],"r"); while(fgets(buff, sizeof(buff),fp)!=NULL){ sscanf(buff,"%s",&s[i]); i=n; } printf("File reading completed.\n"); heapsort(s[NS+1][WC],n); for (i=0; i<n; i++) { if (strcmp(A1[i],A2[i])!=0) { printf("Results are incorrect!\n"); exit(1); } } printf("Results are correct.\n"); fclose(fp); exit(0); }
- ベストアンサー
- その他(ソフトウェア)
- C言語 シンプルソート
C言語始めて1年の初心者です。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXSIZE 10000 void swapData(char *x, char *y); void simpleSort(char data[], int first, int last); int main(int argc, char *argv[]) { int data[MAXSIZE][300]; int i, j, count; FILE *fp; if(argc != 2) { fprintf(stderr, "Usage: %s <filename>\n", argv[0]); exit(0); } if ((fp = fopen(argv[1], "r")) == NULL) { fprintf(stderr, "File %s is not found.\n", argv[1]); exit(0); } for(i = 0; i < MAXSIZE; i++) { if (fscanf(fp,"%s", &data[i]) == EOF) break; } simpleSort(data[], 0, i - 1); for(j = 0; j < i; j++) printf("%s\n", data[j]); } void swapData(char *x, char *y){ char tmp[300]; strcpy(tmp, x); strcpy(x, y); strcpy(y, tmp); } void simpleSort(char data[], int first, int last) { int i, j; for(i = first; i < last; i++){ for(j = i+1; j <= last; j++){ if(strcmp(&data[i], &data[j]) > 0) swapData(&data[i], &data[j]); } } } 読み込んだ文字データをシンプルソートするプログラムなんですが、コンパイルできません。 simpleSortの部分がおかしいみたいなんですが、見直しても先入観からか間違いを見つけられません・・・・ どなたか間違いを指摘していただけたら助かります。
- ベストアンサー
- C・C++・C#
- ヒープソート
何回も申し訳ございません。ヒープソートを使用して、K番目に小さい配列の要素を見つけるプログラムを作成していますが、セグメンテーションフォルトが出力され、途方に暮れています。どなたか助けていただけないでしょうか？ #include<stdio.h> #include<stdlib.h> #include<time.h> void heap(int c,int size,int *s){ int child,p; int tmp; child=s[c]; while(1){ p=(c-1)/2;//calculate an index of their parent if(c<0) break; if(c!=0){ if (s[c]>s[c-1]) { c=c-1; } } if (s[p]<=s[c]) break; // break if a parent is smaller than a child tmp=s[p]; s[p]=s[c]; s[c]=tmp; c=p;//declare a parent node as a child node } } void heap_sort(int c,int size,int *s){ int tmp,i,j; //make the first heap for(i=size-1;i>=0;i--){ heap(i,size,s); } //exchange root s and the last s, and sort them for(i=size-1;i>=0;i--){ tmp=s[0]; s[0]=s[i]; s[i]=tmp; for(j=i;j>=0;j--){ heap(j-1,j,s); } } } main() { int num,i,k; int high; int low=0; int s[20]; struct timeval t1,t2; printf("How many elements?:"); scanf("%d",&high); printf("?n"); printf("What number?:"); scanf("%d",&k); printf("?n"); srand((unsigned)time(NULL)); for(i=0;i<high;i++){ s[i]=rand()%10; printf("%d ",s[i]); } printf("?n"); gettimeofday(&t1,0); heap_sort(high-1, high,s); gettimeofday(&t2,0); printf("Time=%dmicrosec?n", t2.tv_usec-t1.tv_usec); printf("The %dth smallest is %d?n ", k,s[k]); }
- ベストアンサー
- C・C++・C#
- プログラミング(配列と関数の引数)
a : ABCDE a : ABCDEFGH Len : 8 a : FGHIJ a : FGH a : FGH, c : FGH 上記のように表示されるプログラムを作りたいのですが、なかなかできません。下記のようなプログラムを作ったのですがどこが間違っているのかよくわかりません。分かる方、指摘をお願いします。 #include <stdio.h> void my_strcpy(char s[], char t[]); int my_strlen(char s[]); void my_strcat(char s[], char t[]); int main(){ char a[10]; char b[10] = "ABCDE"; char c[] = "FGH"; int len; my_strcpy(a, b); printf("a : %s\n", a); my_strcat(a, c); printf("a : %s\n", a); len = my_strlen(a); printf("Len : %d\n", len); my_strcpy(a, "FGHIJ"); printf("a : %s\n", a); a[3] = '\0'; printf("a : %s\n", a); if(strcmp(a, c) == 0){ printf("a : %s, c : %s\n", a, c); } int i, s, t; my_strcpy(a, b + 2); printf("a : %s\n", a); void my_strcpy(char s[], char t[]){ for (i = 0; t[i] != '\0'; i++){ s[i] = t[i]; } s[i] = '\0'; } int my_strlen(char s[]){ int i; for (i = 0; s[i] != '\0'; i++); return i; } void my_strcat(char s[], char t[]){ int i, j; for (i = 0; s[i] != '\0'; i++); for (j = 0; t[j] != '\0'; i++, j++){ s[i] = t[j]; } s[i] = '\0'; } }
- ベストアンサー
- C・C++・C#
- 最小ヒープソートについて
問題：numbers.datから１０個の整数を読みこみヒープソートで昇順に表示せよ。 numbers.dat 91 63 71 14 60 1 24 13 80 15 質問：下記が自分のコードなんですが実行すると 1 13 13 13 13 13 13 13 13 13になるんですが、何を直せばいいでしょうか。最小の値を取り出していくようにしているつもりなんですが #include<stdio.h> #include<stdlib.h> void insert( int i,int a[], int n); int deletemin(int a[], int n,int m); int main() { int a[10],m[10]; int i,j,k; int n = 10; FILE *fp; fp = fopen("numbers.dat", "r"); if(fp == NULL) { printf("ファイルが開けません\n"); return 1; } fscanf(fp,"%d %d %d %d %d %d %d %d %d %d\n",&a[0] ,&a[1] ,&a[2] ,&a[3] ,&a[4] ,&a[5] ,&a[6] ,&a[7] ,&a[8],&a[9] ); for(i = (n - 2)/2; i >= 0; i--) { insert(i, a, n-1); } for(i = n-1; i >= 0; i-- ) { m[9-i] = deletemin(a, i, n-1); } for(j = 0; j < 10; j++){ printf("%3d",m[j]); } return 0; } void insert( int i,int a[], int n) { int j; int temp; while (2 * i + 1 <= n) { j = 2 * i + 1; if (j < n) { if (a[j] > a[j + 1]) { j++; } } if (a[i] <= a[j]) { break; } temp = a[j]; a[j] = a[i]; a[i] = temp; i = j; } } int deletemin(int a[],int n, int m) { int b; int temp; int i,j; b = a[0]; a[0] = a[n]; i = 0; while (2 * i + 1 <= m) { j = 2 * i + 1; if (j < m) { if (a[j] > a[j + 1]) { j++; } } if (a[i] <= a[j]) { break; } temp = a[j]; a[i] = a[j]; a[i] = temp; i = j; } return b; }
- 締切済み
- C・C++・C#
- strcpyのsegmentation faulｔ
118 char* argv[argc+1]; 120 121 for(i = 0; i < argc ; i++) 122 { 123 char tmp[BUF]; 124 while(buf[k]!=' ' & buf[k]!='\0') 125 { 126 tmp[j] = buf[k]; 127 j++; 128 k++; 129 } 130 tmp[j]='\0'; 131 j=0; 132 k++; 133 strcpy(argv[i],tmp); 134 //arg v[array]=tmp; 135 printf("temp = %s argv = %s\n",tmp,argv[array]); 136 } 137 argv[i+1]=tmp2; 133番の部分が問題です 最初に回る時にはprintfの結果が出ます temp = test argv = test でも2回目からはerrorになるます argv[1]は char*刑なのでstrcpyに何の問題もないと思いますが どんな問題でerrorがでるのでしょうか？ これはlineを呼んで int main(int argc, char* argv[]) のargv部分をようにするためのcodeです errorの理由とか char* argv[]部分を簡単に作る方法を知りたいです お願いします
- ベストアンサー
- C・C++・C#
- クイックソートのアルゴリズムが分かりません＞＜；
C言語初心者の学習を終えて、アルゴリズムの構造を学んでいる段階のものです。バブルソートを実装することは成功したのですが、クイックソートが実装できません＞＜ 以下は文字列をバブルソートできるアルゴリズムです。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MAXCHARSINONELINE 400 #define LINETABLESIZE 100 char linetable[LINETABLESIZE][MAXCHARSINONELINE]; int resultindex[LINETABLESIZE]; int maxtableindex = 0; void addToTable(char *); void initresult(); void mysort(); int mycompare(int, int); void myswap(int, int); char mark[2]; int start; int end; int main(void) { char line[MAXCHARSINONELINE]; char *ret; int i; do { ret = fgets(line,MAXCHARSINONELINE,stdin); if( ret != NULL ) { addToTable(line); } } while(ret != NULL); fprintf(stderr,"sorting...\n"); start = clock(); /* for(i=0; i<10000; i++){ */ initresult(); mysort(); /* } */ end = clock(); fprintf(stderr,"[%f sec]\n",(float)(end-start)/CLOCKS_PER_SEC); fprintf(stderr,"[results]\n"); for( i = 0; i < maxtableindex; i++ ) { printf("(L.%3d):%s",resultindex[i]+1, linetable[ resultindex[i] ]); } return 0; } void addToTable(char *data) { if( maxtableindex >= LINETABLESIZE ) { fprintf(stderr,"Table is full.!\n"); exit(0); } strncpy( linetable[maxtableindex], data, MAXCHARSINONELINE ); maxtableindex++; } void initresult() { int i; for( i = 0; i < maxtableindex; i++ ) { resultindex[i] = i; } } void mysort() { int i,j,k; for( i = maxtableindex-1; i > 0; i-- ) { for( j = 0; j < i; j++ ) { /* printf("--\n"); for(k = 0; k < maxtableindex; k++) { if((k == j) || (k == j + 1)) { strcpy(mark,"*"); } else { strcpy(mark," "); } printf("%s %s", mark, linetable[resultindex[k]]); } printf("--\n"); */ if( mycompare(j, j + 1) > 0) { /* printf("swap %d <----> %d\n",j ,j + 1); */ myswap(j, j + 1); } } } } int mycompare(int i, int j) { return strcmp(linetable[resultindex[i]], linetable[resultindex[j]]); } void myswap(int i, int j) { int tmp; tmp = resultindex[j]; resultindex[j] = resultindex[i]; resultindex[i] = tmp; } このプログラムを改編して、クイックソートにしたいのですが、どこをどうすればよいのでしょうか。 長くなってすみません。 ご回答をお願いします。
- 締切済み
- C・C++・C#
- 入力されたテキスト行の中で最も長い行を表示するプログラム
下のプログラムのmainの***************部とgetl()をどのように書いたらいいかわかりません。 出来ればプログラミングで書いていただけると嬉しいです。 #include <stdio.h> #define MAXLINE 1000 int getl(char s[] , int lim) { } void copy(char to[], char from[] ) { int i; i= 0; while((to[i] = from[i]) ! = ‘\0’) ++i; } int main() { int len; int max; char line[MAXLINE]; char longest[MAXLINE]; max = 0; 本で調べたところ、ループが終わる条件はＥＯＦか、\nが出たときと、limitを超えるときのようなんですが・・・ お願いいたします。
- ベストアンサー
- C・C++・C#
- cプログラミングについて
以下はsample.txtというファイルを読み込み、辞書順に並べるプログラミングですが、どう正しく 直したらよいかわかりません。間違っている場所を指摘していただけたらと思います。 (間違えだらけで申し訳ありません) #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXLINE 500 void mysort(char *word[MAXLINE]) { int i,j; char *tmp; for(i=0;;i++){ for(j=i+1;; j++){ if(strcmp(word[j],word[i])==1){ tmp=word[i]; word[i]=word[j]; word[j]=tmp; } } } } int main(void) { int i; FILE *fp; char str[MAXLINE]; fp= fopen("sample.txt", "r"); if (fp == NULL) { printf("fopen error\n"); exit(1); } while(( fgets( str, MAXLINE, fp )) != NULL) mysort(str); for(i=0;; i++) printf("%s\n", str[i]); return 0; }
- 締切済み
- C・C++・C#
- プログラミングのポインタの所の課題で、途中までやったのですが・・・
プログラミングのポインタの所の課題で、途中までやったのですが・・・ どうしてもとけません。どなたか解けるかた、ご指導お願いします。。。 課題は以下の通りです。 １．文字配列の先頭文字でソートを行って出力するプログラムを完成させよ。ただし、my_sort_stringsはポインタ配列とその要素数を引数として、登録されている文字配列を昇順に並べ替える関数である。 #include<stdio.h> #include<string.h> void print_strings(char **p, int n); void swap_strings(char **p, int i, int j); int min_index(); void my_sort_strings(); int main() { char*p[100]; char Orange[] = "orange"; char Apple[] = "apple"; char Peach[] = "peach"; char Grape[] = "grape"; char Melon[] = "melon"; int i; p[0] = Orange; p[1] = Apple; p[2] = Peach; p[3] = Grape; p[4] = Melon; print_strings(p, 5); my_sort_strings(); print_strings(p, 5); return 0; } void print_strings(char **s, int n) { int i; printf("-----------begin: print_string ----------\n"); printf("print_string: s's value: %08x\n", s); for(i = 0; i < n; i++) { printf("(s[%d])'s value: %08x\n", i, s[i]); printf("(s[%d])'s address: %08x\n", i, &s[i]); } for(i = 0; i < n; i++) printf("%d: %s\n, i, s[i]"); printf("-----------end: print_strings-----------\n"); } void swap_strings(char **p, int i, int j) { char *tmp; tmp = p[i]; p[i] = p[j]; p[j] = tmp; } int min_index(char **a, int n) { } void my_sort_strings( ) { } ２．課題１を元に文字配列の2文字目以降の順序まで考慮した辞書式順序でソートを行うプログラムを作成せよ。関数名はlexicographic_sortとする。
- 締切済み
- C・C++・C#
お礼
分かりました、ｓ[]の部分を重点的に見ていじってみます。。 ありがとうございます。。