並べ替えアルゴリズム ||パイソン ||データ構造とアルゴリズム-Python チュートリアル-php.cn

Sorting Algorithms || Python || Data Structures and Algorithms

並べ替えアルゴリズム

1. バブルソート

ここでは、配列の最後に到達するまで、上位の要素をその隣の要素と交換します。これで、最上位の要素が最後の位置になります。そこで、境界を変更して、最後から 1 ずつ減らします。最悪の場合、配列をソートするには n 回反復する必要があります。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

ログイン後にコピー

アルゴリズム -

配列を反復処理して最大の要素を見つけ、それを最後の要素と交換します。
隣接するすべての要素を比較し、大きい要素が小さい要素の前にある場合は交換します。配列の最後に到達するまでこれを続けます。
フラグを維持します。交換される要素がない場合は、配列がソートされるため、ループを中断できます。

時間計算量:

ベストケース - 配列がすでにソートされている場合、必要な反復は 1 回だけです。時間計算量 - O(n)
平均ケース - 配列がランダムにソートされている場合、時間計算量 - O(n2)
最悪のケース - 配列が降順の場合、n*2 回の反復が必要になります。

空間の複雑さ - O(1)、追加のメモリは必要ありません。

利点 -

追加のメモリは必要ありません。
要素が相対的な順序を維持するため安定しています。

欠点 -

時間計算量 - O(n2)。大規模なデータセットでは非常に高くなります。

アプリケーション -

データセットが非常に小さく、時間の複雑さによる非効率性よりも単純さが優先される場合にのみ使用できます。

2. 選択範囲の並べ替え

ここでは、配列内の最小の要素を見つけて、それを最初の要素に置き換えます。次に、境界を 1 ずつ増やし、配列の最後に到達するまで同じ手順を繰り返します。

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

ログイン後にコピー

アルゴリズム -

配列を反復処理して最小要素を見つけます。
最初の要素と交換し、ポインタを 1 増やします。
配列の最後に到達するまでこのプロセスを繰り返します。

時間計算量: 3 つのケースすべてで O(n2) の時間計算量があります: 最高、平均、最悪。 これは、最小限の要素を選択する必要があるためです。配列がすでにソートされているかどうかに関係なく、毎回それを交換します。

空間の複雑さ - O(1)、追加のメモリは必要ありません。

利点 -

追加のメモリは必要ありません。
バブルソートよりも少ないスワップが行われます。

欠点 -

時間計算量 - O(n2)。大規模なデータセットでは非常に高くなります。
等しい要素の相対的な順序が維持されないため、安定していません。

アプリケーション -

追加のストレージを必要としないため、メモリが限られたシステムでも使用できます。
これは、書き込み操作が遅いシステムなど、スワップ数を最小限に抑えることが重要なシステムで使用されます。

3. 挿入ソート

これは、要素の位置から配列の先頭まで逆方向に反復チェックすることで、ソートされていない要素を正しい位置に挿入するアルゴリズムです。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

ログイン後にコピー

アルゴリズム -

配列の 2 番目の要素から開始して、最初の要素と比較します。現在の要素が最初の要素より小さい場合は、それらを交換します。
ここでポインターを増やし、3 番目の要素に対してこれを行います。2 番目と最初の要素と比較します。
残りの要素についても同じプロセスを繰り返し、前のすべての要素と比較し、適切な位置に挿入します。

時間計算量:

- 最良のケース - 配列がすでにソートされている場合、必要な反復は 1 回だけです。時間計算量は O(n)
- 平均的なケース - 配列がランダムにソートされている場合、時間計算量は O(n2)
- 最悪の場合 - 配列が降順の場合、n2 回の反復が必要になります。

空間の複雑さ - O(1)、追加のメモリは必要ありません。

利点 -

追加のメモリは必要ありません。
要素が相対的な順序を維持するため、安定しています。

欠点 -

時間計算量 - O(n2)。大規模なデータセットでは非常に高くなります。
等しい要素の相対的な順序が維持されないため、安定していません。

アプリケーション -

ライブデータストリームなど、要素がリアルタイムで到着し、並べ替える必要があるシナリオでは効率的です。

4. マージソート

マージソートは、分割統治アプローチに従うアルゴリズムです。これには 2 つの主なステップがあります。1 番目は配列を再帰的に分割し、2 番目は分割された配列をソート順にマージします。

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

ログイン後にコピー

アルゴリズム -

中点を計算して配列を 2 つの半分に分割します。
各部分配列の長さが 1 になるまで分割を続けます。
両方の半分、つまり左半分と右半分でマージ関数を呼び出します。
マージプロセスには 3 つのポインターを使用します:

