[Algorithm] 정렬 알고리즘

이번엔 정렬에 대해서 알아보도록 하겠습니다. 사실 정렬의 경우 JAVA 나 Python 은 라이브러리를 제공하고 있어 왠만한 정렬과 관련된 문제가 아니라면 해당 라이브러리를 사용해도 될 것 입니다. 하지만 몇몇 문제들에서는 여러 정렬 알고리즘의 동작 원리를 알고 있는지 혹은 라이브러리에서 제공해 주는 정렬보다 빠른 정렬을 알고 있는지를 묻는 문제들이 출제되므로 정렬에 대해서 기본적인 개념을 짚고 넘어 가고자 포스트를 작성하게 되었습니다. 그렇다면 코딩 테스트를 위한 정렬에 대해서 알아보도록 하겠습니다.

선택 정렬

선택 정렬은 가장 원시적인 정렬 방법으로 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것입니다. 예제를 통해 한 번 알아보도록 하겠습니다.

리스트 안에 있는 정렬되지 않은 10개의 숫자 [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 을 가지고 진행하도록 하겠습니다.

step 0 : 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택합니다. 우리가 사용하는 리스트에서는 0과 7을 바꿔줍니다.

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

step 1 : 이제 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 1을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 5와 바꿔줍니다.

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

step 2 : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 2를 선택하고 정렬 처리 되지 않은 숫자들 중에서 가장 앞에 있는 것과 바꿔줍니다.

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

step 3 : 이 과정을 리스트에 있는 모든 요소에 대해서 진행 후에 정렬된 결과를 확인 합니다.

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

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료되는 것을 알 수 있습니다. 파이썬 코드로 작성하면 다음과 같습니다.

# 선택 정렬 예제 코드

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]: # i 인덱스 이후의 값 들 중에서 i 보다 작은 것이 있다면 min_index 변경
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 값 변경

print(array)

콘솔 출력
[0, 1, 2, 3, 5, 6, 7, 8, 4, 9]

선택 정렬의 시간 복잡도

그렇다면 선택 정렬의 시간 복잡도를 계산해 보도록 하겠습니다.
선택 정렬은 N-1번 만큼 가장 작은수를 찾아서 맨 앞으로 보내야 합니다. 또한 매번 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요합니다. 구현 바익에 따라서 작은 오차는 있을 수 있지만 앞쪽의 그림대로 구현했을 때 연산 횟수는 N + (N-1) + (N-2)+ $\cdots$ + 2로 볼 수 있습니다. 따라서 근사치로 N(N+1)/2 즉 ($N^2+N$)/2로 표현할 수 있는데 빅오 표기법으로 간단히 O($N^2$)이라고 표현할 수 있습니다. 이는 반복문을 기준으로 보았을 때 대략적으로 2중 반복문이 사용됐다고도 볼 수 있습니다.
만약 정렬해야 할 데이터의 개수가 100배 늘어나면, 이론적으로 수행 시간은 10,000배로 늘어납니다. 그러므로 선택 정렬은 평균적으로 O(NlogN) 의 시간 복잡도를 가지는 다른 정렬에 비해 굉장히 느린편에 속합니다만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서는 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있습니다.

