アルゴリズムをすこしかじってみているのですが、いきなり躓いてしまいました。詳しい方にお聞きします。クイックソートの再帰呼び出し後のプログラムの記述がよくわかりません。(特に配列の範囲)
QuickSort(Head,Tail)というプログラムがあるとします。最初の一連の処理が終わり、再帰呼び出しの部分で、
QuickSort(Head,Left-1)という前半部分を指定した再帰呼び出しとQuickSort(Right+1,Tail)という後半部分を指定した再帰呼び出しがされるとします。ここまでは分かるのですが、この再帰呼び出しのプログラムの実行を記述するとなるとどうなるのでしょうか?特に分からないのはこの再帰呼び出しでさらに再帰呼び出しされるQuickSortのカッコ内の配列の範囲がどのようになるのか、何か特別な記述はされるのかということです。あとソートの必要のないレベルまで来た場合の処理(記述)も分かりません。どなたかご教授願えないでしょうか?
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
クイックソートは、ピボット(分割値)を決め、データをピボット以下とそれ以外の2つに分けることを繰り返す方法です。
クイックソートの手順は、
(1)ピボットを決め、データをピボット以下とそれ以外に分ける
(2)前半部分をクイックソートする(再帰呼び出し)
(3)後半部分をクイックソートする(再帰呼び出し)
これだけです。
>特に分からないのはこの再帰呼び出しでさらに再帰呼び出しされるQuickSortのカッコ内の配列の範囲がどのようになるのか、何か特別な記述はされるのかということです。
何が分からないのかが分かりませんが、QuickSort(Head,Tail)ですることは、HeadからTailまでの区間の配列データを処理するだけです。それ以外の範囲のデータは考える必要はありません。
>あとソートの必要のないレベルまで来た場合の処理(記述)も分かりません。
クイックソート(再帰呼び出し)するかどうかは、データ数で判断します。
データ数が1以下の場合はすでにソートされていますから、再帰呼び出しする必要はありません。
この回答への補足
理解力がなくすみません。(1)「QuickSort(Head,Tail)ですることは、HeadからTailまでの区間の配列データを処理するだけです。それ以外の範囲のデータは考える必要はありません。」とのことですが、質問で、再帰呼び出し後のHeadからTailの配列の始端と終端を書いたのですが、これが実行されるとその次の配列の始端と終端はどう示されるかということなのですが・・あと、「クイックソート(再帰呼び出し)するかどうかは、データ数で判断します。」とお書き頂きましたが、これはプログラムでどのように記述されるのでしょうか?
補足日時:2009/07/20 16:28お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) 十進BASICでの再帰についての質問です。 2 2022/11/18 09:17
- その他(プログラミング・Web制作) FORTRAN77の配列(除算) 2 2023/02/01 14:34
- エアコン・クーラー・冷暖房機 エアコンの修理について 3 2023/02/24 19:26
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- gooのスマホ lineの着信画面ならず「不在着信」になる 1 2022/07/07 12:31
- 警察・消防 暴行の被害届について。自分は暴行の被害者です。 警察に暴行の被害届を出した後に、検察庁から連絡があり 6 2023/05/26 03:02
- Visual Basic(VBA) 前回ご教授いただいたコードに覚えたてのループ処理で品名りんごAから順に20回for nextでループ 7 2023/01/13 22:01
- その他(生活家電) ミュート機能のあるインターホンでも、外で訪問者が呼び出しベルを押したらピンポンという音は鳴りますか? 3 2023/07/18 10:41
- 世界情勢 グレート・リセット「世界のエネルギーや食糧を生み出す土地は、誰の物か?」 1 2022/11/08 16:55
- 会社・職場 メンタル不調者からのいじめ嫌がらせをどう改善したらよいか 6 2022/04/10 21:37
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
VBA 変数名に変数を使用したい。
-
C#でbyte配列から画像を表示さ...
-
COBOLの基本的な事なので...
-
VB6からの移行したいけど、VB.N...
-
vba フィルター 複数条件 3つ以...
-
2次元配列の初期値
-
テキストボックの文字を一行ず...
-
配列の中の最大値とそのインデ...
-
構造体配列の特定のメンバーをF...
-
Excel2010のinputboxで複数デー...
-
VB.NETの配列にExcelから読み込...
-
Segmentation Fault (メモリ制限?)
-
エクセルでXY座標に並べられた...
-
OutOfMemoryExceptionの回避策...
-
Redim とEraseの違いは?
-
コンボボックスのインデックス...
-
定数配列の書き方
-
C#で作成したdllをVBScriptで使...
-
画像の座標取得
-
オブジェクト名を変数で参照で...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VBA 変数名に変数を使用したい。
-
Excel2010のinputboxで複数デー...
-
vba フィルター 複数条件 3つ以...
-
C#でbyte配列から画像を表示さ...
-
配列のペースト出力結果の書式...
-
Dir関数で読み取り順を操作でき...
-
エクセルでXY座標に並べられた...
-
VBAで配列引数を値渡しできない...
-
C++で作成したDLLにVBAから配列...
-
構造体配列の特定のメンバーをF...
-
OutOfMemoryExceptionの回避策...
-
大量の変数を定義するにはどう...
-
VBAでMODE関数をつくる
-
VBScriptでCSVファイルを読み出...
-
定数配列の書き方
-
Segmentation Fault (メモリ制限?)
-
Excelのメモリ(配列)の上限は2G...
-
Redim とEraseの違いは?
-
CheckBoxの配列化
-
配列の中の最大値とそのインデ...
おすすめ情報