中央値(median)を使用しての選択法(selection sort)

質問

中央値(median)を使用して、選択法により、K番目に小さい要素を見つけるプログラムを作成しようとしていますが、なかなかうまくいかず困っています。どなたか助けていただきたく。以下は作成しましたプログラムです。質問内容欄に入りきらない所は補足に掲載しますのでよろしく御願いいたします。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

//int pivotpoint;

int minimum(int i, int j)
{
if(i<=j)
return i;
else
return j;
}

void partition2(int *s, int low, int high, int *pivotpoint)
{
const int arraysize = high-low+1;
const int r=(arraysize/5)+1;
int i,j,mark,first,last;
int pivotitem;
int t[5];
int x,y,tmp;

//t=(int *)malloc(5);
for(i=1;i<=r;i++){
first=low+5*i-5;
last=minimum(low+5*i-1,arraysize);
for(x=first;x<last;x++){
for(y=x+1;y<=last;y++){
if(s[x]>s[y]){
tmp=s[x];
s[x]=s[y];
s[y]=tmp;
}
}
}
t[i]=s[first+2];
}
pivotitem=select(r,t,(r+1)/2);
j=low;
for(i=low;i<=high;i++)
if(s[i]==pivotitem){
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
mark=j;
j++;
}
else if(s[i]<pivotitem){
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
j++;
}
*pivotpoint=j-1;
tmp=s[mark];
s[mark]=s[j-1];
s[j-1]=tmp;
}

int selection2(int *s,int low,int high,int k)
{
int pivotpoint;
if(high==low)
return s[low];
else{
partition2(s,low,high,&pivotpoint);
if(k==pivotpoint)
return s[pivotpoint];
else if(k<pivotpoint)
return selection2(s,low, pivotpoint-1,k);

回答No.3

cherry_moon

>配列要素を５つずつグループにしてそれぞれのグループの中央値（median)を決めて、そのそれぞれの中>央値のなかでの中央値を決めてそれを基準にK番目に小さい要素を見つけるというものです。
>よろしく御願いいたします。

アルゴリズムの前に、それぞれの関数の外部仕様がわかりません。

minimum： i と j の小さい方を返す。
selection2: 配列 s の low 番目から high 番目の中で、k 番目に小さい要素を返す。
partition2: 配列 s の low 番目から high 番目の要素を *pivotpoint の値より小さいものが *pivotpoint の値より若い番号になるように並び替える。
select: 長さ n の配列 s の k 番目に小さい要素を返す。

ですか？ もし違うなら訂正お願いします。
あってるなら selection2 と partition2 の内部仕様を教えてください。

お礼

cherry moon さん
返事がおそくなりすいませんでした。
私もずっと考えていましたが、やっとできました。
教えていただいたデバックのやりかたでなんとかできました。
ありがとうございました

回答No.2

cherry_moon

直接の回答はわかりませんでした。ごめんなさい。
代わりに、デバッガがないということなので、簡単なデバッグの方法を何点か。

うまく動かない間は、入力をランダムにせずに固定値にする。
high = 4; k = 2;
s[0] = 2; s[1] = 3; s[2] = 1; s[3] = 4;

計算途中の状態を出力してみる。その１
＃呼び出された関数の引数を出力してみました。
partition2
printf("%s: low:%d, high:%d, pivotpoint:%d?n",
__FUNCTION__, low, high, *pivotpoint);

selection2
printf("%s: high:%d, low:%d, k:%d?n",
__FUNCTION__, high, low, k);

select
printf("%s: n:%d, k:%d?n", __FUNCTION__, n, k);

計算途中の状態を出力してみる。その２
＃関数の終了時の状態＆戻り値を出力してみました。

partition2
printf("%s: ", __FUNCTION__);
for ( i=low; i<=high; i++ ) {
printf("%d ", s[i]);
}
printf("?n");

select
int ret = selection2(s,1,n,k);
printf("select %d?n",ret);
return ret;

で、実行してみたところ、こんな結果が得られました。
どこに問題があるかわかりませんか？

2 3 1 4
select: n:4, k:2
selection2: low:1, high:4, k:2
partition2: low:1, high:4, pivotpoint:-1073742768
select: n:1, k:1
selection2: low:1, high:1, k:1
select: 3
partition2: -1073742592 1 3 4
selection2: low:1, high:2, k:2
partition2: low:1, high:2, pivotpoint:4
select: n:1, k:1
selection2: low:1, high:1, k:1
select: 3
partition2: -1073742592 0
select: 0
Time=52microsec
The 2th smallest is 0

補足

配列要素を５つずつグループにしてそれぞれのグループの中央値（median)を決めて、そのそれぞれの中央値のなかでの中央値を決めてそれを基準にK番目に小さい要素を見つけるというものです。
よろしく御願いいたします。

回答No.1

cherry_moon

selectの関数の中身がないですね。
途中で切れちゃったんですかね。

こういう問題はデバッガを使うとわかりやすいですよ。

補足

cherry moonさん、申し訳ございません。質問内容欄には８００文字しか入力できないので。下に残りのプログラムを記載させていただきます。よろしく御願いいたします。
＞こういう問題はデバッガを使うとわかりやすいですよ。
すいません。デバッカをもっていないもので。

else
return selection2(s,pivotpoint+1,high,k);
}
}

int select(int n, int *s, int k)
{
return selection2(s,1,n,k);
}

main()
{
int num,i,k;
int high;
int s[10];
struct timeval t1,t2;

printf("How many elements?:");
scanf("%d",&high);
printf("?n");
printf("What is kth 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);
num=select(high,s,k);
gettimeofday(&t2,0);
printf("Time=%dmicrosec?n", t2.tv_usec-t1.tv_usec);
printf("The %dth smallest is %d?n ", k,num);

}