삽입 정렬

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편입니다. 그렇다면 다른 정렬에 대해서 알아보도록 하겠습니다.
삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘 입니다. 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있습니다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 훨씬 효율적입니다.
삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부릅니다. 특히 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정합니다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징입니다. 예시를 통해 알아보도록 하겠습니다. 예시에 사용할 리스트는 [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 을 사용하도록 하겠습니다.

step 0 : 첫 번째 데이터 7은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단합니다. 우리는 오름차순으로 정렬하고자 하므로 7의 왼쪽에 삽입합니다.

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

step 1 : 이어서 9가 어떤 위치에 들어갈 지 판단합니다. 삽입될 수 있는 위치는 총 3가지 이며 현재 9는 5와 7보다 크기 때문에 원래 자리에 그대로 둡니다.

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

step 2 : 이어서 0이 어떤 위치에 들어갈지 판단합니다. 0은 5, 7, 9와 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입합니다.

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

step 3 : 이어서 3이 어떤 위치에 들어갈지 판단합니다. 0과 5 사이에 삽입합니다.

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

step 4 : 0~3 과정을 정렬이 완료될 때까지 반복합니다.

이를 파이썬 코드로 한 번 알아보도록 하겠습니다.

# 삽입 정렬 예제

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

for i in range(1, len(array)): # 1번째 인덱스 부터 리스트 마지막 인덱스까지 반복

    """
    인덱스 i부터 1까지 하나씩 감소하는 반복문 
    i부터 1까지만 역으로 감소하게 한 이유는 아래 조건문에서 j에 -1을 해주기 때문에 조건문 연산 시 0번째 인덱스도 확인하기 때문
    """
    for j in range(i, 0, -1):
        if array[j] < array[j-1]: # j와 j-1 번째의 값을 비교한 후 j 인덱스에 있는 값이 더 작을 경우 바꿔줌
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

print(array)

콘솔 출력
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O($N^2$)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었습니다. 실제로 수행 시간을 테스트해보면 아퍼 다루었던 선택 정렬과 흡사한 시간이 소요되는 것을 알 수 있습니다. 여기서 꼭 기억할 내용은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점입니다. 최선의 경우 O(N)의 시간 복잡도를 가집니다. 보통은 삽입정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 삽입정렬의 시간이 가장 빠르므로 문제 유형을 보고 삽입 정렬을 사용해야 할 때도 있습니다.

퀵 정렬

퀵 정렬은 이름 그대로 정렬 알고리즘 중에서 가장 빠르기 때문에 퀵이 붙었고, 병합 정렬과 더불아 가장 많이 사용되는 정렬입니다. 또한 퀵 정렬과 병합 정렬은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 합니다. 그렇다면 퀵 정렬에 대해서 알아보도록 하겠습니다.
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작합니다. 퀵 정렬에는 피벗(pivot)이 사용됩니다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준을 피벗이라고 합니다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 합니다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 이번에는 가장 대표적인 방식인 호어 분할(Hoare Partition) 방식을 기준으로 설명해 보겠습니다. 호어 분할 방식은 리스트에서 첫 번째 데이터를 피벗으로 정한다 입니다. 이를 토대로 스텝별로 설명을 해보도록 하겠습니다. 아래는 사용할 예시 데이터 입니다.

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

퀵 정렬은 3가지 파트로 나누어서 보는 것이 이해가 빠릅니다. 그리고 피벗이 되는 숫자를 파란색, 피벗에 의해 위치가 바뀔 숫자들을 빨간색으로 표시하도록 하겠습니다.

step 0 : 리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 5입니다. 이후에 왼쪽에서 부터 5보다 큰 데이터를 선택하므로 7이 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 4가 선택됩니다. 그리고 이 두 데이터의 위치를 서로 변경합니다.

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

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

step 1 : 0 번째 step 에서 왼쪽과 오른쪽에서 인덱스를 하나씩 옮긴 후 같은 과정을 진행해 줍니다.

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

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

step 2 : step 0을 반복하다 보면 찾는 값의 위치가 서로 엇갈릴 때가 있습니다. 이렇게 두 값이 엇갈린 경우에는 작은 데이터와 피벗의 위치를 서로 변경합니다. 이렇게 엇갈릴 때는 왼쪽의 인덱스가 오른쪽의 인덱스보다 커질 때이므로 이를 조건으로 이용하면 됩니다.

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

step 3 : 분할 완료 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴봅시다. 이제 5의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 5보다 크다는 특징이 있습니다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할 혹은 파티션이라고 합니다.

step 4 : 피벗을 기준으로 분할된 오른쪽과 왼쪽 각각을 step 0~3 과정을 반복해서 진행을 하면 정렬이 됩니다.

step 5 : 이렇게 정렬을 진행하다 정렬을 하고자 하는 리스트의 원소가 1개인 경우 정렬을 종료합니다.

이제 파이썬 예제 코드로 한 번 알아보도록 하겠습니다.

# 퀵 정렬 예제

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

콘솔 출력
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵 정렬의 시간 복잡도

퀵 정렬의 시간 복잡도는 평균적으로 O(NlogN) 으로 선택 정렬보다는 무조건 빠르고, 삽입 정렬과는 비교했을 때 삽입 정렬의 특수한 케이스를 제외하곤 퀵 정렬이 빠릅니다. 퀵 정렬이 빠른 이유에 대해서는 수학적으로 증명할 수 있지만 이는 추후에 좀 더 심화해서 다룰 때 알아보도록 하겠습니다. 다만 퀵 정렬의 시간 복잡도에 대해 한 가지 기억해둘 것이 있는데 그건 바로 퀵 정렬은 평균적으로 시간 복잡도가 O(NlogN) 이지만 최악의 경우 시간 복잡도가 O($N^2$)이라는 것입니다. 데이터가 무작위로 입력될 경우 퀵 정렬은 빠르게 동작할 확률이 높습니다. 하지만 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작합니다. 그래서 여러 프로그래밍 언어에서 제공해 주는 정렬 라이브러리 중 퀵 정렬을 사용하는 라이브러리의 경우 시간 복잡도가 O(NlogN)이 되는 것을 보장할 수 있도록 피벗값ㅇ르 설정할 때 추가적인 로직을 더해줍니다. 파이썬 또한 마찬가지로 기본 정렬 알고리즘을 이용하면 O(NlogN)을 보장해주기 때문에 크게 걱정 없이 사용해도 됩니다.

계수 정렬

계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘입니다. 모든 데이터가 양의 정수인 상황을 가정해봅시다. 데이터의 개수가 N, 데이터 중 최댓값이 K 일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장합니다. 계수 정렬은 이처럼 매우 빠르게 동작할 뿐만 아니라 원리 또한 매우 간단합니다. 다만, 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있습니다. 예를 들어 데잍의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵습니다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있습니다.
예를 들어 0 이상 100 이하인 성적 데이터를 정렬할 때 계수정렬이 효과적입니다. 다만, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없습니다. 계수 정렬이 이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문입니다. 예를 들어 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화해야 합니다. 여기에서 1개를 더해주는 이유는 0부터 1,000,000까지는 총 1,000,001개의 수가 존재하기 때문입니다.
계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아닙니다.
계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있습니다. 구체적인 예시를 통해 계수 정렬에 대해서 이해해봅시다. 단, 말했듯이 계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작합니다. 따라서 예시 또한 앞서 다루었던 예시와 다르게 많은 데이터가 존재하는 경우를 살펴봅시다.

• 초기 단계 : [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

계수 정렬은, 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성합니다. 현재 예시에서는 가장 큰 데이터가 9이고 가장 작은 데이터가 0입니다. 따라서 우리가 정렬할 데이터의 범위는 0부터 9까지이므로 리슽의 인덱스가 모든 범위를 포함할 수 있도록 합니다. 다시 말해 우리는 단순히 크기가 10인 리스트를 선언하면 됩니다. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화합니다. 그 다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킵니다. 그리고 정렬해야 할 리스트의 숫자들을 인덱스로 각 숫자들이 카운팅된 리스트에서 인덱스 순서대로 카운팅 된 개수 만큼 그 인덱스의 숫자를 출력하면 정렬이 되는 것입니다. 예제 코드로 확인해 보도록 하겠습니다.

# 계수 정렬 예제

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

array_max = max(array)

# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count_array = [0] * (array_max+1)

for i in range(len(array)):
    count_array[array[i]]+=1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count_array)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count_array[i]):
        print(i, end = " ") # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

