ソートアルゴリズム

就職のためのコードテストとPython(羅東彬著)の本と講義を読んで整理した文章だ.
レッスンソース:https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

ソートアルゴリズム

ソート(Sorting)とは、特定の基準に従ってデータを順番にリストすることです.通常、問題の場合によっては、対応するソートアルゴリズムが式のように使用されます.

ソートの選択

未処理のデータの中から最小のデータを選択し、一番前のデータとの置換を繰り返します.
7 5 9 0 3 1 6 2 4 8
0 5 9 7 3 1 6 2 4 8
0 1 2 7 3 5 6 9 4 8
:
:
0 1 2 3 4 5 6 7 8 9
ソートされていないデータが1つ残っている場合は、処理する必要はありません.
検索範囲は繰り返し回数が増えるにつれて減少し、最小のデータを見つけるためには検索範囲に従ってデータを確認する必要があるため、毎回線形検索を行う.2つの重複文を使用して実装できます.

array = [7, 54, 9, 10, 3, 12, 63, 2, 4, 8]

for i in range(len(array)):
    min_index = i  # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]  # 스와프

print(array)

ソートの時間的複雑さの選択

ソートを選択して、N回の最小数を見つけて、一番前に送信します.

N + (N-1) + (N-2) + ... + 2

これは(n^2+n−2)/2で表すことができ,bikoマーキング法によればO(n^2)である.

整列挿入

処理されていないデータを適切な位置に1つずつ挿入します.ソートの選択に比べて、実装は難しくなりますが、効率は高くなります.
7 5 9 0 3 1 6 2 4 8
1番目のデータ7は位置合わせされていると考えられ、2番目のデータ5はどの位置に入るのか.7くらいしか存在しません.
5 7 9 0 3 1 6 2 4 8
9は入ることができる4つの位置のうち、入る位置を求めればよい.
0 5 7 9 3 1 6 2 4 8
0 3 5 7 9 1 6 2 4 8
:
:
0 1 2 3 4 5 6 7 8 9

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

for i in range(1, len(array)):
    for j in range(i, 0, -1):  # 인덱스 i부터 1까지 1씩 감소하며 반복
        if array[j] < array[j-1]:  # 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:  # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

        # 내립차순
        # if array[j] > array[j-1]:

print(array)

挿入ソートの時間的複雑さはO(N^2)であり,バイリンガル文からなる.現在のリストのデータがほとんどソートされている場合は、ソートの挿入速度が非常に速くなります.(最適な場合はO(N))

クイックソート

データムデータを設定し、データムより大きいデータとデータムより小さいデータの位置を変更します.最も基本的なクイックソートは、最初のデータを基準データ(Pivot)に設定することです.
5 7 9 0 3 1 6 2 4 8
現在、ピボットの値は5です.左から5より大きいデータを選択し、7を選択し、右から5より小さいデータを選択し、4を選択します.この2つのデータの位置は互いに変更されています.
5 4 9 0 3 1 6 2 7 8
9と2を選択します.
5 4 2 0 3 1 6 9 7 8
6と1を選択し、位置が一致しない場合は、ピボットとイテレーションの位置を互いに変更します.
1 4 2 0 3 5 6 9 7 8
このように軸心を基準としてデータパケットを行う動作を分割と呼ぶ.
5を基準として、左右のデータの並びをそれぞれ判断し、左側のデータ間で軸心を決定し、右側のデータ間で軸心を決定し、高速並べ替えという繰り返し

クイックソートの理由:直感的な理解

理想的には、分割が半分発生すれば、O(Nlogn)を総演算回数として期待することができる.
幅X高さ=Nx logN=NlogN

高速ソートの時間的複雑さ

平均的にはO(Nlogn)の時間的複雑度,最悪の場合はO(N^2)の時間的複雑度を持つ.
最初の要素を軸とする場合、並べ替えられた配列をすばやく並べ替えると、最小の数はそれ自体になるため、分割は行われず、データは右側にのみ集約されます.この場合,分割を実行する回数はNに比例し,分割を行うためには毎回線形探索を行い,時間複雑度はO(N^2)である.
最悪なのは、O(N^2)なので、標準ライブラリを使用すると、より速い速度とO(Nlogn)を保証できます.

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end

    # 엇갈릴 때까지 반복
    while(left <= right): 
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1

        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1

        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = ar ray[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right -1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

クイックソート:Pythonのメリットを活用

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


def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0]  # 피벗은 첫 번째 원소
    tail = array[1:]  # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot]  # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]  # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)


print(quick_sort(array))

ソート数

特定の条件が満たされている場合にのみ使用できますが、非常に高速なソートアルゴリズムが実行されます.データのサイズ範囲が限られている場合、整数で表すことができる場合に使用できます.データの個数がNであり、データ(正の値)の中で最もコストが大きい値がKである場合、最悪の場合でも実行時間O(N+K)を保証することができる.
リストを初期化して、最小から最大のデータ範囲を含むようにします.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
最小の0と最大の90～9のデータ範囲のリストを初期化します.

データを1つずつチェックすることで、データ値と同じインデックスのデータを1ずつ増やします.

結果を確認すると、リストの最初のデータから、その値を1つずつ繰り返してインデックスを出力します.
結果:0 1 1 1 2 3 4 5 6 8 9

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1  # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)):  # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ')

係数ソートの複雑さ分析

時間複雑度、空間複雑度:O(N+K)
0と99999999の2つのレベルのデータしかない場合、深刻な効率が低下する可能性があります.
同じ値を持つデータが複数ある場合、これらのデータを有効に使用できます(成績では複数の学生が100点を取っている可能性がありますので、ソートカウントは非常に有効です)

ソートアルゴリズムの比較

<問題>2つの配列の要素を置換

2つの配列A,BはN個の元素からなり,配列した元素はいずれも自然数である.K回までの置換演算を実行できます.置換演算とは、配列Aの1つの要素と配列Bの1つの要素を選択して2つの要素を置換することです.
最終的な目標は、アレイAのすべての要素の和を最大にすることである.
N、KおよびアレイA、Bの情報が与えられた場合、最大K回の置換操作を行い、アレイAのすべての要素の最値の和を出力するプログラムを作成してください.
例)N=5,K=3,A=[1,2,5,4,3],B=[5,5,6,5]
1と6、2と6、3と5
結果:A=[6,6,5,4,5],B=[3,5,1,2,5]
2つの配列の要素は最大100000個まで入力できるので、最悪の場合、O(Nlogn)を保証するソートアルゴリズムを使用する必要があります.(標準ライブラリ)

N, K = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort(reverse=True)

cnt = 0

# 내 풀이
for i in range(len(A)):
    if A[i] <= B[i]:
        A[i], B[i] = B[i], A[i]
        cnt += 1
    if cnt == K:
        break

# # 동빈쌤 풀이
# for i in range(k):
#     if A[i] <= B[i]:
#         A[i], B[i] = B[i], A[i]
#     else:
#         break

print(sum(A))