クイックソートアルゴリズム Javaスクリプトとサンプル

クイックソートとは？

クイックソート は、比較ソートアルゴリズムであり、 分割統治 このアプローチでは、1つの要素をピボットとして選択し、配列をピボットより小さい値を持つ部分とピボットより大きい値を持つ部分に分割し、配列全体が順序付けられるまで、それぞれの部分に同じ手順を適用します。

クイックソートは、あらゆるプログラミング言語で最も広く使われているソートアルゴリズムの1つです。 Javaスクリプトおそらく、あなたは既に内蔵のものを使用しているでしょう ソート（） メソッドなので、クイックソートの実装を別途学ぶ価値がある理由が疑問に思うかもしれません。それに答えるには、まずソートの意味とデフォルトのソートが何であるかを知る必要があります。 Javaスクリプトは実際にそうしています。

クイックソートを定義する3つの特性：

• 設置場所： 元の 配列 また、同じサイズの2つ目の配列は割り当てません。
• 再帰的: 各パーティションは、同じ関数でソートされた2つのより小さな範囲を生成します。
• 不安定: キーが同じ2つの要素は、元の相対的な順序とは異なる順序で配置される可能性があります。

並べ替えとは何ですか?

ソートとは、要素を定められた順序に並べることです。これは学校で習ったことがあるはずです。数字を小さい順に並べることは、 上昇 順序、そして大きい順から小さい順に並べることは 降順 順序。並べ替えは数値に限定されません。文字列はアルファベット順、日付は時系列順、オブジェクトは価格やスコアなど、任意のフィールドで並べ替えることができます。

ソートが重要なのは、順序付けられたデータによって処理速度が向上するからです。二分探索はO(log n)の時間で実行されますが、これは入力データがソートされている場合に限ります。重複排除、範囲クエリ、ランキング、マージ操作はすべて、データが順序付けられると大幅にコストが削減されます。そのため、どのプログラミング言語にも少なくとも1つのソートルーチンが付属しています。

デフォルトのソート Javaスクリプト

先に述べたように、 Javaスクリプトは ソート（）. 昇順にしたい小さな配列 [5,3,7,6,2,9] を用意します。 ソート（） 配列上ではまさにそのように動作するようです。

上記のスクリーンショットは、ブラウザのコンソールにソートされた配列が表示されている様子を示しています。以下は同じコードです。

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

出力：

[ 2, 3, 5, 6, 7, 9 ]

その結果は正しいが、それは偶然に過ぎない。 Array.prototype.sort() は、各要素を文字列に変換し、文字列を比較します。 比較関数を指定しない限り、この配列の値はすべて1桁の数字なので、文字列の順序が数値の順序と偶然一致します。データを変更すると、この錯覚は崩れます。

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

出力：

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

sort() 関数はどのアルゴリズムを使用しますか？

仕様書にはアルゴリズムが指定されていないため、各エンジンが独自のアルゴリズムを選択する。最新のエンジンはすべてマージベースのアルゴリズムを使用している。

