この記事では、コンピューターサイエンスの一般的なソートアルゴリズムをカバーします.ソートアルゴリズムは、しばしば問題の複雑さを減らすことができるので、研究することが重要です.また、検索アルゴリズム、データベースアルゴリズム、および大いに多くの直接アプリケーションがあります.
ソートアルゴリズムは次のようになります.

バブルソート

選択ソート

挿入ソート

マージソート

クイックソート

バケットソート

スワッピングと比較のためのヘルパー法

スワップと呼ばれるヘルパーメソッドを書くことから始めましょう.

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

私たちは多くの要素を比較することになるでしょう.したがって、そのための関数を書くのは良い考えだと思います.

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};

function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

さて、それが解決した今、ソートに移動しましょう!

バブルソート

ベスト: O ( n ),最悪: O ( n ^ 2 )

バブルソートは良い出発点ですので、簡単なソートアルゴリズムの一つです.それは、最も遅いソートアルゴリズムの1つであるけれども、ほとんどが教育目的のためにちょうど良いです.
要するに、最初のものが第2のものより大きいならば、バブルソートアルゴリズムは2つの隣接した価値を比較して、彼らをスワップします.これは、値が正しい順序に移動する傾向があるため、その名前を反映し、泡が表面に上昇するように.

function bubbleSort(arr, compare = defaultCompare) {
    const { length } = arr;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) { // refer to note below
            if (compare(arr[j], arr[j + 1]) === Compare.BIGGER_THAN) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}

私が提供した解決策は、私たちが不必要な比較を避けるために内側のループからパスの数を差し引いているので、通常のバブルソートアルゴリズムのわずかに改良されたバージョンです.実際に起こっていることをよりよく理解するには、次のような例を示します.

選択ソート

ベスト/ワースト：O（n ^ 2）

選択ソートアルゴリズムの背後にある基本的な考え方は、データ構造の最小値を見つけ、最初の位置に配置し、2番目の最小値を見つけ、2番目の位置に配置します.

function selectionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let minIndex;
    for (let i = 0; i < length - 1; i++) {
        minIndex = i;
        for (let j = i; j < length; j++) {
            if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex);
        }
    }
    return arr;
}

次の図は、アクションの選択ソートアルゴリズムの例です.

挿入ソート

ベスト: O ( n ),最悪: O ( n ^ 2 )

挿入ソートアルゴリズムは、一度に最終ソートされた配列の1つの値を構築します.プロセスは以下のようになります.

最初の要素が既にソートされていると仮定します.

第1と第2の要素を比較してください- 2番目の値がその場所にとどまるか、最初の値の前に挿入されるべきですか?

次に、3番目の値と同様の比較を行うことができます-最初、2番目、または3番目の位置に挿入する必要がありますか?など

function insertionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let temp;
    for (let i = 1; i < length; i++) {
        let j = i;
        temp = arr[i];
        while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

動作中の挿入ソートの例については、図を参照してください.

挿入ソートアルゴリズムは、小さい配列をソートするときに、選択とバブルソートアルゴリズムよりも優れた性能を持っています.

マージソート

ベスト/ワースト：O（n log n）

マージソートアルゴリズムは、分割統治アルゴリズムです.言い換えれば、各々の小さい配列が1つのポジションだけを有するまで、それはより小さいアレーにオリジナルのアレーを分割する.そして、それはソートされるより大きい配列により小さい配列を合併する.

ここでの実装は、2つの関数から成ります.

function mergeSort(arr, compare = defaultCompare) {
    if (arr.length > 1) {
        const { length } = arr;
        const middle = Math.floor(length / 2);
        const left = mergeSort(arr.slice(0, middle), compare);
        const right = mergeSort(arr.slice(middle, length), compare);
        arr = merge(left, right, compare);
    }
    return arr;
}

function merge(left, right, compare) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

プロセスを視覚化するための図です.

クイックソート

ベスト/平均: O ( n log n )、最悪: O ( n ^ 2 )

クイックソートは、最も使用されるソートアルゴリズムの一つです.マージソートと同様に、クイックソートも分割と征服アプローチを使用します.それは私たちがカバーした以前のソートより少し複雑であるので、少しそれを理解するために手順を中断してみましょう:

一般的に配列の真ん中の値をピボットと呼ぶ配列から値を選択します.

パーティション操作を実行し、左のピボットよりも小さく、右側の方が大きい値を持つ配列になります.

配列が完全にソートされるまで、最初の2つのステップを繰り返します.

function quickSort(arr, compare = defaultCompare) {
    return quick(arr, 0, arr.length - 1, compare);
}

function quick(arr, left, right, compare) {
    let i;
    if (arr.length > 1) {
        i = partition(arr, left, right, compare);
        if (left < i - 1) {
            quick(arr, left, i - 1, compare);
        }
        if (i < right) {
            quick(arr, i, right, compare);
        }
    }
    return arr;
}

function partition(arr, left, right, compare) {
    const pivot = arr[Math.floor((right, left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (compare(arr[i], pivot) === Compare.LESS_THAN) {
            i++;
        }
        while (compare(arr[j], pivot) === Compare.BIGGER_THAN) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

バケットソート

ベスト/平均: O ( n + k ),最悪: O ( n ^ 2 )

バケットソートアルゴリズムは、異なるバケットまたは小さな配列に要素を分離する分散ソーティングアルゴリズムであり、次に、挿入バインディングなどの小さな配列をソートするのに最適なソートアルゴリズムを使用して、各バケツを並べ替えます.

function bucketSort(arr, bucketSize) {
    if (arr.length < 2) {
        return arr;
    }
    // create buckets and distribute the elements
    const buckets = createBuckets(arr, bucketSize);
    // sort the buckets using insertion sort and add all bucket elements to sorted result 
    return sortBuckets(buckets);
}

function createBuckets(arr, bucketSize) {
    // determine the bucket count
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;

    // initialize each bucket (a multidimensional array)
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    // distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArr = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // quick sort is another good option
            sortedArr.push(...buckets[i]);
        }
    }
    return sortedArr;
}

バケットソートは、要素を均等にバケツに分配することができる場合に最適です.要素が大部分が疎であるならば、より多くのバケツを使用することはよりよく、そしてその逆です.
動作中のバケットソートアルゴリズムを次の図に示します.

結論

我々はいくつかの最も一般的なソートアルゴリズムをカバーしている.あなたが私に第2の部分を書くことを望むならば、私に知らせて、私はこの記事の上で行くために得られなかったより多くのソートアルゴリズムがあります.いずれにせよ、私はすぐにので、調整滞在を書く予定です!
下記の参考資料があります.

Big O Notation Cheat Sheet

The Sound of Sorting (Full Video) ティモBingmannによって

Implementations in multiple languages Freecodecampから

Sorting Visualization Tool ビジュアルから

Comedic Sorting Algo Webcomic からのXKCD