[이코테] Chapter6-1 / 기준에 따라 데이터를 정렬

정렬 알고리즘 개요

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary Search)이 가능해진다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬 알고리즘은 굉장히 다양한데, 이 중에서 많이 사용하는 선택정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 책에서 언급하려 한다. 더불어 파이썬에서 제공하는 기본 정렬 라이브러리를 적용하여 좀 더 효과적인 정렬 수행 방법도 다루려 한다. 

보통 정렬부터 공부하면 '알고리즘의 효율성'을 쉽게 이해할 수 있어 알고리즘 개론서 초반에 정렬 알고리즘을 설명하는 경우가 많다. 또한 일반적으로 문제에서 요구하는 조건에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 상황에 적절하지 못한 정렬 알고리즘을 이용하면 당연히 프로그램은 비효율적으로 동작하며 필요 이상으로 시간을 많이 소요한다. 그래서 정렬 알고리즘을 공부하다보면 자연스럽게 알고리즘 효율의 중요성을 깨닫는다.

이 책은 코딩 테스트 합격을 주목적으로 하기 때문에, 그리디 유형과 구현 유형에 대해서 먼저 다루었지만 정렬 알고리즘은 또한 매우 중요하다. 면접에서도 단골 문제로 출제된다는 점을 기억하자.

이제 문제 상황에 대해서 생각해보자. 여기 숫자가 하나씩 적힌 카드가 10장 있다. 이제 이 카드를 오름차순으로 정렬하자.

정렬 알고리즘

어떻게 이 데이터(카드)를 정렬할 수 있을까? 보통은 카드를 빠르게 훑고 숫자가 0부터 9까지로 구성된 걸 눈치챈 다음 카드를 0부터 9까지 순차적으로 나열할 것이다. 이러한 과정 속에서 우리의 뇌는 우리도 모르게 데이터의 규칙성을 파악한다. 

하지만 우리에게 쉽다고 컴퓨터에게도 쉬운 일은 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

이 카드 예제를 기준으로 이번 장에서는 정렬 알고리즘을 설명하겠다. 또한 이 장에서 다루는 예제는 모두 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬을 수행하는 알고리즘에서 크기 비교를 반대로 수행하면 된다. 또한 파이썬에서는 특정한 리스트의 원소를 뒤집는 메서드를 제공한다. 그래서 내림차순 정렬은 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기(Reverse)하여 내림차순 리스트를 만들 수 있다. 리스트를 뒤집는 연산은O(N)의 복잡도로 간단히 수행할 수 있으므로 이 책에서 오름차순을 위한 소스코드만 다르도록 한다.

 

선택 정렬

컴퓨터가 데이터를 정렬할 때 어떻게 할지 한번 생각해보자. 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까?  이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택' 한다는 의미에서 선택 정렬(Selection Sort) 알고리즘이라고 한다.

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다. 이해를 돕기위해 예제를 통해 자세한 동작 원리를 확인하겠다.

정렬 알고리즘에서는 흔히 데이터의 개수를 N이라고 표현한다. 다음 예제에서는 N = 10인 경우를 가정한다. 또한 다음의 그림에서 회색 카드는 '현재 정렬되지 않은 데이터 중에서 가장 작은 데이터'를 의미하며, 하늘색 카드는 '이미 정렬된 데이터'를 의미한다.

선택 정렬 그림 설명

[Stpe 0] 

• 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 '0'을 선택해 맨 앞에 있는 데이터 '7'과 바꾼다.

[Step 1]

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

  

[Step 2]

• 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '2'를 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9'와 바꾼다.

  

[Step 3]

• 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '3'을 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '7'과 바꾼다.

  

-- 중략 --

[Step8]

[Step 9]

• 가장 작은 데이터를 앞으로 보내는 과정을 9번 반복한 상태는 다음과 같으며 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 따라서 이 단계에서 정렬을 마칠 수 있다.

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

[6-1.py] 선택 정렬 소스코드

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]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

print(array)

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

