バックアップアルゴリズム11ステップ(ソートアルゴリズム)

新規コンテンツ

ソートアルゴリズムのタイプ(bybigoシンボル)

O(n²)の時間的複雑度(ソートするデータの数が増加する場合は平方で増加)

Bubble Sort

選択ソート

挿入ソート

クイックソート

O(n log n)の時間複雑度

連結ソート

ヒップホップ(Heap Sort)

スムーズソート(Smooth Sort)

その中で最悪の時間複雑度は「bigoマーキング法」です.
ソース、説明:https://velog.io/@jguuun/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
画像ソース:https://blog.chulgil.me/algorithm/

1）2750回並べ替え

現在、ソートアルゴリズムは使用されていませんが、Python内蔵関数を使用しています.sort()の使用

N = int(input())
ans_list = []

for i in range(N):
    x = int(input())
    ans_list.append(x)

# 디폴트로 오름차순 정렬을 시행한다.
ans_list.sort()

for i in ans_list:
    print(i)

2)2751回ソート2(マージソートマージソート)

前述したように、組み込み関数sort()を使用するとタイムアウトします.しかし、sysはinput()とprintに代わる.stdin.readline()とsys.stdout.writeを使用すると、答えが処理されます.
しかし,与えられたヒントを用いて集計ソートを利用することにした.

import sys

N = int(input())
ans_list = []

for i in range(N):
    ans_list.append(int(sys.stdin.readline()))

# 내장 함수인 sorted() 사용
for i in sorted(ans_list):
    sys.stdout.write(str(i)+'\n')

次のコードは、集計ソートアルゴリズムを使用します.
再帰関数ですべてlen=1の配列に分割し、比較して小数からマージします.
したがって,時間的複雑度は分割過程でO(logN),合成過程でO(N)となり,O(NlogN)全体となる.
しかし、リストシート[a:b]は配列のコピーを生成し、メモリ効率は高くない...!
ソース:https://www.daleseo.com/sort-merge/

import sys

N = int(input())
ans_list = []

for i in range(N):
    ans_list.append(int(sys.stdin.readline()))

def mergeSort(checkArr):
    if len(checkArr) < 2:
        return checkArr

    # 재귀를 통한 분할 과정
    mid = len(checkArr) // 2
    front_arr = mergeSort(checkArr[:mid])
    back_arr = mergeSort(checkArr[mid:])

    # 분할이 끝나면 front와 back으로 분할 된 배열의 0번째 수부터 비교하여 다시 병합
    mergedArr = []
    l = h = 0
    while l < len(front_arr) and h < len(back_arr):
        if front_arr[l] < back_arr[h]:
            mergedArr.append((front_arr[l]))
            l += 1
        else:
            mergedArr.append(back_arr[h])
            h += 1
    # 두 배열 중 하나의 배열이 모두 담긴 상황이라면 다른 배열의 나머지 값들도 넣어주기 (이미 정렬됨)
    mergedArr += front_arr[l:]
    mergedArr += back_arr[h:]
    return mergedArr

for j in mergeSort(ans_list):
    print(j)

3)10989番付ソート3(カウントソートカウントソート)

❌❌❌❌<第1話最終失敗!->コードのコメントと理解に注目>
カウントソート、またはカウントソートは、O(n+k)時間の複雑さを有するソートである.
ここで、いくつかの見知らぬkは、ソートを実行する配列の最大値を表す.
kは、kが実行時間に影響を及ぼすため、省略されずに定数と見なされる.
kがnより小さい場合、ソートの実行時間はO(n)であるが、無限大である場合、ソートの実行時間も無限長である.
ソース:https://seongonion.tistory.com/130
カウントソートは、重複要素の個数に基づいて格納され、格納された値に基づいてソートリストを生成するアルゴリズムです.
一般的に学校試験成績と同様に一定範囲(0~100点)に分布し、重複値がある場合に用いられる.
次のコードは、係数を用いて出力をソートするコードです.しかしメモリが超過しています...
理由を検索した結果、入力が最大1000万回に達し、繰り返し文のappendがある場合、メモリの再割り当てなど、メモリ制限が8 mbになるなど、さまざまな原因が発生します.

import sys
N = int(input())
N_list = []
for i in range(N):
    x = int(sys.stdin.readline())
    N_list.append(x)

# 입력한 배열 원소 중 최댓값 범위 만큼의 개수 리스트 생성 후 개수리스트에 원소 개수 만큼 반영해준다.
count_list = [0] * (max(N_list) + 1)
for n in N_list:
    count_list[n] += 1

