クイックソートアルゴリズム Javaスクリプト
ジェームズ・ハートマン
クイックソートとは？
クイックソート アルゴリズムは分割統治アプローチに従います。何らかの条件に基づいて要素を小さな部分に分割し、分割された小さな部分に対してソート操作を実行します。
クイックソートアルゴリズムは、あらゆるプログラミング言語で最もよく使用され、人気のあるアルゴリズムの1つです。しかし、 Javaスクリプト開発者なら、聞いたことがあるかもしれません ソート（） すでに利用可能 Javaスクリプト。それでは、このクイックソートアルゴリズムの必要性について考えたかもしれません。これを理解するには、まずソートとは何か、そしてデフォルトのソートとは何かを知る必要があります。 Java脚本。
並べ替えとは何ですか?
ソートとは、要素を必要な順序に並べることに他なりません。学校や大学時代にこのことを学んだことがあるかもしれません。数字を小さい順 (昇順) に並べたり、大きい順 (降順) に並べたりすることは、これまで見てきたとおりで、ソートと呼ばれています。
デフォルトの並べ替え Javaスクリプト
先に述べたように、 Javaスクリプトには ソート（）。 [5,3,7,6,2,9] のような要素の配列が少ない例を考えて、この配列要素を昇順に並べ替えたいとします。 ただ電話してください ソート（） items 配列に対して、配列要素を昇順に並べ替えます。
コード：
var items = [5,3,7,6,2,9]; console.log(items.sort()); //prints [2, 3, 5, 6, 7, 9]
デフォルトのsort()ではなくクイックソートを選択する理由は何ですか? Javaスクリプト
sort()は望み通りの結果をもたらしますが、問題は配列要素の並び替え方法にあります。 Javaスクリプトの使用 挿入ソート by ChromeのV8エンジン マージソート by Mozilla Firefox Safari.
ただし、これは、多数の要素を並べ替える必要がある場合には適していません。 したがって、解決策は、大規模なデータセットに対してクイック ソートを使用することです。
したがって、完全に理解するには、クイック ソートがどのように機能するかを知る必要があります。ここで、それを詳しく見てみましょう。
クイックソートとは何ですか？
クイックソートが続きます 分割統治 アルゴリズム。これは、ある条件に基づいて要素を小さな部分に分割し、分割された小さな部分に対してソート操作を実行します。したがって、大規模なデータセットに適しています。ここでは、クイックソートがどのように機能するかを簡単に説明します。
- まず、呼び出す要素を選択します。 ピボット 要素。
- 次に、すべての配列要素を選択したピボット要素と比較し、ピボット要素より小さい要素が左側に配置され、ピボット要素より大きい要素が右側に配置されるように配置します。
- 最後に、ピボット要素の左側と右側の要素に対して同じ操作を実行します。
以上がクイックソートの基本概要です。 ここでは、クイック並べ替えを実行するために実行する必要がある手順を XNUMX つずつ説明します。
クイックソートの仕組み
- まず、 "ピボット" 配列内の要素。
- 配列の最初の要素から左ポインタを開始します。
- 右ポインタを配列の最後の要素から開始します。
- 要素が指している要素を左ポインタと比較し、それがピボット要素より小さい場合は、左ポインタを右に移動します (左のインデックスに 1 を追加します)。 左側の要素がピボット要素以上になるまでこれを続けます。
- 要素が指す要素を右ポインターと比較し、それがピボット要素より大きい場合は、右ポインターを左に移動します (右のインデックスから 1 を減算します)。 右側の要素がピボット要素以下になるまでこれを続けます。
- 左ポインタが右ポインタ以下であるかどうかを確認し、これらのポインタの位置にある要素を交換します。
- 左ポインタをインクリメントし、右ポインタをデクリメントします。
- 左ポインタのインデックスがまだ右ポインタのインデックスより小さい場合は、プロセスを繰り返します。 それ以外の場合は、左ポインタのインデックスを返します。
それでは、例を挙げてこれらの手順を見てみましょう。 ソートする必要がある要素の配列が [5,3,7,6,2,9] であると考えてみましょう。
ピボット要素を決定する
ただし、クイック並べ替えを進める前に、ピボット要素の選択が重要な役割を果たします。 最初の要素をピボット要素として選択すると、ソートされた配列のパフォーマンスが最悪になります。 したがって、ピボット要素として中央の要素 (配列の長さを 2 で割ったもの) を選択することが常に推奨されており、同様に行います。
ここでは、例 [5,3,7,6,2,9] で示されているクイック ソートを実行する手順を示します。
1次のサブステップを実行します ピボットを中間要素として決定します。 それで、 7 ピボット要素です。
2次のサブステップを実行します 左ポインタと右ポインタをそれぞれ配列の最初と最後の要素として開始します。 したがって、左ポインタが指しているのは、 5 インデックス 0 で右ポインタが指しているのは 9 インデックス 5 にあります。
3次のサブステップを実行します 左ポインタの要素をピボット要素と比較します。5 < 6 なので、左ポインタを右のインデックス 1 にシフトします。
4次のサブステップを実行します ここでも、3 < 6 なので、左ポインターを 7 つ右のインデックスにシフトします。したがって、6 > 2 になったので、左ポインターの増分が停止し、左ポインターはインデックス XNUMX になります。
5次のサブステップを実行します ここで、右ポインターの値をピボット要素と比較します。 9 > 6 なので、右ポインタを左に移動します。 2 < 6 になったので、右ポインタの移動を停止します。
6次のサブステップを実行します 左右のポインターに存在する両方の値を相互に交換します。
7次のサブステップを実行します 両方のポインターをもう XNUMX ステップ移動します。
8次のサブステップを実行します 6 = 6 であるため、ポインタをもう XNUMX ステップに移動し、左ポインタが右ポインタと交差するところで停止し、左ポインタのインデックスを返します。
したがって、ここでは上記のアプローチに基づいて、上記の手順で説明したように要素を交換し、配列を分割するためのコードを記述する必要があります。
2つの数字を入れ替えるコード Javaスクリプト
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); //swap 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 result = quickSort(items, 0, items.length - 1);
完全なクイックソートコード
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); //sawpping 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); //prints [2,3,5,6,7,9]
注: クイックソートは、 ああ(nlogn)。
