🧊

ソートアルゴリズム

2023/08/09に公開

ソート

tech

はじめに

パフォーマンス向上のため、アルゴリズム知識について少しでも知っておきたい！

最近は色々学びたいことがありすぎて、行ったり来たりしてしまっているので、
明日からは、Reactを本格的に学ぼうと思う！計画も立て直す！

今日は一旦ソートについて！

ソートとは？

ソートは、アイテムの並べ替えのこと。
たとえば、数字や文字列のリストを順番に並べる操作です！

数字のリスト 5, 2, 9, 1, 5, 6 があります！
このリストを昇順（小さい順）にソートすると、1, 2, 5, 5, 6, 9、
降順（大きい順）にソートすると、9, 6, 5, 5, 2, 1 となります。

ソートの用途

データを整理・分析しやすくするため。
データベースやファイルシステムのようなシステムでデータを効率的に検索・取得するため。
人々が情報を視覚的に解釈しやすくするため（例：商品を価格順に表示するなど）。

さまざまなソートアルゴリズムがあり、それぞれに特有の特性や効率性があります🤔

バブルソート、クイックソート、マージソートなどが代表的なソートアルゴリズムです。
適切なソートアルゴリズムを選択することで、特定の状況やデータセットにおいて効率的な結果を得ることができます。

クイックソート
平均的な場合で非常に効率的。ただし最悪のケースでは効率が落ちる可能性があります。
マージソート
安定で、最悪のケースでもO(n log n)の性能を保つ。
ヒープソート
in-placeでありながら、O(n log n)の性能を保証。

バブルソート

隣接する2つの要素を比較して、順序が間違っていれば交換することをリスト全体に対して繰り返し行うこと。この操作をリスト全体に対して行うと、最大の要素がリストの最後に移動します。

アルゴリズムの流れ

最初の要素と次の要素を比較する。
順序が間違っていれば、それらの要素を交換する。
次の要素に移動し、上記の2つのステップを繰り返す。

リストの最後までこの操作を繰り返すと、最も大きな要素がリストの最後に移動します。
リストの長さを1つ減らして、上記の手順を繰り返します。
リストの長さが1になるまで繰り返し続けます。

バブルソートの特徴


時間計算量	平均・最悪時 O(n^2)、最良時 O(n)
安定性	安定なソートアルゴリズム
in-placeソート	追加のメモリを必要としない

O(n^2) と O(n)って何？

アルゴリズムの時間複雑度を示すビッグオ記法による表現。
アルゴリズムが処理するデータのサイズ（n）に対して、どれだけのステップや時間がかかるかのオーダー（大雑把な増加の度合い）を示している!

O(n^2)（オーダー n の 2 乗）

この表現は、データのサイズが n の場合、最悪のケースでアルゴリズムが n^2 回のステップを実行する可能性があることを示します。

O(n)（オーダー n）

この表現は、データのサイズが n の場合、アルゴリズムが最大で n 回のステップを実行する可能性があることを示します。

シンプルなため実装が容易ですが、実際のアプリケーションでの使用は、
効率の面で他のソートアルゴリズム（クイックソート、マージソートなど）に比べて不利です。

javascript

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let swapped = false;
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 要素をJavaScriptの分割代入を使って交換します
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        // もし内側のループで2つの要素が交換されなかった場合、配列はすでにソートされているとみなします
        if (!swapped) {
            break;
        }
    }
    return arr;
}

// 使用例:
const sortedArray = bubbleSort([64, 34, 25, 12, 22, 11, 90]);
console.log(sortedArray); // 期待される出力: [11, 12, 22, 25, 34, 64, 90]

この実装では、交換が1回も行われない場合（すでにソートされている場合）、
処理を早期に終了するようにしています🤔

トーナメントソート

トーナメントソートは、特にAPIなどの外部システムとのインタラクションが制限されている場合や、比較にコストがかかる場合に有効です!ですが、この方法は通常のソートアルゴリズムと比べて効率的ではないです!

トーナメントソートの基本的な考え方では、1回のトーナメントで1つの「勝者」（例えば最小値）しか求められないので、n個のアイテムをソートするためには、実質的にn-1回のトーナメントが必要となります。

トーナメントソートのメリット

制約の下での効率
2つの要素しか比較できない制約など、特定の条件下では、他のソートアルゴリズムよりも効果的に動作することがあります。
予測可能な比較回数
一度の「トーナメント」で最小値を見つける際の比較回数は固定であり、その後のラウンドでは再利用されるため、全体の比較回数が予測しやすくなります。
外部ソートに適している
ディスクなどの外部ストレージで大量のデータをソートする際に効果的な場合があります。

トーナメントソートのデメリット

非効率性
制約がない場合、トーナメントソートは多くのソートアルゴリズムと比べて非効率的。
複雑な実装
データの構造（たとえば、二分ヒープ）を適切に管理する必要があり、実装が他のシンプルなアルゴリズムよりも複雑になる場合があります。
in-placeソートではない
追加のメモリスペースを必要とする場合があります。

in-placeソートとは?

ソートを行う際に追加のメモリをほとんど使わず、
元の配列内で要素を直接並べ替えるソート方法のこと。

具体的には、データをソートするためにO(1)（定数）のメモリしか追加で使いません。
大量のデータをソートする場合など、追加のメモリを節約したい場面で非常に有用です！

in-placeソートの例


バブルソート	要素を隣同士で比較し、必要に応じてスワップします。
選択ソート	最小（または最大）の要素を見つけて、正しい位置にスワップします。
挿入ソート	一つずつ要素を正しい位置に挿入します。
ヒープソート	ヒープデータ構造を使用して要素をソートします。

これに対して、追加のメモリスペースを必要とするソートアルゴリズム（in-placeではない）も存在します。
例としては、マージソートが挙げられます。
マージソートでは、分割と統合のプロセス中に新しい配列やリストを作成するため、追加のメモリが必要となります。

in-placeソートの主な利点は、メモリの節約ができることですが、その性質上、元のデータの順序が変わることがあるため、データの元の順序を保持することが重要な場合は注意が必要です！