並べ替えアルゴリズム2の整理と実装(高速分割、連結連結)

分割とマージアルゴリズム

複雑または大きな問題をいくつかの部分に分けて解決する方法.
小さな問題を解決してから合併する.

分割征服の原理

提供-分割:この問題を複数のサブ問題に分割します.問題を解決しやすくする.

Conquer-征服:問題を最大限に分割し,これ以上分割できなければ問題を解決する.分割の問題を解決する.

マージ(combine)-マージ:解決した問題をマージして既存の問題を解決します.

分割征服の特徴

難題を小さな部分に分けて、解決しやすい.

小さな問題を分割することで、同じタスク

をより速く処理することができる.

関数を再使用すると、オーバーヘッドが増加する可能性があります.

分割可能かどうか,分割征服アルゴリズムを用いて有効かどうかを考慮すべきである.

クイックソート

分割征服を用いてソートする方法では,ピボット(pivot)とパーティション(partition)を用いて分割とソートを行う方法である.
実際に使用する頻度の高いアルゴリズムの1つで、Bubble、挿入、選択ソートよりも効果的です.

分割征服の概念のアルゴリズムを用いて,分割ソートを逐次行う.

アルゴリズムは、

の軸心(pivot)を用いる、軸心分割の基準点

を表す.

パーティションの使用
*このピボットを決定する基準は、次の分割でも変更できません.

の後に再帰呼び出しが実行され、並べ替えが繰り返される.

クイックソートの実装

def quick_sort(lst):
  
  if len(lst) <= 1: # 재귀를 통해 리스트 원소가 1개가 되면 그대로 해당값 반환
    return lst
  else:           
    pivot = lst[0]  # 피벗을 0번 인덱스로 지정
    greater = [i for i in lst if i > pivot]  # 피벗보다 큰 경우 greater 변수에 리스트로 넣는다.
    smaller = [i for i in lst if i < pivot]  # 피벗보다 작은 경우 smaller 변수에 리스트로 넣는다.
    return quick_sort(smaller) +[pivot] + quick_sort(greater) # 재귀함수를 통하 작은것부터 결과 리스트를 합쳐낸다.

lst = [4,7,1,6,3,2,9,0,8,5]
quick_sort(lst)

[output]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ソート

は、不安定なソートに属するため、同じ値があっても内部で再配置されます.

アレイ内では、軸心等化分割が可能な値のみが最適です.

の平均時間複雑度はO(nlogn)O(nlogn)O(nlogn)であり、最悪の場合、初期は完全にアンバランスに1つに分割しなければならないので、時間複雑度はO(n 2)O(n^2)O(n^2)O(n 2)である.

H/Wの影響で性能にばらつきがある可能性がある.
広い範囲で移動せず、良好な地域性(locality)を有するためpage-cacheヒット率が高く、ハードウェア面では他のソートよりも有利である.しかし、これはハードウェアのパフォーマンスのばらつきを引き起こす可能性があります.

連結ソート

合併ソートまたは残留ソートとも呼ばれ、異域を利用して征服を分割しようとするソート方法であるため、大きな問題を小さな問題に分割した後、これらの問題を解決し、合併する方法を採用する.

養分分割、並べ替え、合併並べ替えを用いた典型的な分割征服法.

のすべてのデータを最初から最後まで探索した.

には単独の軸心はなく,バイナリ分類のように配列の中間を切り,再帰呼び出しにより繰り返す.

をマージする場合もソートします.

def merge_sort(lst):
  a = len(lst)      # 리스트의 길이
  mid = a //2       # 중간값
  if a >1:          # 길이가 1인 경우는 그대로 반환한다.
    L =  lst[:mid]  # 중간점 기준 left
    R = lst[mid:]   # 중간점 기준 right

    merge_sort(L)   # 분할이 될때까지 계속해서 재귀호출로 분할을 진행한다.
    merge_sort(R)
    
    i = j = k = 0        # 분할이 완료된 후 작업진행
    while i < len(L) and j < len(R):  # L과 R의 각각의 원소들을 반복 비교해 정렬해나가면서 병합한다.
      if L[i] > R[j]:    # L의 i번쨰 원소가 R의 j번째 원소보다 클 경우
        lst[k] = R[j]    # lst의 k번째 원소를 R의 j번째에 있던 가장 작은 원소로 맞춰놓는다.
        j += 1           # j번째는 리스트에 넣었으니 그다음 원소와 비교를 위해 j에 1을 더해 반복문 진행
      elif L[i] < R[j]:  # 위와 반대로 진행
        lst[k] = L[i]
        i += 1
      k += 1             # 반복 1회마다 메인 리스트에 원소를 넣었으니 그 다음 원소에 넣을 수 있도록 1을 더해줌
    
    while i < len(L):    # 연산 진행 후, L 또는 R이 불균형해 한쪽 리스트가 남아있을 때,
      lst[k] = L[i]      # 해당 리스트 원소들은 이미 반대편 리스트보다 큰 값이므로 반복문으로 넣어준다.
      i +=1
      k += 1
    
    while j < len(R):   # L과 마찬가지
      lst[k] = R[j]
      j +=1
      k += 1

が分割できないまで(lst長が1になるまで)、再帰呼び出しを継続する.

をマージするには、各要素を比較してソートする必要があります.

入力データが多ければ多いほど、移動が多くなり、効率が低下します.

のデータ分布の影響は小さい.時間複雑度は常にO(nlogn)O(nlogn)O(nlogn)

である

接続リストは非常に効率的です.