콘솔 출력
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있습니다. 예를 들어 데이터가 0과 999,999 단 두개만 존재한다고 가정해보겠습니다. 이럴 때에도 리스트의 크기가 100만 개가 되도록 선언해야 합니다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장하고, 정렬해야 하는 숫자의 범위 적을 때 적합합니다. 예를 들어 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적입니다. 반면에 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 때문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리합니다.
다시 말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없습니다. 하지만 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적으로 사용할 수 있습니다. 다만 일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간 문제로 인하여 입력되는 데이터의 개수를 1,000만 개 이상으로 설정할 수 없는 경우가 많기 때문에, 정렬 문제에서의 데이터 개수는 1,000만 개 미만으로 출제될 것입니다. 계수 저렬의 공간 복잡도는 O(N+K) 이며 시간 복잡도는 O(N)입니다.

파이썬의 정렬 라이브러리 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장합니다. 사실 정렬 라이브러리는 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때보다 더욱더 효과적입니다. 앞서 파이썬은 병합 정렬에 기반한다고 했는데 정확히는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있습니다. 책에서 자세히 다루지 않지만, 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하면 됩니다. 따라서 코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있습니다.

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있습니다.

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있습니다.

3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있습니다.

마치며

이번엔 정렬 알고리즘에 대해서 알아보았습니다. 위 본문에서도 말했지만 정렬의 경우 프로그래밍 언어에서 제공해 주는 라이브러리를 사용하는 것이 가장 좋습니다. 다만 간혹 시간 초과가 나는 경우가 있으며 혹은 여러 다른 정렬의 중간 결과가 답으로 된 경우와 같이 특정 정렬 알고리즘을 알고 있는지에 대한 문제가 출제되는 경향도 있습니다. 이를 위해 여러 알고리즘에 대해서 간략하게 알아 보았습니다. 그래도 일반적인 여러 문제들을 풀 때 정렬이 필요하다면 라이브러리를 사용하는 것이 좋아 보입니다. 이번엔 정렬 알고리즘에 대한 개념만 정리를 해보았고 추후에 관련해서 문제 풀이에 대한 것도 다뤄보도록 하겠습니다. 긴 글 읽어주셔서 감사드리며 내용 중에 잘못된 내용 혹은 오타가 있거나 궁금하신 내용이 있으시면 댓글 달아주시기 바랍니다!