左半分の配列の最初のポインタ。
配列の右半分の 2 番目のポインタ。
ソートされた配列の 3 番目のポインター。

両方の半分を反復処理し、それらの要素を比較します。小さい方の要素をソートされた配列に挿入し、対応するポインタを 1 ずつインクリメントします。
配列全体がソートされるまで、このプロセスを再帰的に繰り返します。

時間計算量: マージソートの時間計算量は、最高、平均、最悪の 3 つのケースすべてで O(n log n) です。これは、配列が既にソートされているかどうかに関係なく、分割と結合のたびに同じ手順が実行されるためです。

O( log n ) - 配列サイズは分割フェーズ中の各ステップで半分になります。

O(n) - マージプロセス中に、すべての要素を 1 回反復する必要があります。

したがって、合計時間計算量は O (n) * O (log n) = O (n log n)

空間の複雑さ - O(n)、一時配列を保存するためにマージプロセス中に追加のメモリが必要です。

利点 -

要素が相対的な順序を維持するため、安定しています。
大規模なデータセットであっても、時間計算量は O (n log n) です。
部分配列が独立してマージされるため、並列処理に適しています。

欠点 -

時間計算量 - O(n2)。大規模なデータセットでは非常に高くなります。
マージプロセスには追加のメモリが必要です。
追加のメモリが必要なため、設置されていません。
一般に、ほとんどのデータセットでは QuickSort よりも遅くなります。

アプリケーション -

大きなファイルのマージなど、データが大きすぎてメモリに収まらない状況で使用されます。
ランダムアクセスが必要ないため、リンクリストをソートするために使用されます。

5. クイックソート

クイックソートは、分割統治アプローチに従ったアルゴリズムです。ピボット要素を選択し、ピボットを正しい並べ替え位置に配置した後、ピボット要素を中心に配列を分割します。

最初のステップは、ピボット要素を選択し、ピボットを中心に配列を分割することです。ピボットより小さい要素はすべて左側にあり、ピボットより大きい要素はすべて右側にあります。これで、ピボットは正しいソート位置に配置されます。再帰的には、配列を 2 つの半分に分割することによって、同じプロセスが適用されます。前半にはピボット前の要素が含まれ、後半にはピボット後の要素が含まれます。このプロセスは、各部分配列の長さが 1 に達するまで繰り返されます。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

ログイン後にコピー

アルゴリズム -

中点を計算して配列を 2 つの半分に分割します。
ピボットを選択します。任意の要素をピボットとして選択できます。
配列を反復処理し、各要素をピボットと比較します。
ピボットより小さい要素はすべて左側に、ピボットより大きい要素はすべて右側に配置します。
ピボットが正しいソート位置に配置されるように、ピボットを左ポインターと交換します。
パーティションの長さが 1 より大きくなるまで、このプロセスを再帰的に繰り返します。

時間計算量:

1.最良のケース - 時間計算量 - O(n log n)、ピボットが配列を 2 つの等しい半分に分割する場合。
2.平均的なケース - 時間計算量 - O(n log n)、ピボットが配列を 2 つの等しい半分に分割する場合。しかし、必ずしも等しいわけではありません。
3.最悪の場合 - 時間計算量 - O(n2) 、時 -

すでにソートされた配列のピボットとして最小の要素が選択されます。
降順でソートされた配列内のピボットとして最大の要素が選択されます。

O( log n ) - 配列サイズは分割フェーズ中の各ステップで半分になります。

O(n) - 要素の順序付け中。

したがって、合計時間計算量は O (n) * O (log n) = O (n log n)

空間の複雑さ:

最良および平均のケース - O( log n) - 再帰スタックの場合。
最悪の場合 - O(n) - 再帰スタックの場合。

利点 -

ピボットの選択が間違っていなければ、大規模なデータセットに対して効率的です。
同じ配列でソート作業を行い、データを補助配列にコピーしないため、キャッシュに優しいです。
安定性が必要ない場合の大規模データ向けの最速の汎用アルゴリズムの 1 つ。

欠点 -

時間計算量 - O(n2)。大規模なデータセットでは非常に高くなります。
等しい要素の相対的な順序が維持されないため、安定していません。

アプリケーション -

プログラミングライブラリとフレームワークで使用されます。たとえば、Python のsorted() 関数と Java の Array.sort() はクイックソートに基づいています。
クエリ実行中に行を効率的に並べ替えることにより、indDatabase クエリの最適化に使用されます。
キャッシュに適した特性があるため、大規模なデータセットのメモリ内での並べ替えに適しています。