• V8 (Chrome、Edge、Node.js) は ティムソート V8 7.0以降、Chrome 70で出荷されました。
• クモザル (Firefox）使用 マージソート.
• Javaスクリプトコア （Safari）も使用しています マージソート.

ES2019以降、この言語は以下を保証します。 sort() is 安定したこれは、エンジン内部での単純なクイックソートを排除します。マージベースのソートにはO(n)の補助メモリが必要であり、 Javaすべての比較にスクリプト比較器を使用。手書きの数値クイックソートは数値を直接比較し、その場でソートするため、大きな数値配列で優位に立つことができます。Node.js 22 で 1,000,000 個のランダムな整数をソートするのに約 100ミリ秒 下記のクイックソートと概ね 210ミリ秒 　 sort((a, b) => a - b).

クイックソートは、インプレースソートが必要な場合、メモリを厳密に制御する必要がある場合、あるいはソートの仕組みをしっかりと理解したい場合に、記述する価値があります。それでは、その仕組みを詳しく見ていきましょう。

クイックソートはどのように機能するのですか？

クイックソートは、コア操作を1回繰り返します。 分割範囲をどんどん狭くしていきます。手順は以下のとおりです。

1. 見つける ピボット 配列内の要素。
2. 左ポインタを範囲の最初の要素から開始します。
3. 右ポインタを範囲の最後の要素から開始します。
4. 左ポインタの位置にある要素をピボットと比較します。ピボットより小さい場合は、左ポインタを右に1ステップ移動します。左の要素がピボット以上になるまでこの操作を繰り返します。
5. 右ポインタの位置にある要素をピボットと比較します。ピボットより大きい場合は、右ポインタを左に1ステップ移動します。右ポインタの位置にある要素がピボット以下になるまでこの操作を繰り返します。
6. 左ポインタが右ポインタ以下である場合は、2つの要素を交換する。
7. 左ポインタをインクリメントし、右ポインタをデクリメントします。
8. 左インデックスが右インデックス以下である場合は、手順4から繰り返します。そうでない場合は、左ポインタのインデックスを返します。

上記の図 tracサンプル配列上でポインターの動きを確認します。ピボットより小さい要素はすべて左側に、大きい要素はすべて右側に配置されます。これは、返されるインデックスが示す位置と完全に一致します。以下のセクションでは、同じ配列を段階的に処理していきます。

ピボット要素の決定方法

ピボットの選択は、高速なクイックソートと低速なクイックソートを分ける唯一の決定です。常にピボットを選択する場合は、 最初の 要素、既にソートされた配列は最悪の分割を生成します。片側が空で、もう片側に残りのすべての要素が含まれます。これにより、アルゴリズムは O(n²) になります。 真ん中 要素（配列の長さを 2 で割った値）は、ソート済みおよび逆ソート済みの入力に対するその落とし穴を回避するため、以下のコードではそれを使用しています。

一般的なピボット戦略：

• 最初または最後の要素: コーディングは最も簡単だが、ソート済みデータに対してはO(n²)の計算量となる。
• 中間要素: ソート済み配列と逆ソート済み配列をO(n log n)で処理する優れたデフォルト設定。
• ランダム要素: 最悪の場合の入力を事前に構築することが不可能になる。
• 3つの中央値： 最初の値、真ん中の値、最後の値の中央値を取る。これは、本番環境のライブラリで一般的に用いられる方法である。

それでは、配列に対するクイックソートの手順を見ていきましょう。 【5,3,7,6,2,9].

1次のサブステップを実行します ピボットは中央の要素です。左 = 0、右 = 5 の場合、 Math.floor((5 + 0) / 2) インデックス 2 を返すので、ピボット値は 7.

2次のサブステップを実行します 配列の両端からポインタを開始します。左ポインタはインデックス 0 (値) にあります。 5）そして右ポインタはインデックス5（値）にあります 9).

3次のサブステップを実行します 左側の値をピボットと比較します。5 < 7 なので、右にインデックス 1 に移動します。3 < 7 なので、右にインデックス 2 に移動します。そこの値は 7 で、ピボットより小さくないので、左側のポインタはインデックス 2 で停止します。

4次のサブステップを実行します 右側の値をピボットと比較します。9 > 7 なので、左に移動してインデックス 4 に移動します。そこでの値は 2 で、ピボットより大きくないので、右側のポインタはインデックス 4 で停止します。

5次のサブステップを実行します 左側のインデックス（2）は右側のインデックス（4）以下なので、2つの値を交換します。配列は次のようになります。 【5,3,2,6,7,9].

6次のサブステップを実行します 両方のポインタを1つずつ内側に移動させます。これで、左のポインタはインデックス3に、右のポインタもインデックス3に位置することになります。

7次のサブステップを実行します スキャンを繰り返します。インデックス3の値は6で、6 < 7なので、左ポインタはインデックス4に進みます。インデックス3の値はピボットより大きくないので、右ポインタはインデックス3に留まります。

8次のサブステップを実行します 左インデックス（4）が右インデックス（3）よりも大きくなったので、ループが終了し、関数は戻り値を返します。 4インデックス4より前のものはすべてピボット以下であり、インデックス4以降のものはすべてピボット以上である。

その手順に基づくと、次の 2 つの操作のコードが必要です: swapping 2つの要素と範囲の分割。

Code 2つを交換する Numbers in Javaスクリプト

上記のエディタのスクリーンショットが示すように、スワップヘルパーは一時変数を使用して2つのインデックスの値を交換します。配列を直接変更し、何も返しません。

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

出力：

[ 9, 3, 7, 6, 2, 5 ]

Code パーティションを実行する

上記のスクリーンショットのコードは、ステップ1から8を関数に変換します。 loops ポインタを進めると、 if ブロックはスワップを実行し、関数は分割インデックスを返します。

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

出力：

[ 5, 3, 2, 6, 7, 9 ]
4

出力はマニュアルの手順と完全に一致します。1回のパーティションパスの後、配列は[5,3,2,6,7,9]となり、返された分割インデックスは4です。

再帰を実行する Opera生産

分割によって分割インデックスが返されたら、それを使って範囲を分割し、それぞれの半分に対してクイックソートを実行します。これが分割統治アルゴリズムと呼ばれる所以です。再帰は、すべての部分範囲に要素が1つだけ含まれるまで続き、その時点で配列全体がソートされます。

