ソートアルゴリズム

ソートは、特定の基準に従ってデータを順番にリストします.

ソートの選択

未処理のデータの中から最小のデータを選択し、一番前のデータとの置換を繰り返します.
ソート例の選択

array = [7, 5, 9, 0, 3, 1, 6, 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回の最小数を探し、一番前に送ります
したがって,時間的複雑度はO(N^2)である.

整列挿入

処理されていないデータを適切な位置に1つずつ挿入します.
ソートの選択に比べて、実装は困難ですが、通常は操作効率が高くなります.
配置の例を挿入

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

print(array)

挿入位置合わせの時間的複雑さ

挿入ソートの時間的複雑度はO(N^2)であり,選択ソートと同様に繰り返し文を2回重ねて用いる.
現在のリストに並べ替えられているデータをほぼ整列させると、非常に速く動作します.
最適の場合,O(N)の時間的複雑さを持つ.

クイックソート

これは、基準データを設定し、ビッグデータとビッグデータの位置を変更する方法です.
これは最もよく使われるソートアルゴリズムの一つです.
最も基本的なクイックソートは、最初のデータを基準データ(Pivot)に設定することです.

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

高速ソートはO(Nlogn)の時間的複雑さを有する.
しかし最悪の場合はO(N^2)の時間的複雑さである.
クイックソートの例

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] = array[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)

ソート数

これは、特定の条件を満たす場合にのみ使用できますが、非常に迅速に動作するソートアルゴリズムです.
カウントソートは、データのサイズ範囲が限られており、整数で表すことができる場合にのみ使用できます.
データの個数がNであり、データ(正値)の最大値がKである場合、最悪の場合でも実行時間O(N+K)を保証することができる.
ソート数の例

# 모든 원소의 값이 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)であった.
係数ソートは、深刻な非効率をもたらす場合があります.
ex)データは2つしかありません
カウントソートは、同じ値を持つ複数のデータが表示された場合に有効に使用できます.

比較ソートアルゴリズム

ほとんどの場合、O(Nlogn)を保証するためです.

2つの配列の要素置換の問題

import sys

n,k = map(int,sys.stdin.readline().split())
a = list(map(int,sys.stdin.readline().split()))
b = list(map(int,sys.stdin.readline().split()))

a.sort()
b.sort()
b.reverse()
tmp = 0
for i in range(k):
    if a[i] < b[i]:
        tmp = a[i]
        a[i] = b[i]
        b[i] = tmp
    else:
        break

print(sum(a))

ソース:https://freedeveloper.tistory.com/274?category=888096