다만 이 코드는 스와프(Swap)에 대해서 모른다면 이해하기 어려운 부분이 있다. 스와프란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미한다. 파이썬에서는 다음처럼 간단히 리스트 내 두 원소의 위치를 변경할 수 있다. 하지만 다른 대부분의 프로그래밍 언어에서는 명시적으로 임시 저장용 변수를 만들어 두 원소의 값을 변경해야 한다.

[6-2.py] 파이썬 스와프(Swap) 소스코드

# 0인덱스와 1 인덱스의 원소 교체하기
array = [5, 3]
array[0], array[1] = array[1], array[0]

print(array)

[3, 5]

다른 언어에서도 별도의 스와프 함수가 있지만 파이썬만큼 간편하지는 않다. 다음은 C언어에서 표준 라이브러리를 사용하지 않고 2개의 변수 a와 b의 값을 서로 교체하도록 작성한 코드이다. 다음의 코드는 비교용으로 작성된 코드로, 완전한 C 언어 코드 형태가 아니다.

[C언어로 구현한 스와프 예제]

int a = 3;
int b = 5;

// 스와프 진행
int temp = a;
a = b;
b = temp;

 

선택 정렬의 시간 복잡도

그렇다면 선택 정렬의 시간 복잡도를 계산해보자.

선택 정렬은 N - 1 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 구현 방식에 따라서 사소한 오차는 있을 수 있지만 앞쪽의 그림대로 구현했을 때
연산 횟수는 N + (N -1) + (N - 2) + ... + 2로 볼 수 있다.
따라서 근사치로 N * (N + 1) / 2번의 연산을 수행한다고 가정하자.
이는 (N^2 + N) /2로 표현할 수 있는데, 빅오 표기법으로 간단히 O(N^2)이라고 표현할 수 있다.
빅오 표기법은 1장의 '시간 복잡도'에서 설명했으니 참고하자.

이전 장에서 반복문이 얼마나 중첩되었는지를 기준으로 간단히 시간 복잡도를 판단할 수 있다고 하였다.
선택 정렬의 시간 복잡도는 O(N^2)이다. 직관적으로 이해하자면, 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이라고 이해할 수 있다.

만약 정렬해야 할 데이터의 개수가 100배 늘어나면, 이론적으로 수행 시간은 10,000배로 늘어난다. 그렇다면, 이러한 시간 복잡도를 가지는 선택 정렬이 얼마나 효율적일까?

한 번 알고리즘 수행 시간을 측정해보자. 다음 표는 파이썬 3.7의 선택 정렬 알고리즘과 이후에 다룰 퀵 정렬 알고리즘, 그리고 기본 정렬 라이브러리의 수행 시간을 비교한 결과이다. 측정 시간은 각각의 컴퓨터마다 다를 수 있다. 선택 정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려지는 것을 확인할 수 있다. 또한 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C 언어 기반이며, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다.

정렬 알고리즘 수행 시간

선택 정렬은 기본 정렬 라이브러리를 포함해 뒤에서 다룰 일고리즘과 비교했을 때 매우 비효율적이다.
다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다. 그러므로 선택 정렬 소스코드를 자주 작성해볼 것을 권한다.

 

삽입 정렬

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 그렇다면 다른 접근 방법에 대해서 생각해보자.

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?'

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 물론 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요한 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬(Insertion Sort)이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다. 다음과 같이 초기 데이터가 구성되어 있다고 가정하자.

삽입 정렬

삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

[Step 0]

[Step 1]

[Step 2]

[Step 3]

--중략--

[Step 7]

[Step 8]

[Step 9]

