JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

JavaScriptでクイックソートを実装する方法を徹底解説

クイックソートとは

クイックソート（Quick Sort）は、JavaScriptにおいて最も重要なソートアルゴリズムの一つです。その基本的な仕組みは、配列から基準となる値（ピボット）を1つ選び、残りのすべての要素を「ピボットより小さいグループ」と「ピボットより大きいグループ」の2つに分割することから始まります。

次に、分割されたそれぞれのグループに対して同じ手順を再帰的に適用します。つまり、各グループの中で新たにピボットを選び、さらに小さいグループと大きいグループへと分割していくのです。

この処理を繰り返すことで、最終的には各サブグループが要素を1つだけ持つか、比較対象がなくなる状態まで分割されます。途中でピボットとして選ばれた値は、その時点で正しい位置が確定しているため、それ以上の分割は行われません。こうしてすべてのピースが揃ったところで結合すると、ソート済みの配列が完成します。

クイックソートの平均計算量は O(n log n) と非常に効率的で、大規模なデータを扱う際にも高速に動作することが特徴です。

実装例

以下は、JavaScriptでクイックソートを実装したシンプルなサンプルコードです。

<html>
<body>
<script>
    function quickSort(originalArr) {
      if (originalArr.length <= 1) {
         return originalArr;
        } else {
             var leftArr = [];         
             var rightArr = [];
             var newArr = [];
             var pivot = originalArr.pop();    // ピボット値を取り出す
             var length = originalArr.length;
             for (var i = 0; i < length; i++) {
                if (originalArr[i] <= pivot) {    // ピボットを基準に比較
                   leftArr.push(originalArr[i]);     
             } else {
                    rightArr.push(originalArr[i]);
           }
         }
        return newArr.concat(quickSort(leftArr), pivot, quickSort(rightArr)); // ソート完了まで再帰的に処理
    }
   }
   var myArray = [9, 0, 2, 7, -2, 6, 1 ];
   document.write("Original array: " + myArray);
   var sortedArray = quickSort(myArray);
   document.write("Sorted array: " + sortedArray);
</script>
</body>
</html>

このコードの流れを簡単に整理すると、以下のようになります。

  • 配列の長さが1以下の場合は、すでにソート済みとしてそのまま返します。
  • 配列の末尾の要素を pop() で取り出し、ピボットとして使用します。
  • 残りの要素をループで走査し、ピボット以下の値は左側の配列へ、大きい値は右側の配列へ振り分けます。
  • 左側・右側の配列に対して quickSort() を再帰的に呼び出し、結果をピボットとともに concat() で結合して返します。

出力結果

Original array: 9,0,2,7,-2,6,1
Sorted array: -2,0,1,2,6,7,9

実行すると、元の配列 [9, 0, 2, 7, -2, 6, 1] が昇順に並べ替えられ、[-2, 0, 1, 2, 6, 7, 9] というソート済みの配列が出力されます。負の値を含むデータでも問題なく動作することが確認できます。


  1. JavaScriptで非同期ループを実装する方法をわかりやすく解説

    JavaScriptでは、async/awaitとPromiseを組み合わせることで、各処理の完了を待ちながら繰り返しを実行する「非同期ループ」を実装できます。通常のループ内で時間のかかる処理(API通信やタイマー処理など)を順番に実行したい場合に非常に便利です。以下は、JavaScriptで非同期ループを実装するコード例です。コード例<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8" /> <meta name="vi

  2. JavaScriptでアクセント付き文字を含む文字列を並べ替える方法

    JavaScriptの標準的な sort() メソッドは、文字列をUnicodeコードポイントの順序に基づいて比較します。そのため、「é」や「ó」のようなアクセント付き文字を含む文字列を単純にソートすると、期待通りのアルファベット順にならないことがあります。この問題を解決するには、localeCompare() メソッドを使用します。このメソッドは、指定されたロケールの言語規則に従って文字列を比較できるため、アクセント付き文字も正しく並べ替えられます。localeCompare() の基本的な使い方以下は、スペイン語のアクセント付き文字を含む配列を localeCompare() を使ってソー