注意： クイックソートは、処理全体を通して同じ配列に対して動作します。処理中に新しい配列は作成されないため、インプレースアルゴリズムと言えます。

だからあなたは パーティション（） 上記で説明した関数を使用して、その戻り値で分割します。 配列 分割します。以下にそのコードを示します。

スクリーンショットで強調表示されている2つのガード条件に注目してください。 left < index - 1 少なくとも2つの要素が左側に残っていることを確認し、 index < right 右側についても同様であることが確認できます。これらのガードがないと、関数は単一要素の範囲で無限に自身を呼び出し続けることになります。

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

出力：

[ 2, 3, 5, 6, 7, 9 ]

クイックソートを完了する Code

スワップ、パーティション、再帰の各要素を組み合わせると、完全な実装が得られます。

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

出力：

[ 2, 3, 5, 6, 7, 9 ]

上記のスクリーンショットは、エディタに表示されたプログラム全体と、コンソールに表示されたソート済みの配列を示しています。この実装は、既にソート済みの配列、逆順にソートされた配列、重複値や同一値を含む配列、負の数、単一要素の配列、および空の配列に対して検証され、いずれの場合も正しい結果を返します。

クイックソートの時間計算量と空間計算量

各分割処理では、範囲内の各要素に一度ずつアクセスするため、1回の処理にかかるコストはO(n)です。したがって、総コストは、範囲が自明になるまでに配列を何回分割できるかによって決まります。

空間計算量はO(log n)である。 このインプレースバージョンでは、2つ目の配列は割り当てられないため、追加メモリは再帰スタックのみとなり、バランスのとれた分割によってスタックの深さは約 log₂(n) フレームに抑えられます。最悪の場合、スタックは O(n) フレームまで増大するため、非常に大きな配列ではコールスタックがオーバーフローする可能性があります。

2つの数値がこれを具体的に示しています。上記のコードで4,096個のランダムな値をソートすると、理論上のn·log₂(n)である49,152に対して約65,000回の比較が行われ、最も深い再帰は24フレームに達しましたが、log₂(4096)は12です。これらの数値はどちらも、O(n log n)アルゴリズムに期待される小さな定数係数の範囲内に収まっています。

クイックソートとその他のソート方法 Algorithms

クイックソートは唯一の選択肢となることはほとんどありません。以下の表は、よく使われる他のアルゴリズムとクイックソートを比較したものですので、データに最適なアルゴリズムを選択する際の参考にしてください。

クイックソートは、内部ループがタイトで、キャッシュに優しい連続した範囲で動作するため、実際には多くの場合、最も効果的です。O(n log n) の制約または安定した順序付けが保証されている場合はマージソートを、メモリが極めて限られている場合はヒープソートを、非常に小さい配列またはほぼソート済みの配列の場合は挿入ソートを選択してください。実用的なライブラリでは、これらのソート手法を組み合わせて使用​​することがよくあります。例えば、introsort はクイックソートで開始し、再帰が深くなりすぎた場合はヒープソートに切り替え、小さな範囲の場合は挿入ソートで終了します。

オブジェクトと文字列を素早くソートする方法

これまで示してきた実装では、値を比較します。 < (NAIST) と >これは数値に限定されます。実際のアプリケーションではソートする必要があります。 オブジェクト プロパティ、文字列のアルファベット順、または日付の時系列順による比較。解決策は、組み込みのコールバックと同様に、比較をコールバックに移動することです。 sort() ありません。

比較関数は2つの値を受け取り、最初の値が先になるべき場合は負の数を、2番目の値が先になるべき場合は正の数を、2つの値が等しい場合はゼロを返します。ハードコードされた2つの比較処理を比較関数に置き換えることで、このアルゴリズムはあらゆるデータ型で動作するようになります。

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

出力：

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

注目すべき点が3つあります。再帰ガードは現在 left >= rightこれは任意の範囲に対して正しく、外側の配列の長さに依存しません。文字列比較では、 localeCompare() アクセント付き文字や大文字・小文字が、コードポイントではなく適切に処理されるようにするためです。また、クイックソートは安定していないため、同じ給与のレコードが入れ替わる可能性があります。元の順序が重要な場合は、タイブレーク用の第2キーを使用してソートしてください。

続ける準備はできていますか？基礎を強化して Javaスクリプト紹介ポインタの仕組みを練習する Javaスクリプトループさらに詳しく調べる 実用的 Javaスクリプトコードの例実装を比較する 挿入ソート (NAIST) と ヒープソートまたは、このアルゴリズムに静的型を追加するには、 TypeScript 参照。

よくあるご質問