[이론] 정렬

선택정렬

목표

1. 0번째에 와야하는 값을 찾아서 0번째 값과 교환합니다.
2. 1번째에 와야하는 값을 찾아서 2번째 값과 교환합니다.
3. …
4. i번째에 와야하는 값을 찾아서 i번째 값과 교환합니다.

시간복잡도

• 평균 : O(N^2)

알고리즘

i번째 와야하는 값을 찾기 위해서 (i+1, len)까지 탐색한 뒤 교환합니다.

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

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

print(arr)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입정렬

목표

1. 0번째 값은 이미 정렬된 상태입니다.
2. 1번째 값을 정렬 순서에 맞게 가장 왼쪽으로 옮깁니다.
3. …
4. i번째 값을 정렬 순서에 맞게 가장 왼쪽으로 옮깁니다.

시간복잡도

• 평균 : O(N^2)

알고리즘

i의 번째 값이 정렬 순서에 맞게 왼쪽으로 한칸씩 이동합니다.

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

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
            
print(arr)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵정렬

목표

1. i번째 값을 pivot으로 설정합니다.
2. pivot 값을 최종 목적지로 이동시킵니다.
3. pivot을 중심으로 좌/우를 각각 다시 퀵정렬을 합니다.

시간복잡도

• 평균 : O(NlogN)

알고리즘

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


def quick_sort(arr, start, end):
    if start >= end:  # 원소가 1개인 경우 종료
        return

    pivot = start
    left = start + 1
    right = end

    while (left <= right):
        # pibot 보다 큰 값을 찾을 때까지 반복
        while (left <= end and arr[left] <= arr[pivot]):
            left += 1
        # pivot 보다 작은 값을 찾을 때까지 반복
        while (right > start and arr[right] >= arr[pivot]):
            right -= 1
        # 엇갈렸다면 더 작은 값(right)와 pivot을 교환
        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)


quick_sort(arr, 0, len(arr) - 1)
print(arr)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

계수정렬

시간복잡도

• 평균 : O(N+K)

목적

1. 0이 몇 번 등장하는지 센다.
2. 1이 몇 번 등장한는지 센다.
3. …
4. 0을 등장한 횟수만큼 출력한다.
5. 1을 등장한 횟수만큼 출력한다.

알고리즘

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
count = [0] * (max(arr)+1)

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=' ')

# 0 1 2 3 4 5 6 7 8 9

Success Notice: 수고하셨습니다.