ページ 1 / 1
降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 18:36
by yunyun
ヒープソートのプログラムですが、降順にソートするプログラムに変更したいです。
コード:
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);
}
}
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 21:07
by みけCAT
yunyun さんが書きました: ↑1年前
降順にソートするプログラムに変更したいです。
すればいいでしょう。
質問はありますか?
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 21:51
by yunyun
みけCAT さんが書きました: ↑1年前
yunyun さんが書きました: ↑1年前
降順にソートするプログラムに変更したいです。
すればいいでしょう。
質問はありますか?
ヒープソートの降順がよくわからないので、質問しました。どこをどう変更するのか分かりません。
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 22:10
by box
降順ソートなんかあとでどないでもなるから、
まずは、昇順ソートを完璧にすることを
考えた方がええんとちゃいますか?
直近のコードにある
heapsort()
っていう、引数も戻り値も何もない謎の関数は
ちゃんと動くようになったんですか?
コード:
void heapsort(){
tmp = a[1];
a[1] = a[i];
a[i] = tmp;
}
ここの、何も定義してない
謎の配列
a[]
はどこを見てるんですか?
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 22:25
by box
void heapsort(){
tmp = a[1];
a[1] = a;
a = tmp;
}
おっと謎やなかった。外部変数やった。
えらいすんません。
そやけどやっぱり
tmpに入れるんが
何でa[1]固定なんかはようわかりません。
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 22:28
by box
ところで
swapとcomp
の件は解決したんですか?
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 22:33
by yunyun
box さんが書きました: ↑1年前
ところで
swapとcomp
の件は解決したんですか?
プログラムを改良したところ動きました。このプログラムは動きます。これを降順ソートにしたいと思っています。
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 22:42
by box
それやったらまず見るべきなんは
コード:
void downheap(int from,int to){
if (j+1 <= to && a[j] > a[j+1])
ここの
a[j]とa[j+1]の
不等号を逆向きにしてみることちゃいますか?
自分やったらまずそうします。それであかんかったらまた別の手立てを考えるっちゅうことで。
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 22:45
by yunyun
box さんが書きました: ↑1年前
それやったらまず見るべきなんは
コード:
void downheap(int from,int to){
if (j+1 <= to && a[j] > a[j+1])
ここの
a[j]とa[j+1]の
不等号を逆向きにしてみることちゃいますか?
自分やったらまずそうします。それであかんかったらまた別の手立てを考えるっちゅうことで。
if分の中は試しました。
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 22:56
by box
if分の中は試しました。
そうやったら、今回のスレッドの先頭で
「今のコード全体はこうです。そやけど降順ソートできません」
っていうのをハッキリ示さなあきません。なんかまどろっこしい。
全部さらけ出さんと、的確な回答はいつまでたっても来ないですよ。
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月21日(火) 23:11
by yunyun
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);
}
}
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月22日(水) 07:29
by みけCAT
昇順ソートのプログラムを作って、最後に配列の中身を逆順にする処理を入れれば、降順ソートになるでしょう。
Re: 降順ソートのプログラムにしたい
Posted: 2022年6月22日(水) 20:20
by box
下記のコードを実行したとき、
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;
}