삽입 정렬은 재미있는 특징이 있는데, 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다는 점이다. [Step] 그림을 보면 하늘색으로 칠해진 카드들은 어떤 단계든지 항상 정렬된 상태다. 이러한 특징 때문에 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 위치를 선정할 때(삽입될 위치를 찾기 위하여 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다. 예를 들어 [Step 3] 을 다시 살펴보자.

[Step 3] 에서 '3'은 한 칸씩 왼쪽으로 이동하다가 자신보다 작은 '0'을 만났을 때 그 위치에 삽입된다. 
다시 말해 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는 것이다. 이제 소스코드를 확인해보도록 하자.

# 삽입 정렬
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까지 감소하며 반복하는 문법 - 이것을 사용한 이유는, 삽입 정렬의 경우 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요가 없기 떄문이다.
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

 

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 실제로 수행 시간을 테스트해보면 앞서 다루었던 선택 정렬과 흡사한 시간이 소요되는 것을 알 수 있다. 여기서 꼭 기억할 내용은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우 O(N)의 시간 복잡도를 가진다. 바로 다음에 배울 퀵 정렬 알고리즘과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다. 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

 

퀵 정렬

퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 이 책에서 다루지는 않지만 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 '병합 정렬' 알고리즘이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 그렇다면 퀵 정렬은 도대체 어떻게 동작하길래 이름부터가 '빠른 정렬 알고리즘'인지 알아보자.

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?'

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 이해하기까지 시간이 걸리겠지만 원리를 이해하면 병합 정렬, 힙 정렬 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할 수 있다.

퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 책에서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 퀵 정렬을 설명하겠다. 호어 분할 방식에서는 다음과 같은 규칙에 따라서 피벗을 설정한다. 

✓ 리스트에서 첫 번째 데이터를 피벗으로 정한다.

이와 같이 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행된다. 자세한 과정은 그림으로 살펴보며 이해해보자. 

다음과 같이 초기 데이터가 구성되어 있다고 가정해보자.

퀵 정렬은 전체를 3개의 파트로 나눠서 보는게 편하다. 편의상 I, II, III 파트로 나눠서 보겠다.

I  파트

[Step 0]

[Step 1]

[Step 2]

[Step 3] - 분할 완료

이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보자.이제 '5'의 왼쪽에 있는 데이터는 모두 '5'보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

이러한 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬시키면 어떨까? 어차피 왼쪽 리스트는 어떻게 정렬되어도 모든 데이터가 '5'보다 작다. 마찬가지로 오른쪽 리스트 또한 어떻게 정렬되어도 모든 데이터가 '5'보다 크다. 따라서 왼쪽 리스트와 오른쪽 리스트에서도 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어질 것이다.

II 파트

왼쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

 

III 파트

오른쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

이 과정은 종이를 잘라 숫자를 적은 다음에 직접 한번 해보기를 권한다. 그러면 더 빠르게 이해할 수 있으리라 본다.

퀵 정렬에서는 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 5장에서 다루었던 '재귀 함수'와 동작 원리가 같다. 실제로 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다. 재귀 함수 와 동작 원리가 같다면, 종료 조건도 있어야 할 것이다. 퀵 정렬이 끝나는 조건은 언제일까? 바로 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 1개라면, 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다. 따라서 이러한 과정을 전체적으로 살펴보면 다음과 같이 정리할 수 있다. 퀵 정렬을 처음 접한 독자라면 다음 그림에서의 분할 과정을 곧바로 이해하기는 쉽지 않겠지만, 곧이어 등장할 소스코드와 함께 살펴보면 비로소 이해할 수 있을 것이다.

다음 소스코드 형태는 널리 사용되고 있는 가장 직관적인 형태의 퀵 정렬 소스코드다.

[6-4.py] 퀵 정렬 소스코드

# 6-4.py 퀵 정렬 소스코드

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 = left + 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right = right - 1
        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[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)

[출력]

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

 

다음은 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드다. 전통 퀵 정렬의 분할 방식과는 조금 다른데, 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서는 조금 비효율적이다. 하지만 더 직관적이고 기억하기 쉽다는 장점이 있다.

 

[6-5.py] 파이썬의 장점을 살린 퀵 정렬 소스코드

# 6-5.py 파이썬의 장점을 살린 퀵 정렬 소스코드

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(N^2)이라고 하였따. 선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도 O(N^2)을 보장한다. 퀵정렬의 평균 시간 복잡도는 O(NlogN)이다. 앞서 다루었던 두 정렬 알고리즘에 비해 매우 빠른 편이다.

퀵 정렬이 어떻게 평균적으로 O(NlogN)의 시간 복잡도를 가지는지 궁굼할 수 있는데, 퀵 정렬의 시간 복잡도에 증명은 초보자가 다루기에는 간단하지 않다. 더불어 코딩 테스트를 목적으로 하는 경우, 퀵 정렬의 시간 복잡도 증명에 대하여 자세히 알지 못해도 큰 무리가 없다. 따라서 책에서는 구체적인 증명보다는 직관적인 이해를 돕기 위한 설명에 초점을 맞추어 전개하고자 한다.

퀵 정렬에서 최선의 경우를 생각해보자. 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면 어떨까? 데이터의 개수가 8개라고 가정하고 다음과 같이 정확히 절반씩 나눈다고 도식화를 해보자. 이때 '높이'를 확인해보면, 데이터의 개수가 N개일 때 높이는 약 logN이라고 판단할 수 있다. 

퀵정렬 시간복잡도

다시 말해 분할이 이루어지는 횟수가 기하급수적으로 감소하게 되는 것이다. 일반적으로 컴퓨터 과학에서 log의 의미는 밑이 2인 로그를 의미한다.  즉 log(아래2)N을 의미하며 데이터의 개수 N이 1,000일 때 log(아래2)N은 10가량이다. N = 1,000일 때 log(아래2)N ≈ 10은 상대적으로 매우 작은 수임을 이해할 수 있다. 

데이터의 개수가 많을수록 차이는 매우 극명하게 드러난다. 다음 표를 보면 데이터의 개수가 많을수록 퀵 정렬은 앞서 다루었던 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작하리라 추측할 수 있다. 표는 '평균 시간 복잡도'를 기준으로 각 정렬 알고리즘이 데이터의 개수에 따라 얼마나 많은 연산을 요구하는지를 보여주기 위해 작성되었으며, 엄밀한 연산 횟수 비교는 아니다.

정렬 알고리즘 시간복잡도

일반적으로 컴퓨터공학과 학부에서 퀵 정렬을 공부할 때에는 퀵 정렬의 수학적인 검증에 대해서도 공부하지만, 코딩 테스트를 준비하는 과정에서는 그림을 통해 직관적인 이해를 하는 것만으로도 충분하다.

다만, 퀵 정렬의 시간 복잡도에 대하여 한 가지 기억해둘 점이 있다. 바로 평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 시간 복잡도가O(N^2)이라는 것이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 이 책에서의 퀵 정렬처럼 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.

앞서 다룬 삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대된다고 이해할 수 있다.

그래서 실제로 C++와 같이 퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간 복잡도가 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가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다. 

계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 구체적인 예시를 통해 계수 정렬에 대해서 이해해보자. 단, 말했듯이 계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작한다. 따라서 예시 또한 앞서 다루었던 예시와 다르게 많은 데이터가 존재하는 경우를 살펴보자.

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

 

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

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

 

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

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

 

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

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

 

-- 과정 반복 --

 

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

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

 

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

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

결과적으로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. 예를 들어 5 인덱스의 값이 2이므로 '5'는 2번 등장한 것이다. 이 리스트에 저장된 데이터 자체가 정렬된 형태 그 자체라고 할 수 있다. 정렬된 결과를 직접 눈으로 확인하고 싶다면 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 된다. 예를 들면 '0' 인덱스의 값이 2이므로 0을 2번 출력하면 된다.

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

출력 결과 : 0 0

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

출력 결과 : 0 0 1 1

 

-- 과정 반복 --

 

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

출력 결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 

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

출력 결과 : 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

 

[6-6.py] 계수 정렬 소스코드

# 6-6.py 계수 정렬 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 점위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)  # [0]이 array의 최대값만큼의 개수가 만들어져야 하므로 list index의 특성상 +1을 해줌

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

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

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

 

계수 정렬의 시간 복잡도

앞서 언급했듯이 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N+K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다. 
따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 사실상 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.

보통 기수 정렬은 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다. 다만 알고리즘 원리나 소스코드는 더 복잡하다. 다행히 반드시 기수 정렬을 이용해야만 해결할 수 있는 문제는 코딩 테스트에서 거의 출제되지 않으므로, 책에서는 기수 정렬에 대해서 자세히 다루지는 않는다. 

 

계수 정렬의 공간 복잡도

계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999 단 2개만 존재한다고 가정해보자. 이럴 떄에도 리스트의 크기가 100만개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 예를 들어 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다. 반면에 앞서 설명한 퀵 정렬은 일반적인 경우에서 평균적으로 빠르게 동작하기 떄문에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.

다시말해 계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다. 하지만 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 많을 때에도 효과적으로 사용할 수 있다. 다만 일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간 문제로 인하여 입력되는 데이터의 개수를 1,000만 개 이상으로 설정할 수 없는 경우가 많기 때문에, 정렬 문제에서 데이터 개수는 1,000만 개 미만으로 출제될 것이다. 계수 정렬의 공간 복잡도는 O(N+K)이다.

 

 

파이썬의 정렬 라이브러리

알고리즘은 오랫동안 연구된 분야이며, 특히 정렬 알고리즘은 매우 많이 연구된 주제이다. 그렇기 때문에 정렬 알고리즘은 이 밖에도 매우 다양한 종류가 있다.  물론, 정렬 알고리즘은 정립되어 있기 때문에 앞으로는 큰 개선이 이루어질 것으로 예상하기는 어렵다. 따라서 정렬 알고리즘 문제는 어느정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제라고 할 수 있다.

지금까지 다양한 정렬 알고리즘에 대해서 알아보았다. 우리가 알고리즘 문제를 풀 때는 앞서 다루었던 예제처럼 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 더 많다.

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다. * 이러한 sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다. 

[6-7.py] sorted 소스코드

# 6-7.py sorted 소스코드

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

result = sorted(array)
print(result)

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

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있다. 리스트 객체의 내장 함수인 sort()를 이용하는 것인데, 이를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

 

[6-8.py] sort 소스코드

# 6-8.py sort 소스코드

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

array.sort()
print(array)

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

또한 sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다. key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다. 예를 들어 리스트의 데이터가 튜플로 구성되어 있을 때, 각 데이터의 두 번째 원소를 기준으로 설정하는 경우 다음과 같은 형태의 소스코드를 작성할 수 있다. 혹은 람다(Lambda)함수를 사용할 수도 있는데, 자세한 내용은 부록부분에서 확인하도록 하겠다.

 

[6-9.py] 정렬 라이브러리에서 Key를 활용한 소스코드

# 6-9.py 정렬 라이브러리에서 key를 활용한 소스코드

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result = sorted(array, key = setting)   # Sorted의 key 파라미터의 기능은 함수를 리스트 요소에 매핑해주는 것
print(result)

[('바나나', 2), ('당근', 3), ('사과', 5)]

실제로 sorted() 함수가 실행될 때 내부의 setting 함수에 들어가는 대상은 array 리스트 전체가 아니라 array 리스트의 element인 각 튜플이다. setting(array[1]) 넣으면 array의 두번째 element인 튜플 ('사과', 5)의 두 번째 element인 5가 출력될 것이다.

즉, 함수를 리스트(array)의 길이 횟수 만큼 실행해서 각 튜플의 [1]번째 값을 모두 반환해서 정렬하는 것 이다.

즉 6-9.py 예제의 경우 data = ('str', 'int') 에서 data[1]인 'int'를 기준으로 정렬하게 된다.

 

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

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

코딩 테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다. 

이 책에서는 이 3가지 유형을 모두 다룰 것이다. 일단 이번 장에서는 가장 기본적인 문제 3개를 풀어보도록 하자.