Sorting Algorithm을 비판적으로 바라보자.

Sorting Algorithm을 비판적으로 바라보자.

#1. 첫번째 의문

quick sort가 가장 좋고 빠르다며, 그래서 이름도 quick sort라며!

그런데 heap sort, merge sort는 왜 존재하며 왜 필요하지?

어디에 쓰이고 있길래 살아남은 거지?

세 sorting algorithm(Quick sort, Merge sort, Heap sort)의 expected-Time Complexity는 O(n log n)으로 모두 동일하다. 하지만 Space Complexity는 merge sort만 Sorting하고자 하는 데이터의 크기 만큼이다. 그러면 일단 heap sort는 그렇다치고,

어떻게 Merge Sort가 살아남았을까?

한정된 메모리 상황에서 ‘빅 데이터'를 Sorting 해야하는 경우를 가정하자. 기존의 Sorting 알고리즘으로는 한 번에 Sorting 할 수 없을 정도의 '빅 데이터'말이다. 한 번에 Sorting 할 수 없다는 것은 디스크에서 읽어오는데 데이터 전부를 메모리에 올리지 못하는 경우를 말한다.

그래서 이 큰 문제를 작은 문제로 나누어(Divide) Sorting하기로 하였다. 작은 문제로 나누어진 데이터를 quick sort로 정렬을 한 뒤(Conquer) 각각 정렬된 데이터들을 다시 합쳐야 한다.(Combine) 하지만 그냥 combine 한다면 작은 문제로 나누어 Sorting 한 의미가 없어진다. 이 경우에 merge sort 를 사용하여 combine 하는 것이다.

이번엔 heap sort를 보자.

이번엔 둘다 In-place sorting algorithm으로 space complexity도 동일하다.

왜 heap sort가 사용되었는지 먼저 생각해보자.

Min-heap 으로 만들면 최소값을 O(1)만에 추출할 수 있다 하고 Max-heap으로 만들면 최대값을 O(1)만에 추출할 수 있다고 했다.  그래? Time complexity도 같겠다, quick sort로 오름차순 정렬한 다음에 index 0번째의 값을 꺼내오면 최소값이지 않아? 마찬가지로 내림차순 정렬한 다음에 0번째 값을 꺼내오면 최대값이지 않아?

...듣고 보니 맞는 말 같다.

하지만 heap sort의 강력함은 하나의 값이 추출되고, 새로운 값이 추가될 때 나타난다. 계속해서 최소값(or 최대값)을 추출하고, 새로운 값(이 값은 random)을 추가하려고 할 때, quick sort algorithm으로 정렬해서 원하는 값을 추출한다고 하면, 매번 모든 데이터를 대상으로 sorting을 진행해야 한다.

하지만 heap sort의 경우에는 새로 들어온 값에 대해서만 heapify를 통해 저장될 위치를 정해주면 된다. 즉, quick sort algorithm을 사용할 경우, 매번 O(n log n)의 Time complexity를 소요하지만 heap sort의 경우 O(log n)의 Time complexity를 소요하는 것이다.

각자 살아남은 이유가 있었다.

#2. quick sort는 항상 빠르고 좋은 것인가?

정렬하고자 하는 데이터의 크기가 작을 때, 즉 n 이 작을 때를 가정해보자.

계속해서 재귀적으로 partition 함수를 호출하는 quick sort로만 정렬을 한다면 n이 작을 때 function call하는 비용이 더 많이 들 것이다. 즉, n이 작을 때 quick sort algorithm을 사용하는 것은 배보다 배꼽이 더 큰 격이 되는 것이다. n이 작아진 경우에는 다른 sorting algorithm을 통해 sorting하면 더 효율적이지 않을까 하는 생각이 든다. function call 없이 정렬할 수 있는 algorithm을 생각해보자. O(n^2)인 Sorting algorithm인 Insertion Sorting algorithm이 있다. n 값이 작을 때, n log n 과 n^2차이는 미미하다.

실제로 Java에서 quick sort의 구현이 이렇게 되어있다고 한다. n 의 값이 작을 때는 Insertion Sort 로 Sorting을 한다. 그렇다면 n의 값을 설정하는 것이 중요하게 보인다. 이는 실험적으로 측정할 수 있으며, JDK에는 실험적으로 가장 높은 성능을 보이는 n 의 값으로 설정되어 있다고 한다.

임시 end