📂알고리즘

비교 정렬 알고리즘들의 시간 복잡도

정리

$n$ 개의 데이터가 주어져 있을 때, 비교 정렬 알고리즘들의 시간 복잡도는 다음과 같다.

• [1] 버블 정렬: $$ \Theta ( n^2 ) \\ O ( n^2 ) $$
• [2] 선택 정렬: $$ \Theta ( n^2 ) \\ O ( n^2 ) $$
• [3] 삽입 정렬: $$ \Theta ( n^2 ) \\ O ( n^2 ) $$
• [4] 힙 정렬: $$ \Theta ( n \log n ) \\ O ( n \log n ) $$
• [5] 합병 정렬: $$ \Theta ( n \log n ) \\ O ( n \log n ) $$
• [6] 퀵 정렬: $$ \Theta ( n \log n ) \\ O ( n^2 ) $$

설명

여기서 소개되는 알고리즘들이 어떠한 원리인지 하나하나 설명하지는 않겠다. 원리와 구현 자체를 잘 설명한 문서가 너무 많기도하고, 생새우초밥집이 중요하게 생각하는 관점은 그와 거리가 제법 있기 때문이다.

정렬 알고리즘은 거의 모든 프로그래밍에 동원되는데, ‘단순히 구현되기만 하는 것’과 ‘대체로 가장 우수한 알고리즘을 신뢰하는 것’만으로는 단어 그대로 ‘최적화’를 할 수가 없다. 보다시피 단순한 정렬 알고리즘들은 정렬에 성공할지라도 너무 긴 시간을 낭비하지만, 오히려 특정한 조건에서는 더욱 복잡한 알고리즘보다 높은 퍼포먼스를 낼 수도 있다는 사실을 알아야한다. 이러한 차이점을 명확하게 이해하고 적재적소에 알고리즘을 사용하는 것이 프로그래머의 역할이다.

[1] 버블 정렬

움짤에서 확인할 수 있듯 수면 아래의 거품이 떠오르는 듯한 꼴을 하는데에서 붙여진 이름이다. 시간 복잡도의 측면에서는 비교 정렬 알고리즘 중에서 가장 열등하나, 코드 구현이 아주 간단해서 패키지, 내부 함수에 기댈 수 없을 정도로 열악한 환경에서 금방 짜서 사용해볼만하다.

[2] 선택 정렬

정렬되지 않은 영역에서 가장 큰 수 하나만을 옮기는 방법이므로 전체 데이터를 기억하는 것 외에는 가장 큰 수 하나만을 기억하면 충분하다. 시간 복잡도의 측면에서는 열등하나, 공간 복잡도의 측면에서는 아주 우수하다.

[3] 삽입 정렬

배열에서 하나씩 빼면서($n$ 번) 새로운 배열의 어디쯤 있어야할지 찾아($n$ 번) 삽입하는 알고리즘이므로 $O(n^2)$ 인 것은 사실이나, 이미 배열이 거의 다 정리되어있다면 새로운 위치를 찾는 과정에 시간을 쓸 필요가 없으므로 거의 $\Theta ( n)$ 에 준하는 시간이 들 수 있다. 실제 프로그래밍에서 ‘이미 배열이 거의 다 정리되어있는’ 상황이란 곧 배열의 크기가 작은 상황을 말한다. 가령 $n < 20$ 정도로 작다면 단순한 운으로라도 배열이 거의 다 정리 된 상황이 종종 나올 수 있다.

[4] 힙 정렬

힙 자료 구조를 이용한 방법으로써, 힙이 구성되어있기만 하다면 $O ( \log n )$ 의 시간만으로 정렬을 할 수 있다. 힙을 구성하는데에는 $O( n)$ 만큼의 시간이 필요한데, 이것을 감안하더라도 [1]~[3]에 비하면 아주 빠르다. 힙 정렬이 특별히 유리한 부분은 정렬을 한 번에 처리하지 않는 상황이다. 힙 소팅에서 가장 많은 시간을 소비하는 것은 힙을 구성하는 단계인데, 지속적으로 조금씩 데이터가 추가된다면 이미 구성된 힙을 보수하는 것은 큰 부담이 안 되고 힙만 구성되어있다면 소팅 자체는 엄청나게 빠르기 때문이다.

[5] 합병 정렬

폰 노이만에 의해 개발된 알고리즘으로, 시간복잡도가 $O ( n \log n )$ 으로 무척 빠를 뿐만 아니라 동일한 값의 원소들의 순서가 알고리즘을 거친 뒤에도 유지되는 안정 정렬 알고리즘에 속한다. 이것은 간단하게 말해 $(1, 3_{2}, 2, 3_{1}, 5)$ 가 있다면 $(1, 2, 3_{2}, 3_{1}, 5)$ 와 같이 $3_{2}$, $3_{1}$ 의 순서가 유지되는 것을 말한다. 1차원 배열이라면 이것은 아무짝에도 쓸모 없지만, 어떤 대표값으로 소팅해야할 데이터 테이블이 있다면 이러한 안정성이 필요하다. $3_{2}$, $3_{1}$ 자체의 순서는 어떻게 되든 상관 없지만, 이들이 물고 있는 데이터는 어떤 의미 있는 순서로 나열되어있을 수 있기 때문이다.

[6] 퀵 정렬

퀵 정렬은 이름 그대로 빠른 것이 가장 큰 장점이다. 이론적으로는 $O( n^2)$ 이라서 힙정렬이나 합병 정렬보다 열등하며 $\Theta ( n \log n )$ 역시 장점으로 내세울 게 못 되어 보이지만, 실제로 사용할 때 있어서는 거의 대부분의 경우에 우수한 퍼포먼스를 보인다. 앞서 언급한 ‘대체로 가장 우수한 알고리즘’이란 바로 이 퀵 정렬을 말한다. 마찬가지로, 앞서 언급한 다른 정렬 알고리즘들의 특징을 이해했다면 퀵 정렬을 주로 사용하면서도 현명하게 다른 알고리즘을 골라 쓸 수 있을 것이다.