정렬 알고리즘

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 의 책과 강의를 보고 정리한 글입니다.
강의 출처 : 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

정렬되지 않은 데이터가 하나 남았을 경우 처리하지 않아도 된다.

탐색 범위는 반복할 때마다 줄어들게 되고 가장 작은 데이터를 찾기 위해 탐색 범위만큼 데이터를 확인해야 하기 때문에 매번 선형 탐색을 시행해야 한다. 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로 표현할 수 있는데, 빅오 표기법에 따라 O(N^2)이다.

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다. 선택 정렬에 비해 구현 난이도가 높지만 더 효율적이다.

7 5 9 0 3 1 6 2 4 8

첫 번째 데이터 7은 그 자체로 정렬이 되어 있다고 판단하고 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단한다. 7의 왼쪽 or 오른쪽 두 경우만 존재.

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)이고, 이중 for문으로 구성된다. 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. (최선의 경우 O(N))

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법. 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

5 7 9 0 3 1 6 2 4 8

현재 피벗의 값은 5이다. 왼쪽에서부터 5보다 큰 데이터를 선택하므로 7이 선택되고 오른쪽에서부터 5보다 작은 데이터를 선택하므로 4가 선택된다. 이 두 데이터의 위치를 서로 변경 한다.

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 높이 = N x 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)

퀵 정렬 : 파이썬의 장점을 살린 방식

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과 가장 큰 9. 0~9 데이터 범위의 리스트를 초기화한다.

데이터를 하나씩 확인하여 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.

결과를 확인할 때는 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다.

결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 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과 999,999 단 2개만 존재하는 경우.. ㄷㄷ)
동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있음(성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적)

정렬 알고리즘 비교

<문제> 두 배열의 원소 교체

두 배열 A, B는 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 최대 K 번의 바꿔치기 연산을 수행할 수 있는데 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 바꾸는 것을 말한다.
최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.

N, K, 그리고 배열 A와 B의 정보가 주어졌을 때 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

예) N = 5, K = 3, A = [1, 2, 5, 4, 3], B = [5, 5, 6, 6, 5]
1과 6, 2와 6, 3과 5

결과 : A = [6, 6, 5, 4, 5], B = [3, 5, 1, 2, 5] 답 : 26

두 배열의 원소가 100,000개까지 입력될 수 있으므로 최악의 경우 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))