(メモリ容量の取得)・クイックソートクイックソートは最も高速であるといわれているソート法です。この方法は、並び替える値の中から基準の値を決め、その基準値より小さい値を集めたグループ、大きい値を集めたグループを作成していき、さらに、各グループの中の値から基準値を決めて同様の方法でグループを分割していきます。分割の結果、グループ内の値が一つになったとき、その値が確定されます。それでは、具体的な値でクイックソートの動きをみていきましょう。以下は、並び替える前のデータです。この中から基準値を決めます。ここでは、配列に格納されているほぼ中心の値を基準値とします。データ数が10なので、配列の添え字は0~9です。ここでは、添え字の最大値9を2で割った整数部の4(左から5番目)に格納されている値12を基準値としています。次に、配列の先頭(添え字:0)から後方に向けて基準値以上の値を探します。その後、配列の最後(添え字:9)から前方に向けて基準値以下の値を探します。この例では、配列の2番目(添え字:1)の値20が基準値12以上、配列の10番目(添え字:9)の値9が基準値12以下の値が見つかりました。この処理で値が見つかった場合、その2つの値を入れ替えます。この操作を、前方からの検索位置sが後方からの検索位置eと同じになるか、超えるまで行います。これを満たす条件は、s>=e。検索位置s=6、検索位置e=5となり、s>=e条件を満たしました。この時点で、配列の中の基準値12の前方に格納されている数字は12以下、後方に格納されている数字は12以上であることが確認できます。次に検索位置s=6、検索位置e=5でグループを分割します。ここでの分割は、2つの新しい配列を作成するのではなく、ここまでの処理を添え字0~5、添え字6~9の2つの範囲で行うことを意味しています。(下図)このように分割処理を繰り返していき、グループの値の数が1つになればその値を確定します。グループの値の数が2つの場合、2つの値の大小を比較して小さいほうから並べて値を確定します。この処理では、1つのグループの値の並びで、基準値の前方の値が全て基準値未満で、後方の値が基準値より大きい場合、検索位置sと検索位置eが同じ状態で処理を終了します。この場合、検索位置sに1を足してグループを分割します。最後にグループ内の値の数が2個以下になった場合について説明します。グループ内の値の数が1個の場合は、その値で確定です。グループ内の値の数が2個の場合は、その2つの値を比較して、前方の値が後方の値より大きければ値を入れ替えて値を確定します。2個の場合は基準値は使いません。以上が、クイックソートの考えかたです。以下は、クイックソートのJavaソースコード例です。}QuickSortの出力結果047891012131520出力結果から、元の配列の値が昇順に並び替わっていることが確認できます。それでは、ここからソースコードを解説していきます。{クラス名を、QuickSortとしています。)クイックソート行うquick_sortメソッドです。int型の配列aとint型の変数startとendに処理する範囲の添え字を指定してソートを実行します。添え字の位置クイックソートで使う変数を宣言しています。return;変数startの値がendの値以上であればreturn文でメソッドを抜けます。}処理範囲の値の数が2個の場合、単純な値の比較による値の入れ替え処理を行い、return文でメソッドを抜けます。)は、startとendが隣同士の関係であることを表し、これにより値が2個であることがわかります。];変数startとendを足して2で割った位置の配列の値を基準値を格納する変数pivotに代入しています。1;基準値との比較位置の初期値を変数sとeに代入しています。変数sにstart-1を代入しているのは、基準値の前方の値を比較する処理が、先に変数sをインクリメントした後で配列の値を比較するようにしているためです。変数eにend+1を代入している理由も同様に、先に変数eをデクリメントしているからです。}for文で無限ループ作成しています。そのループの中で、a[s]>=pivotになるsと、a[e]<=pibotになるeを求めています。sとeを求めた結果、sがe以上になったときにbreak文でループを終了するようにしています。sがe未満のときは、a[s]とa[e]の値を入れ替えます。s;for文を抜けたときのsとeが同じとき、sをインクリメントします。);範囲を2つに分けて処理を行います。その範囲はstart~eとs~endの2つで、quick_sortメソッドにそれらの範囲を渡し再帰的に処理をしていきます。}処理範囲を引数として渡さないクイックソートのメソッドです。与えられたint型の配列aの個数が1個以下であれば処理をせずメソッドをreturn文で抜けます。2個以上の場合、処理範囲を引数として渡せる再帰処理用のquick_sortメソッドに、処理範囲0~a.length-1を渡してソートを実行します。