お世話になります。
C言語を勉強していまして授業課題でクイックソート(再帰型)の比較総数を計算する問題が正答しません。カウントの仕方をご教示いただけましたら幸いです。
何卒よろしくお願いいたします。
typedef int value_type;
value_type med3(value_type x, value_type y, value_type z) {
if (x < y) {
if (y < z) return y;
else if (z < x) return x;
else return z;
} else {
if (z < y) return y;
else if (x < z) return x;
else return z;
}
}
// [quicksort ] a = 対象配列 left = 開始位置 right = 終了位置
void quicksort(value_type a[], int left, int right) {
if (left < right) {
int i = left, j = right;
value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2
while (1) { // a[] を pivot 以上と以下に分ける
while (a[i] < pivot) i++; // a[i] >= pivot 位置検索
while (pivot < a[j]) j--; // a[j] <= pivot 位置検索
if (i >= j) break;
tmp = a[i]; a[i] = a[j]; a[j] = tmp; // a[i], a[j] 交換
i++; j--;
}
quicksort(a, left, i - 1); //分けた左側--再帰並べ替え
quicksort(a, j + 1, right); //分けた右側--再帰並べ替え
}
}
No.1ベストアンサー
- 回答日時:
まず、処理手順を日本語で考え、それを日本語の箇条書きや何らかのチャート図(ご存じなら)に書き表しましょぅ。
その際、「比較回数」とは何処で何をカウントすればよいかを考えましょう。
注意点としてはif条件に当てはまらなかった場合、whileループの脱出条件に該当した場合も「比較回数」に入らないのか?。。。という点です。そこをしっかり考えてとはどこの何をカウントすればよいかを決めましょう。
プログラムは思った通りには動きません。作った通りに動きます。
それを念頭に不備な点を洗い出しましょう。
[蛇足]
ソースコードを書く際はタブ付けを上手に使うとある{}の範囲がどこからどこまでなのかがわかりやすくなり焼いた後に読みやすくかつミスを防ぎやすいものとなります。
あと、関数中で使用する変数はその変数が必要になったところで宣言するのではなく、関数の最初で宣言しましょう。構造的にもスッキリし、後から読みやすいものとなります。
参考まで。
ご丁寧に教えていただきましてありがとうございます。
一度チャート図を書いて再度整理したいと思います。
「if条件に当てはまらなかった場合、whileループの脱出条件に該当した場合」
↑↑↑
ここだと思います。見逃していました。比較という意味を理解しておりませんでした。
タブ付けとは コメントのことでしょうか?
すこし調べさせていただきます。
微に細にご指導いただき感謝申し上げます。
助かりました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- JavaScript HTMLでJavaScriptを使ってパスワードの強化判定のプログラムを作成しています。 一通り作っ 2 2022/10/19 01:41
- JavaScript 画像の表示位置 3 2022/12/23 08:25
- JavaScript clear機能を失わずにファイルアップロード機能を作成したい 3 2023/06/10 16:12
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- PHP PHPで画像の渡しが上手く行きません。 1 2023/02/02 09:39
- JavaScript アップロードファイルの種類によって処理を分岐させたいのですが書き方が分からずアドバイスお願いします 4 2023/06/17 19:12
- JavaScript 1日1回引けるJavaScriptおみくじについて 1 2022/12/12 22:28
- JavaScript プログラムがうまく動きませんレビューお願いします 1 2022/07/10 05:08
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
ラジオボタンの選択で解答・点...
-
テキストボックスに入力された...
-
マクロ オブジェクト変数With...
-
全角の縦書きが一定文字数で改...
-
フレーム内のJavaスクリプトの...
-
javascriptでhiddenに二次元配...
-
クリックの度に加算していくには?
-
プルダウンから移動時のフレー...
-
フォーム内で記入したクエリ送...
-
正規表現で複数マッチ条件で悩...
-
【javascript・PHP】プルダウン...
-
javascriptでセレクトボックス...
-
Jvasvriptのlengthで個数が取得...
-
return trueとreturn falseの用...
-
VBScriptでpingを実行(ブラウザ...
-
UWSCのIE操作でプルダウンを選...
-
親子連動型のselectを設置し、...
-
VBScript
-
プルダウン 項目が多いので先頭...
-
submitボタン押下時にPOSTされ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
hiddenのvalueの値を変えたい
-
value内に変数を入れたい
-
複数のsubmitボタンで押された...
-
3桁区切りのカンマをつけたい...
-
VB.NET DateTimeの型について
-
javascriptでhiddenに二次元配...
-
テキストボックスに入力された...
-
eval()を使わずに数値を取得し...
-
引数に数値、文字列の混在
-
クイズ作成:15個の問題から5個...
-
sessionStorageを調べています。
-
setIntervalの間隔を途中で変更...
-
javascriptにてHTMLのhiddenエ...
-
Pythonで会員サイトの自動ログ...
-
セレクトボックスの初期選択状...
-
name属性が同じフォームが複数...
-
ラジオボタンの選択で解答・点...
-
商品コードを入れたら自動で商...
-
演算対象の数字と演算子を入力...
-
フォームで入力した値を別のフ...
おすすめ情報
zircon3様
おっしゃられた通りです。
while( 条件式 )の中のこれから比較しますよと言うのを総比較数と言います。比較した結果は条件に合致したものだけでした。
大切なことを気づかせていただき深く御礼申し上げます。
ベストアンサーに選ばせていただきました。