ソートアルゴリズム

ソートアルゴリズムは、リスト内の要素を特定の順序で入れるアルゴリズムです.デジタル順と辞書順に並べます.ソートアルゴリズムは簡単で、熟知していて、役に立ちますが、効果的に解決しにくいです.アルゴリズムは入門のいいテーマだそうです.アルゴリズムの花と呼ばれています.実務的にはほとんど反映されていませんが、勉強のために勉強します.それを実現して得られるものは非常に大きいと言われています.基本を身につければいいと思う.

泡の位置合わせ

まず、コードで確認します.

def bubblesort(A):
    for i in range(1, len(A)):
        for j in range(0, len(A)-1):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]

バブルのソートは重要ではないそうです.上記のコードから,時間複雑度は常にO(n^2)であり,非常に低効率なソート方式であることがわかる.

連結ソート

合併ソートは、ジョン・フォンノイマンが1945年に提案したアルゴリズムです.ほとんどの場合、高速ソートよりも遅くなりますが、一定の実行速度だけでなく、安定したソートであるため、共通ライブラリで多く使用されます.分割征服の真髄を示すアルゴリズムとも呼ばれる.
たとえば、ソートアルゴリズムは次のようになります.

[42, 1, 62, 34 7, 65, 14]
> [42, 1, 62, 34],         [7, 65, 14]
> [42, 1],   [62, 34],     [7, 65],   [14]
> [42], [1], [62], [34],   [7], [65], [14]
> [1, 42],   [34, 62],     [7, 65], [14]
> [1, 34, 42, 62],         [7, 14, 65]
> [1, 7, 14, 34, 42, 62, 65]

分割とマージ

その名の通り、全体的に解決できないので、分割して問題を解決する方法です.たとえば、リストのサイズが大きすぎるため、指定したリストで解決できません.この場合、対応するリストを分割することで問題を解決することができる.

クイックソート

高速ソートは、1959年にトニー・ホールが設計したアルゴリズムです.軸心を基準として左右を区切る特徴から、パーティション交換ソートとも呼ばれる.つまり、軸心を基準として、小さいものは左に、大きいものは右に移動します.前述したマージソートと同様に,分割征服アルゴリズムである.ただし、連結ソートとは異なり、クイックソートは入力値によってパフォーマンスにばらつきがあります.時間的複雑さを例にとると、最悪の場合はO(n^2)に相当する.しかし、平均はO(nlog n)に相当する時間複雑度である.

じく

ここで、ピボットは、ソート・オブジェクトのリスト内のデータの要素です.これにより、ピボットを選択するときに常に右端の要素を選択することをromuto partitionと呼びます.
たとえば、ソートのアルゴリズムは次のとおりです.

以下に、上記コードの実行結果を示す.

A = [2, 8, 7, 1, 3, 5, 6, 4]
lo = 0, hi = 7

以上の結果を以下に説明する.

left = 0, right = 0
A[left] = 2, A[right] = 2, pivot = 4
A[right] < pivot == true
A[left], A[right] = A[right], A[left]
하지만 left = right 이기 때문에 변화 없음. 첫 번째 print 결과
left += 1 > left = 1

A[left] = 8, A[right] = 8, pivot = 4
A[left] = 8, A[right] = 7, pivot = 4
A[left] = 8, A[right] = 1, pivot = 4
A[right] < pivot == true
A[left], A[right] = A[right], A[left]
1과 8의 위치 변경, 이렇게 pivot 보다 큰 경우 오른쪽으로 이동시킨다.
left += 1 > left = 1

これらの論理の繰り返しによってソートされます.
上述したように、最悪の場合、時間的複雑度はO(n^2)である可能性がある.ソートされたリストが入力値として指定されている場合、ピボットは常に右側にあり、リスト全体を迂回します.常に一定のパフォーマンスを示す集計ソートとは異なり、入力値はパフォーマンスのばらつきをもたらします.

安定ソートvs不安定ソート

安定ソートは、前述したバブルソート、マージソートに対応し、不安定ソートは高速ソートに対応する.安定ソートアルゴリズムは、入力順序と同じ繰返し値をソートします.たとえば、領域と時間の2つのデータがあると仮定し、時間順に並べ替えてから領域順に並べ替えると、安定した並べ替えと不安定な並べ替えの違いが発生します.
安定したソートは、時間順にソートされた順序でゾーンソートされますが、不安定なソートは、時間順にソートされた順序を無視して、ゾーン別にソートされます.すなわち、時間>地域順に並べ替えると、その地域内では時間順に並べ替えられ、不安定な並べ替えは時間>地域順に並べ替えられ、その地域内では時間順に並べ替えられない.

その他の学習点

挿入ソート

小隊

ヒップホップソート

選択ソート
など、いろいろなソートアルゴリズムも勉強します.