JavaScript でのクイックソート
マージ ソートと同様に、QuickSort は分割統治戦略を使用します。 要素をピボットとして選択し、指定された配列をその周りに分割します。
いくつかの異なる QuickSort のバリエーションがあり、それらはすべて異なる方法でピボットを選択します。
JavaScript でのクイックソート
パーティションは、quickSort() のメイン プロセスです。 配列と配列メンバー x がピボットとして与えられた場合、分割の目的は x をソート済み配列の正しい位置に配置し、すべての小さい要素を x の前に配置し、すべての大きい要素を x の後に配置することです。 ; これらはすべて線形時間で完了する必要があります。
JavaScript には sort() メソッドがあります。 sort() は望ましい結果をもたらしますが、問題は配列コンポーネントをどのようにソートするかです。
JavaScript のデフォルトの sort() は、Chrome の V8 Engine の Insertion Sort と Mozilla Firefox および Safari の Merge Sort を利用します。 ただし、多くのアイテムを並べ替える必要がある場合、これは適切ではありません。
そのため、大規模なデータセットのソリューションは、クイック ソートを使用することです。
ここでは、クイック ソートを実装するための簡単な手順を示します。
-
まず、ピボット要素と呼ばれる要素を選択します。 この要素は通常、配列の最初または最後の要素です。
-
配列の各メンバーを選択したピボット要素と比較して、ピボット要素よりも小さいコンポーネントが左側に、ピボット要素よりも大きいコンポーネントが右側に配置されるように、コンポーネントを再配置します。 これをパーティショニングと呼びます。
-
最後に、左側と右側のコンポーネントに対して行ったのと同じ手順をピボット要素に対して実行します。
並べ替えられていないアイテム [9, 1, 4, 7, 0, 2, 5, 8] を含む配列の例を使用して、これらのプロセスを詳しく見てみましょう。 最後の要素をピボットにします。
パーティショニング用の JavaScript コード:
const partitionFunction = (arratItems, left, right) => {
let pivotElement = arratItems[Math.floor((right + left) / 2)];
let leftElement = left;
let rightElement = right;
while (leftElement <= rightElement) {
while (arratItems[leftElement] < pivotElement) {
leftElement++;
}
while (arratItems[rightElement] > pivotElement) {
rightElement--;
}
if (leftElement <= rightElement) {
swapFunction(arratItems, leftElement, rightElement);
leftElement++;
rightElement--;
}
}
return leftElement;
};
スワッピングを実行する JavaScript コード:
const swapFunction = (arratItems, leftIndex, rightIndex) => {
const temp = arratItems[leftIndex];
arratItems[leftIndex] = arratItems[rightIndex];
arratItems[rightIndex] = temp;
};
左と右の配列のすべての要素が並べ替えられるまで、クイック並べ替えが使用されます。 クイック ソート中に新しい配列は作成されません。 現在の配列を使用するだけです。
したがって、上記の partitionFunction() 関数を呼び出して配列を分割する必要があります。 コードは、ここで使用できるように提供されています。
const arratItems = [9, 1, 4, 7, 0, 2, 5, 8];
const quickSortFunction = (arratItems, left, right) => {
let index;
if (arratItems.length > 1) {
index = partitionFunction(arratItems, left, right);
if (left < index - 1) {
quickSortFunction(arratItems, left, index - 1);
}
if (index < right) {
quickSortFunction(arratItems, index, right);
}
}
return arratItems;
};
// Initial call to quick sort function
const result = quickSortFunction(arratItems, 0, arratItems.length - 1);
console.log(result);
JavaScript と互換性のあるブラウザーで上記のコード行を実行します。 次の結果が表示されます。
出力：
[0, 1, 2, 4, 5, 7, 8, 9]
Shraddha is a JavaScript nerd that utilises it for everything from experimenting to assisting individuals and businesses with day-to-day operations and business growth. She is a writer, chef, and computer programmer. As a senior MEAN/MERN stack developer and project manager with more than 4 years of experience in this sector, she now handles multiple projects. She has been producing technical writing for at least a year and a half. She enjoys coming up with fresh, innovative ideas.
LinkedIn