# 개수 리스트의 원소를 누적합 값으로 갱신 (입력값 배열에 담긴 원소를 바로 정렬된 위치로 삽입하기 위한 사전작업)
for i in range(1, len(count_list)):
    count_list[i] += count_list[i-1]

result_list = [0] * (len(N_list))

for n in N_list:
    idx = count_list[n]
    result_list[idx - 1] = n
    count_list[n] -= 1

for k in result_list:
    print(k)

次のコードは、上記のエラーを回避するために、入力値の範囲10000を考慮し、arrayとして予め作成し、値を変更する方法です.
さらに説明を加えて、係数ソートをこの問題に最適化し、所定の入力値範囲のヒントを利用してメモリ使用量を減らす.

import sys

n = int(sys.stdin.readline())
array = [0] * 10001

for i in range(n):
    data = int(sys.stdin.readline())
    array[data] += 1

for i in range(10001):
    if array[i] != 0:
        for j in range(array[i]):
            print(i)

ソース:https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=vjhh0712v&logNo=221466898588

4）2108号統計学

import sys

N = int(input())
N_list = []

for i in range(N):
    x = int(sys.stdin.readline())
    N_list.append(x)

# 산술평균 출력
print(round(sum(N_list) / N))

# 중앙값 출력
N_list.sort()
print(N_list[int(len(N_list) / 2)])

# 최빈값 출력
# 계수 정렬의 아이디어를 빌려 반복되는 수를 저장할 리스트를 생성해주고, 이에 값을 담아 활용했다.

# -4000 ~ 4000까지 총 8001개를 담을 리스트 생성 (0도 포함)
count_list = [0] * 8001
for i in N_list:
	# 음수는 절댓값을 씌워 인덱스 1~4000 자리에 할당
    if i < 0:
        count_list[abs(i)] += 1
    # 양수는 4000을 더해 인덱스 4001~8000 자리에 할당
    elif i > 0:
        count_list[i + 4000] += 1
    # 0은 인덱스 0자리에 할당
    else:
        count_list[0] += 1

# 최대 반복수 구하기
maxval = max(count_list)
max_list = []
for i in range(0, len(count_list)):
	# 해당 원소가 최대 반복수일 경우 음수, 0, 양수를 따져 max_list에 저장
    if count_list[i] == maxval and i <= 4000:
        max_list.append(-i)
    elif count_list[i] == maxval and i > 4000:
        max_list.append(i-4000)
    elif count_list[i] == maxval and i == 0:
        max_list.append(i)
# 최빈값이 중복된다면 len은 1이 아니기에 가장 작은걸 지우고 그다음 작은걸 출력한다.
if len(max_list) != 1:
    max_list.remove(min(max_list))
    print(min(max_list))
# 그 외 상황은 최빈값이 하나인 경우, 따라서 그냥 출력
else:
    print(min(max_list))

# 범위 출력 (최대 - 최소)
print(max(N_list) - min(N_list))

5）1427番内線

N = int(input())
strN_list = []

for i in str(N):
    strN_list.append(i)

strN_list.sort(reverse=True)

ans = ''
for i in strN_list:
    ans+=i
print(int(ans))

6）11650番座標を揃える

2 D配列のsort()は、内部配列のiに基づいて昇順ソートされる.
したがって,この問題は関数sort()のポーリング機能を内蔵することで解決できる.
ソース:https://asxpyn.tistory.com/75

import sys

N = int(input())
# 입력한 좌표를 담아줄 2차원 배열 중 바깥 배열 생성
xy_list = []
for i in range(N):
    x, y = map(int, sys.stdin.readline().split())
    xy_list.append([x, y])

xy_list.sort()

for j in xy_list:
    print(str(j[0]) + ' ' + str(j[1]))

7）位置合わせ11651号座標2

2 Dアレイで、内部アレイの特定の値に基づいてソートする方法:
.sort(key = lambda x: (x[i]))
特定の値(iの1番目の要素)に従って昇順に並べ替えます.
.sort(key = lambda x: (x[i], x[j]))
i番インデックスの値が同じ場合は、後のj番インデックスに準じてソートします.
.sort(key = lambda x: (-x[i]))
このとき、カッコ内のxに-を付けると降順に並べられます.

import sys

N = int(input())
xy_list = []
for i in range(N):
    x, y = map(int, sys.stdin.readline().split())
    xy_list.append([x, y])

# 내부 배열의 1번째 값으로 정렬하고 같을 시 0번째 값으로 정렬
xy_list.sort(key = lambda x: (x[1], x[0]))

for j in xy_list:
    print(str(j[0]) + ' ' + str(j[1]))