降順ソートのプログラムにしたい

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
yunyun

降順ソートのプログラムにしたい

#1

投稿記事 by yunyun » 1年前

ヒープソートのプログラムですが、降順にソートするプログラムに変更したいです。

コード:

void downheap(int from,int to){
    int i, j;
    int val;
    
    val = a[from];
    i = from;
    while (i <= to/2){
        j = i*2;
        if (j+1 <= to && a[j] > a[j+1])
            j++;
            comp++;
        
     
        if(val <= a[j])
        break;
        

        a[i] = a[j];
        i = j;
        
    }
    a[i] = val;
    
}
void heapsort(){
        int i;
        int tmp;
        
        
        
        for (i = n/2; i >= 1; i--)
            downheap(i,n);
        
        for (i = n; i >= 2; i--){
            swap++;
            tmp = a[1];
            a[1] = a[i];
            a[i] = tmp;
            downheap(1, i-1);
            
        }
}

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 降順ソートのプログラムにしたい

#2

投稿記事 by みけCAT » 1年前

yunyun さんが書きました:
1年前
降順にソートするプログラムに変更したいです。
すればいいでしょう。
質問はありますか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

yunyun

Re: 降順ソートのプログラムにしたい

#3

投稿記事 by yunyun » 1年前

みけCAT さんが書きました:
1年前
yunyun さんが書きました:
1年前
降順にソートするプログラムに変更したいです。
すればいいでしょう。
質問はありますか?
ヒープソートの降順がよくわからないので、質問しました。どこをどう変更するのか分かりません。

box
記事: 2002
登録日時: 13年前

Re: 降順ソートのプログラムにしたい

#4

投稿記事 by box » 1年前

降順ソートなんかあとでどないでもなるから、
まずは、昇順ソートを完璧にすることを
考えた方がええんとちゃいますか?

直近のコードにある
heapsort()
っていう、引数も戻り値も何もない謎の関数は
ちゃんと動くようになったんですか?

コード:

void heapsort(){
            tmp = a[1];
            a[1] = a[i];
            a[i] = tmp;
}
ここの、何も定義してない
謎の配列
a[]
はどこを見てるんですか?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

box
記事: 2002
登録日時: 13年前

Re: 降順ソートのプログラムにしたい

#5

投稿記事 by box » 1年前

void heapsort(){
tmp = a[1];
a[1] = a;
a = tmp;
}

おっと謎やなかった。外部変数やった。
えらいすんません。
そやけどやっぱり
tmpに入れるんが
何でa[1]固定なんかはようわかりません。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

box
記事: 2002
登録日時: 13年前

Re: 降順ソートのプログラムにしたい

#6

投稿記事 by box » 1年前

ところで
swapとcomp
の件は解決したんですか?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

yunyun

Re: 降順ソートのプログラムにしたい

#7

投稿記事 by yunyun » 1年前

box さんが書きました:
1年前
ところで
swapとcomp
の件は解決したんですか?
プログラムを改良したところ動きました。このプログラムは動きます。これを降順ソートにしたいと思っています。

box
記事: 2002
登録日時: 13年前

Re: 降順ソートのプログラムにしたい

#8

投稿記事 by box » 1年前

それやったらまず見るべきなんは

コード:

