配列要素から基準値(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ベストアンサー
- 回答日時:
partition3において
randspot=rand()%(high+1);
pivotitem=s[randspot];
のところでせっかくselection3の呼び出しでlowとhighを制限しているにもかかわらずs[]に対していつでもすべてのアイテムの中から抽出しています。
下記に変更
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
- 回答日時:
partition3はなにをしようとしていますか?^^
どのようにソートしたいとお考えですか?^^
No.1
- 回答日時:
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で1です。このときs[i]<pivotitemを満たしたとき
j++でj=1です。結果として
tmp=s[i];
s[i]=s[j];
s[j]=tmp;
この交換はなにもしていないことになりませんか?
このことがループの間s[i]<pivotitemであり続けたとき同じようにjも加算されていくので交換しないままループします。
s[i]>pivotitemであったとき初めてiとjがずれるのでそれ以降交換が始まります。
この辺に何か問題はありませんか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- FX・外国為替取引 mql4のコンパイルエラー箇所の修正お願いします。 1 2023/03/15 16:14
- C言語・C++・C# 質問です 下記のコードを分かりやすく解説お願いします 初心者です #include ‹stdio.h 3 2022/05/26 22:03
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- C言語・C++・C# C言語でif文が予想と違う動きをする件について7 4 2023/03/20 00:26
- C言語・C++・C# C言語 コードを書いたのですが上手く実行出来なかったです。どこが間違ってますか? 【作成したいもの】 1 2022/05/04 11:36
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
比較回数と交換回数表示について
-
nCmの関数
-
複数桁10進数の*桁目だけを抽出...
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語 配列と関数の練習問題
-
c言語
-
std::set<int> で、ある値が何...
-
卒業研究でよく分からないとこ...
-
C言語 エラーの原因がわからな...
-
DLLをGetProcAddress()で実行で...
-
【C++】関数ポインタの使い方
-
read関数をノンブロッキングで...
-
C言語における対称行列の作り方...
-
構造体の勉強中です 合計点の高...
-
C言語です。
-
C言語での引数の省略方法
-
困ってます…nCrを求めるC言語...
-
C++でvectorにテキストファイル...
-
プログラミング
-
素数 再帰関数
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
「指定されたキャストは有効で...
-
C言語 配列と関数の練習問題
-
複数桁10進数の*桁目だけを抽出...
-
(int *)の意味
-
if と配列の組み合わせ
-
ラップ関数とはどんなものですか?
-
卒業研究でよく分からないとこ...
-
【C++】関数ポインタの使い方
-
c言語
-
足して100になるような乱数のア...
-
C言語初心者です、、、お助けく...
-
数字列を3桁ごとにカンマで区切...
-
C言語 エラーの原因がわからな...
-
実数の整数部,小数部の取得
-
課題でつまってます・・・
-
商と剰余を同時に求める(C言語)
-
C言語の配列をC++のvectorに高...
-
std::set<int> で、ある値が何...
おすすめ情報