基準値をランダムに選んでの選択ソート

配列要素から基準値(pivot)をランダムに選び、K番目に小さい要素を検索するプログラムを書いているのですが、うまくいきません。かなり考えているのですが、何が間違っているのか全然わかりません。どなたか教えていただけないでしょうか？

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

int pivotpoint;

void partition3(int *s,int low,int high,int *pivotpoint)
{
int i,j,randspot;
int tmp;
int pivotitem;

randspot=rand()%(high+1);
pivotitem=s[randspot];
j=low;
for(i=low+1;i<=high;i++){
if(s[i]<pivotitem){
j++;
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
}
}
*pivotpoint=j;
tmp=s[low];
s[low]=s[*pivotpoint];
s[*pivotpoint]=tmp;
}

int selection3(int *s,int low,int high,int k)
{
if(low==high)
return s[low];
else{
partition3(s,low,high,&pivotpoint);
if(k==pivotpoint)
return s[pivotpoint];
else if(k<pivotpoint)
return selection3(s,low,pivotpoint-1,k);
else
return selection3(s,pivotpoint+1,high,k);
}
}

main()
{
int num,i,k;
int high;
int low=0;
int s[1000];
struct timeval t1,t2;
int seed=2;

printf("How many elements?:");
scanf("%d",&high);
printf("?n");
printf("What is the kth smallest number?:");
scanf("%d",&k);
printf("?n");
srand(seed);
for(i=0;i<high;i++){
s[i]=rand();
printf("%d ",s[i]);
}
printf("?n");

gettimeofday(&t1,0);
num=selection3(s,low,high-1,k-1);
gettimeofday(&t2,0);
printf("Time=%dmicrosec?n", t2.tv_usec-t1.tv_usec);
printf("The %dth smallest is %d?n ", k,num);
}

No.3 ベストアンサー 回答者： keikan 回答日時： 2005/02/25 16:39

partition3において

randspot=rand()%(high+1);
pivotitem=s[randspot];

のところでせっかくselection3の呼び出しでｌｏｗとhighを制限しているにもかかわらずｓ[]に対していつでもすべてのアイテムの中から抽出しています。

下記に変更
randspot=rand()%(high-low+1);
pivotitem=s[randspot+low];

あたりになるでしょうか。



void partition3(int *s,int low,int high,int *pivotpoint1){
int i,j,randspot;
int tmp;
int pivotitem;

randspot=rand()%(high-low+1);

//ここで基準値の保管場所がわからなくなるのを防止するため最後のアイテムと交換しておく
pivotitem=s[low+randspot];
s[low+randspot]=s[high];
s[high]=pivotitem;

j=low;
//printf(" P=%d \n",pivotitem);

for(i=low;i<high;i++){
if(s[i]<pivotitem){
tmp=s[j];
s[j]=s[i];
s[i]=tmp;
j++;
}
}

*pivotpoint1=j;
//ここで基準値のはいる場所が決まったので待避しておいた値と交換する。
tmp=s[j];
s[j]=pivotitem;
s[high]=tmp;

}

この回答へのお礼

レスかなり遅れてもうしわけございませんでした。
keikanさんの意見を参考にしてみたら、できました。
ありがとうございました。

お礼日時：2005/03/31 07:45

No.2 回答者： keikan 回答日時： 2005/02/25 09:37

partition3はなにをしようとしていますか？＾＾

どのようにソートしたいとお考えですか？＾＾

この回答への補足

ランダムに基準値(pivot)を決めて、その基準値よりも小さい要素を左に、大きい要素を右に分けたいのですが。

補足日時：2005/02/25 10:04

No.1 回答者： keikan 回答日時： 2005/02/24 17:30

j=low;

for(i=low+1;i<=high;i++){
if(s[i]<pivotitem){
j++;
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
}
}

ここのルーチンでlow=0のときiの初期値はlow+1で１です。このときs[i]<pivotitemを満たしたとき
ｊ＋＋でj=1です。結果として
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
この交換はなにもしていないことになりませんか？
このことがループの間s[i]<pivotitemであり続けたとき同じようにｊも加算されていくので交換しないままループします。

s[i]＞pivotitemであったとき初めてiとｊがずれるのでそれ以降交換が始まります。
この辺に何か問題はありませんか？

この回答への補足

具体的にはどうすればいいのでしょうか？教えてください。

補足日時：2005/02/25 02:41