クイックソートの再帰呼び出し後の記述について（特に配列の範囲）

質問

アルゴリズムをすこしかじってみているのですが、いきなり躓いてしまいました。詳しい方にお聞きします。クイックソートの再帰呼び出し後のプログラムの記述がよくわかりません。（特に配列の範囲）
ＱｕｉｃｋＳｏｒｔ（Ｈｅａｄ，Ｔａｉｌ）というプログラムがあるとします。最初の一連の処理が終わり、再帰呼び出しの部分で、
ＱｕｉｃｋＳｏｒｔ（Ｈｅａｄ，Ｌｅｆｔ－１）という前半部分を指定した再帰呼び出しとＱｕｉｃｋＳｏｒｔ（Ｒｉｇｈｔ＋１，Ｔａｉｌ）という後半部分を指定した再帰呼び出しがされるとします。ここまでは分かるのですが、この再帰呼び出しのプログラムの実行を記述するとなるとどうなるのでしょうか？特に分からないのはこの再帰呼び出しでさらに再帰呼び出しされるＱｕｉｃｋＳｏｒｔのカッコ内の配列の範囲がどのようになるのか、何か特別な記述はされるのかということです。あとソートの必要のないレベルまで来た場合の処理（記述）も分かりません。どなたかご教授願えないでしょうか？

回答No.2

nag0720

クイックソートは、ピボット（分割値）を決め、データをピボット以下とそれ以外の２つに分けることを繰り返す方法です。

クイックソートの手順は、

(1)ピボットを決め、データをピボット以下とそれ以外に分ける
(2)前半部分をクイックソートする（再帰呼び出し）
(3)後半部分をクイックソートする（再帰呼び出し）

これだけです。

＞特に分からないのはこの再帰呼び出しでさらに再帰呼び出しされるQuickSortのカッコ内の配列の範囲がどのようになるのか、何か特別な記述はされるのかということです。

何が分からないのかが分かりませんが、QuickSort(Head,Tail)ですることは、HeadからTailまでの区間の配列データを処理するだけです。それ以外の範囲のデータは考える必要はありません。

＞あとソートの必要のないレベルまで来た場合の処理（記述）も分かりません。

クイックソート（再帰呼び出し）するかどうかは、データ数で判断します。
データ数が１以下の場合はすでにソートされていますから、再帰呼び出しする必要はありません。

補足

理解力がなくすみません。(1)「QuickSort(Head,Tail)ですることは、HeadからTailまでの区間の配列データを処理するだけです。それ以外の範囲のデータは考える必要はありません。」とのことですが、質問で、再帰呼び出し後のＨｅａｄからＴａｉｌの配列の始端と終端を書いたのですが、これが実行されるとその次の配列の始端と終端はどう示されるかということなのですが・・あと、「クイックソート（再帰呼び出し）するかどうかは、データ数で判断します。」とお書き頂きましたが、これはプログラムでどのように記述されるのでしょうか？

回答No.1

cametan_42

http://www.codereading.com/algo_and_ds/algo/quick_sort.html