ソートの選択

:最小を選択するたびに、前のデータとswapを

インプリメンテーション

for i in range(len(arr)):
	min_idx = i
	for j in range(i+1, len(arr)):
		if arr[min_idx] > arr[j]:
				min_idx = j

	#python에서의 swap
	arr[min_idx], arr[j] = arr[j], arr[min_idx]

時間の複雑さ

(検索最小数:N-1)*(比較ごとに検索最小数:N+(N-1)+(N-2)+...+2)
≈ N*(N+1) → O(N^2)
→非効率なソート方法

整列挿入

:適切な場所にデータを挿入し、同時にデータを1つずつ検査する
→位置を揃える前に

インプリメンテーション

for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        if arr[j-1] > arr[j]:
            arr[j-1], arr[j] = arr[j], arr[j-1]
        else:
            break

→データがほぼ整列している場合、より効率的

時間の複雑さ

O(N^2)
→ほぼ整列時最大O(N)

クイックソート

:条件データを設定した後、その条件より大きいまたは小さいデータ位置を変更します.
→最初のデータを軸とする

インプリメンテーション

def quick_sort(arr, start, end):
    #원소가 1개인 경우 종료
    if start >= end:
        return
    #맨 첫번째원소를 피봇으로
    pivot = start
    left = start+1
    right = end

    while left <= right:
        #피봇보다 큰 데이터 찾을때까지
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        #피봇보다 작은 데이터 찾을때까지
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        
        #엇갈린 경우 작은 데이터와 피봇 교체
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:
            arr[left], arr[right] = arr[right], arr[left]
        
    #피봇 기준 왼쪽, 오른쪽 부분에 대해 정렬 수행
    quick_sort(arr, start, right-1)
    quick_sort(arr, right+1, end)

→さらにPython化

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    tail = arr[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)

時間の複雑さ

最悪なのは、O(N^2)→ソートされたデータについて
平均値:O(Nlogn)

ソート数

:データのサイズ範囲が限られており、整数で表すことができる場合に使用します.

abs(最大(arr)-分(arr)<100000)

は比較に基づくアルゴリズムではなく、

である.

有利な場合

データのサイズ制限は

である.

重複データ

インプリメンテーション

for i in range(len(arr)):
    count[arr[i]] +=1 

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

arr : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

最大および最小のデータ範囲を含むリストの作成

データを1つずつ表示し、データ値と同じインデックスデータを追加

リストの最初のデータからインデックスを値で出力

時間の複雑さ

データのサイズN,最大値KのO(N+K)

くうかんふくざつさ

能率が落ちる
e.g.09999992 2個のデータが存在する場合、リストサイズは100万個