void downheap(int from,int to){
        if (j+1 <= to && a[j] > a[j+1])
ここの
a[j]とa[j+1]の
不等号を逆向きにしてみることちゃいますか?
自分やったらまずそうします。それであかんかったらまた別の手立てを考えるっちゅうことで。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

yunyun

Re: 降順ソートのプログラムにしたい

#9

投稿記事 by yunyun » 1年前

box さんが書きました:
1年前
それやったらまず見るべきなんは

コード:

void downheap(int from,int to){
        if (j+1 <= to && a[j] > a[j+1])
ここの
a[j]とa[j+1]の
不等号を逆向きにしてみることちゃいますか?
自分やったらまずそうします。それであかんかったらまた別の手立てを考えるっちゅうことで。
if分の中は試しました。

box
記事: 2002
登録日時: 13年前

Re: 降順ソートのプログラムにしたい

#10

投稿記事 by box » 1年前

if分の中は試しました。
そうやったら、今回のスレッドの先頭で
「今のコード全体はこうです。そやけど降順ソートできません」
っていうのをハッキリ示さなあきません。なんかまどろっこしい。
全部さらけ出さんと、的確な回答はいつまでたっても来ないですよ。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

yunyun

Re: 降順ソートのプログラムにしたい

#11

投稿記事 by yunyun » 1年前

box さんが書きました:
1年前
if分の中は試しました。
そうやったら、今回のスレッドの先頭で
「今のコード全体はこうです。そやけど降順ソートできません」
っていうのをハッキリ示さなあきません。なんかまどろっこしい。
全部さらけ出さんと、的確な回答はいつまでたっても来ないですよ。
今はこのような感じです。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX_ELEMENTS    500 /* 最大のデータ数 */  
#define OFFSET          100   /* データ数の増分値 */  
#define MAX_LINES       10    /* 関数の最大行数 */  
#define MAX_HEAP        500
  
//int  a[MAX_ELEMENTS] ;        /* 探索するデータ領域 */
int a[MAX_HEAP+1];   
  
int  comp, swap;        /* 比較回数、交換回数を格納する変数 */  

int n;

  
void downheap(int from,int to); 
void heapsort(); 
void init_step(void);  
void print_step(int);  
void print_header(char *);  
int sorted(int);  
  
int main(void){  
  int i;  
  //int n; /* データ数 */  
  
  srandom(time(0));           /* 乱数の種を初期設定する */  
  
 /* ランダム入力の場合 */  
  print_header("random");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = random() % n ;    /* 配列要素に乱数値を設定する */  
    }  
  
    heapsort();         /* ヒープソートを実行 */  
 
    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */
 
 
    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
 /* 昇順にソートされた入力の場合 */  
  print_header("ascending order");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = i ;               /* 配列要素に昇順のデータ値を設定する */  
    }  
  
    heapsort();         /* ヒープソートを実行 */  
 
    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */
 
    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
 /* 降順にソートされた入力の場合 */  
  print_header("descending order");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = n - i ;           /* 配列要素に降順のデータ値を設定する */  
    }  
  
    heapsort();         /*  ヒープソートを実行 */  
 
    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */
 
    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
  return 0;  
}  
  
void init_step(void){  
  swap = 0; comp = 0;  
}  
  
void print_header(char *s) {  
  printf("%s\n   n, 比較回数, 交換回数, チェック",s);  
  printf("\n");  
}  
  
void print_step(int n){  
  printf("%4d, %8d, %8d", n, comp, swap);  
  
  if (sorted(n)) { /* 配列が昇順に整列されているかチェック */  
    printf(", sorted\n");  
  } else {  
    printf(", unsorted\n");  
  }  
}  
  
int sorted(int n) {  
  int i;  
  for (i=0; i < n-1; i++)  
    if (a[i] < a[i+1]) return 0;  
  return 1;  
}  

//int k = n;

void downheap(int from,int to){
    int i, j;
    int val;
    
    val = a[from];
    i = from;
    while (i <= to/2){
        j = i*2;
        if (j+1 <= to && a[j] > a[j+1])
            j++;
            comp++;
        
     
        if(val <= a[j])
        break;
        

        a[i] = a[j];
        i = j;
        
    }
    a[i] = val;
    
}
void heapsort(){
        int i;
        int tmp;
        
        for (i = n/2; i >= 1; i--)
            downheap(i,n);
        
        for (i = n; i >= 2; i--){
            swap++;
            tmp = a[1];
            a[1] = a[i];
            a[i] = tmp;
            downheap(1, i-1);
            
        }
}


アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 降順ソートのプログラムにしたい

#12

投稿記事 by みけCAT » 1年前

昇順ソートのプログラムを作って、最後に配列の中身を逆順にする処理を入れれば、降順ソートになるでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 2002
登録日時: 13年前

Re: 降順ソートのプログラムにしたい

#13

投稿記事 by box » 1年前

下記のコードを実行したとき、
50
40
30
20
10
って出力する関数sortArray()の中身を書けますか?>質問者さん

コード:

#include <stdio.h>

#define N (5)

void sortArray(int *src, int *dest, int n)
{
    /* ここに、配列srcを降順に並べ直して配列destに格納するコードを書く */
}

void printArray(int *a, int n)
{
    int i;

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

int main(void)
{
    int arrA[N] = { 10, 20, 30, 40, 50 }, arrB[N];

    sortArray(arrA, arrB, N);
    printArray(arrB, N);
    return 0;
}
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

返信

“C言語何でも質問掲示板” へ戻る