6.ヒープソート

ヒープソートは、比較ベースのソートアルゴリズムです。これは選択ソートの拡張機能です。ヒープソートでは、バイナリヒープを作成し、最大または最小の要素を最後の要素と交換します。次に、ヒープサイズを 1 減らします。このプロセスは、ヒープの長さが 1 より大きくなるまで繰り返されます。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

ログイン後にコピー

アルゴリズム -

heapify プロセスを使用して最大ヒープを構築します。 Heapify は、バイナリヒープデータ構造のヒーププロパティを維持するために使用されるメソッドです。
配列のサイズが n の場合、n//2 個の親ノードが含まれます。
インデックス i の親の場合:

a.その左側の子はインデックス 2i 1 にあります

b.その右側の子はインデックス 2i 2

にあります。

インデックス n//2 から 0 までの親を持つすべてのサブツリーを反復処理し、それらに対して heapify 関数を呼び出します。
これで、配列は最大ヒープになり、最大の要素はインデックス 0 になります。
ヒープの最初の要素と最後の要素を交換し、ヒープのサイズを 1 減らします。
ヒープの長さが 1 より大きくなるまでこのプロセスを繰り返します

時間計算量: ヒープソートの時間計算量は、最良、平均、最悪の 3 つのケースすべてで O(n log n) です。これは、配列が既にソートされているかどうかに関係なく、最大ヒープが作成され要素が交換されるたびに同じ手順が実行されるためです。

O( log n ) - 最大ヒープを作成します

O(n) - 最大ヒープが作成され、要素が n 回スワップされるため。

したがって、合計時間計算量は O (n) * O (log n) = O (n log n)

空間複雑度 : すべての場合 - O( log n) - 再帰的スタックの場合。

利点 -

大規模なデータセットであっても、時間計算量は O (n log n) です。
メモリ使用量はほぼ一定です。

欠点 -

等しい要素の相対的な順序が維持されないため、安定していません。
マージソートと比較して多くのスワップが必要です。

アプリケーション -

最大要素または最小要素の抽出が頻繁に行われる優先キューの実装に役立ちます。
インプレースソートが必要でメモリ使用量が重要なシステムで役立ちます。
ランキングが必要なシナリオで使用されます。

7.カウンティングソートと基数ソート

カウンティングソートは、非比較ベースのソートアルゴリズムです。これは、入力値の範囲がソート対象の要素の数に比べて小さい場合に特に効率的です。カウンティングソートの背後にある基本的な考え方は、入力配列内の個別の各要素の頻度をカウントし、その情報を使用して要素を正しいソート位置に配置することです。

基数ソートは、サブルーチンとしてカウンティングソートを使用します。数値の各桁にカウンティングソートを適用し、配列内の最大の数値のすべての桁が処理されるまでソートを繰り返します。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

ログイン後にコピー

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

ログイン後にコピー

アルゴリズム -

配列内の最大数を見つけて、その桁数 (d) を決定します。数値の長さが d の場合、配列に対して Counting Sort が d 回呼び出されます。
コールカウンティング配列内の各桁を 1 の位から順に並べ替え、次に 10 の位まで並べます。
カウントソート中:

まず、インデックス配列を作成し、その値に基づいて要素をマップします。たとえば、数字が 4 の場合、インデックス配列の 4 番目のインデックスの値を増分します。
インデックス配列からプレフィックス合計配列を作成します。
プレフィックス合計配列を使用して、入力配列の長さに等しい新しい並べ替えられた配列を作成します
たとえば、プレフィックス合計配列のインデックス 1 の値が 2 である場合、ソートされた配列の位置 2 に値 1 を配置し、プレフィックス合計配列の値を 1 ずつ減分します

時間計算量:

Counting Sort の時間計算量は O(n k) です。ここで、n は並べ替える要素の数、k は値の範囲 (インデックス配列のサイズ) です。この計算量は次の場合に有効です。 3 つのケースすべて: 最良、平均、最悪。

これは、配列が既にソートされているかどうかに関係なく、毎回同じ手順が実行されるためです。

基数ソート の時間計算量は d 倍に増加します。ここで、d は配列内の最大の数値の桁数です。時間計算量は O (d * (n k))

したがって、合計時間計算量は O (d) * O(n k) = O (d * (n k)) となります

空間複雑度: すべての場合 - O(n k)、n は入力配列の長さ、k はインデックス配列内の値の範囲です。

利点 -