어떤 정렬 알고리즘을 사용할 것인가?

어떤 정렬 알고리즘을 사용할 것인가?

 

 

컴퓨터 과학에는 숫자 혹은 문자를 오름차순, 혹은 내림차순으로 정렬하는 알고리즘이 필요한 경우가 종종 발생하며, 그 문제를 해결하기 위한 많은 정렬 알고리즘이 있다.

 

정렬 알고리즘은 일반적으로 시간복잡도가 작을수록 더 좋은 알고리즘이라고 할 수 있다.

 

 

---

Bubble Sort, Selection Sort, Insertion Sort의 경우 O(n^2)의 시간복잡도를 가지고,

 

Quick Sort, Merge Sort의 경우 O(nlgn)의 시간복잡도를 가지며,

 

Counting Sort, Radix Sort의 경우 O(n)과 O(dn)의 시간복잡도를 가진다. (d는 Radix Sort의 자릿수)

---

 

 

같은 정렬 알고리즘인 Counting Sort나 Radix Sort의 경우 O(n), O(dn)의 시간복잡도를 가지므로 대부분의 정렬에 가장 적합하다고 생각할 수 있으나 실제로는 이 알고리즘들을 모든 보편적인 상황에서 적용하기엔 비효율적인 경우가 많다.

실행 속도의 미미한 향상을 위해 엄청난 메모리 공간을 소모해야하거나, 심지어 실행 속도조차도 다른 정렬 알고리즘에 느린 경우가 발생한다.

 

이러한 알고리즘들은 정렬하고자 하는 각 element가 특정 조건을 충족시키는 상황에 강력하다.

 

다음은 O(n)의 시간복잡도를 가지는 Counting Sort, Radix Sort의 효율적인 적용을 위해 요구되는 element의 두 가지 제약사항이다.

 

 

---

1) Counting Sort에서 정렬하고자 하는 element 값의 범위(가장 큰 element와 가장 작은 element의 차이)가 작아야 한다.

 

2) Radix Sort에서 정렬하고자 하는 element값의 자릿수가 작아야한다.

부동소수점 표기형을 사용하는 자료형(float, double)을 사용하는 element를 정렬하는 경우에 특히 비효율적이다.

---

 

 

이 두 가지 제약조건을 충족시키지 못할 경우, 심각한 메모리 관련 문제가 발생한다.

 

Counting Sort는 (정렬하고자 하는 element 값의 범위 * element의 자료형이 사용하는 메모리 공간)만큼 메모리를 할당받아야 한다.

 

예를 들어, -40,000,000 ~ 600,000,000 까지의 범위를 가지고, 중복된 수가 최대 2^16-1개인 수를 정렬하기 위해선 640,000,000 * (sizeof(unsigned short)) = 1,280,000,000B = 1.28GB의 메모리가 필요한 것이다. (unsigned short는 2B의 메모리 공간을 사용한다.)

 

Radix Sort 또한 Queue를 활용해 정렬하는 방법을 사용할 경우 Queue가 LinkedList의 형태로 element를 저장할 것을 고려한다면, (LinkedList의 element크기 * n) 만큼의 메모리 공간이 확보되어야 한다.

Java의 경우 LinkedList의 각 element는 24B의 메모리를 사용하므로 매우 치명적이다.

 

또한 높은 자릿수부터 Queue에 넣었다가 빼는 작업을 d번 반복해야 하므로 오히려 O(nlgn)의 시간복잡도를 가지는 다른 정렬 알고리즘에 비해 더 느린 경우도 발생할 수 있다.

 

---

 

따라서 결론적으로 Counting Sort와 Radix Sort는 특수한 경우에만 효율적인 제한적인 알고리즘이라고 할 수 있다.

 

그럼 메모리 관련 이슈가 없고 O(nlgn)의 시간복잡도를 가지는 Quick Sort와 Merge Sort과 비교해 O(n^2)의 시간복잡도를 가지는 다른 정렬알고리즘은 어떤 용도로 사용되는 것일까?

시간복잡도도 더 크며, 메모리도 비슷하게 사용하니 O(n^2) 정렬 알고리즘이 마치 O(nlgn) 정렬 알고리즘의 하위호환같은 느낌이다.

 

---

 

하지만 그렇지 않다.

 

n이 매우 작은(대략 n < 10) element의 정렬에서는 O(nlgn) 정렬 알고리즘보다 O(n^2) 정렬 알고리즘이 더 빠른 경우가 많다.

 

Quick Sort와 Merge Sort는 기본적으로 DnC(Divide & Conquer) 기법을 사용하는데, element들을 divide하는 과정에서 나누어진 부분의 크기가 10보다 작아진 경우 그 부분 element들에 대해 계속적으로 DnC 기법을 사용하는 것보다 그 부분 element들에 대해서 O(n^2) 정렬 알고리즘을 사용하는 경우가 더 빠르다.

 

10보다 작은 부분을 굳이 쪼개서 다시 합치는 것보다 그 부분에 대해서만 Insertion Sort와 같은 O(n^2) 정렬 알고리즘을 사용하는 것이 속도 측면에서 더 빠른 것이다. (O(n^2) 정렬 알고리즘 중에서는 Insertion Sort가 일반적으로 가장 효율적이다.)

 

단순히 10보다 작은 부분에 대한 정렬 방식을 바꾸는 것이라 별 의미 없는 내용이라고 생각할 수 있지만, DnC 과정에서 가장 많이 하는 연산은 divide한 이후 그 잘게 잘라진 부분을 정렬하는 과정이다. 그런 이유에서 이 과정이 결과적으로 유의미한 속도향상을 불러올 수 있는 것이다.

 

 

 

---

 

우리에게 익숙하게 알려져있는 정렬 알고리즘은 시간복잡도에 관계없이 많이 익혀놓을수록 각각의 상황에 적합한 정렬을 수행할 수 있다.

그러기 위해선 각각의 정렬 알고리즘이 가지고 있는 장단점을 속도와 메모리 관점에서 분석, 비교할 줄 아는 능력을 갖춰야 한다.