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

質問

配列要素から基準値(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 · ベストアンサー

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さんの意見を参考にしてみたら、できました。
ありがとうございました。

回答No.2

keikan

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

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

補足

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

回答No.1

keikan

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とｊがずれるのでそれ以降交換が始まります。
この辺に何か問題はありませんか？

補足

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