モダンJavaScript入門: クイックソートアルゴリズムを使用した配列の並び替え

1. クイックソート アルゴリズムとは

クイックソートは、高速なソートアルゴリズムの一つで、平均計算時間がO(n log n)となる分割統治法に基づくアルゴリズムです。ピボットと呼ばれる要素を基準に、ピボットより小さい要素と大きい要素に分割し、それぞれを再度ソートします。

2. クイックソートのアルゴリズムとコード例

配列から任意の要素を選び（これをピボットと呼ぶ）、ピボットより小さい要素と大きい要素に分割する。
各部分配列に対して同様の操作を適用する（これを再帰と呼ぶ）。
配列の要素が1つまたは0つになったら、その配列はソート済みとなる。

JavaScriptによるクイックソートのコード例は以下の通りです。

function quickSort(array) {
    if (array.length < 2) {
        return array;
    }

    const pivot = array[0];
    const lesser = array.slice(1).filter(item => item < pivot);
    const greater = array.slice(1).filter(item => item >= pivot);

    return [...quickSort(lesser), pivot, ...quickSort(greater)];
}

console.log(quickSort([9, 2, 5, 6, 4, 3, 7, 10, 1, 8]));  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

3. クイックソートの応用例

クイックソートは様々な問題に応用できます。ここでは、数値の降順ソート、オブジェクトのソート、文字列のソートの3つを例に挙げます。

3.1 数値の降順ソート

クイックソートを利用して数値の降順ソートを行うことができます。

function quickSortDesc(array) {
    if (array.length < 2) {
        return array;
    }

    const pivot = array[0];
    const lesser = array.slice(1).filter(item => item <= pivot);
    const greater = array.slice(1).filter(item => item > pivot);

    return [...quickSortDesc(greater), pivot, ...quickSortDesc(lesser)];
}

console.log(quickSortDesc([9, 2, 5, 6, 4, 3, 7, 10, 1, 8]));  // [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

3.2 オブジェクトのソート

クイックソートを利用してオブジェクトの配列を特定のキーでソートすることができます。

function quickSortObjects(array, key) {
    if (array.length < 2) {
        return array;
    }

    const pivot = array[0];
    const lesser = array.slice(1).filter(item => item[key] < pivot[key]);
    const greater = array.slice(1).filter(item => item[key] >= pivot[key]);

    return [...quickSortObjects(lesser, key), pivot, ...quickSortObjects(greater, key)];
}

const objects = [{id: 1, name: 'John'}, {id: 3, name: 'Alice'}, {id: 2, name: 'Bob'}];
console.log(quickSortObjects(objects, 'id'));  // [{id: 1, name: 'John'}, {id: 2, name: 'Bob'}, {id: 3, name: 'Alice'}]

3.3 文字列のソート

クイックソートを利用して文字列の配列をソートすることができます。

function quickSortStrings(array) {
    if (array.length < 2) {
        return array;
    }

    const pivot = array[0];
    const lesser = array.slice(1).filter(item => item < pivot);
    const greater = array.slice(1).filter(item => item >= pivot);

    return [...quickSortStrings(lesser), pivot, ...quickSortStrings(greater)];
}

console.log(quickSortStrings(['banana', 'apple', 'cherry', 'dragonfruit']));  // ['apple', 'banana', 'cherry', 'dragonfruit']

以上、クイックソートアルゴリズムを使用した配列の並び替えの基本的な理解と応用例について学びました。これからクイックソートを用いた様々な問題解決にチャレンジしてみてください。

AIko Code Symphony