[자료구조 및 프로그래밍] 16. O(N log N)정렬 방법 별 비교 횟수, 쓰기 횟수 비교

방식의 비교횟수와 쓰기 횟수를 비교해보고자 한다.

병합 정렬

 

merge_sort() 함수의 호출시, 기존 배열을 복사해서 넣어놓고, 카운팅할 비교횟수와 데이터 쓰기 횟수를 초기화한다.

mergeSort() 라는 재귀용 함수를 호출한다.

 

받은 배열을 반씩 나눠서 재귀적으로 mergeSort 를 호출하며, mergeSort 로 반씩 정렬된 결과를 다시 합쳐서 정렬할 merge 함수도 호출한다.

 

실질적인 정렬이 수행되는 merge 함수다.

먼저 반씩 정렬된 배열을 다른 배열에 복사해서 옮겨둔다.

merge sort 를 배열롤 구현할 때 반드시 수행해야 하는 작업이기에, 이는 데이터 쓰기 횟수에 포함시켜서 카운팅했다.

 

그리고 기존 입력된 배열을 복사한 배열을 반씩 나눠 탐색하면서 작은값부터 채워나간다.

이 과정에서 키값을 비교하므로 카운팅을 해주고, 데이터를 쓰면서도 카운팅을 해준다.

 

반씩 나눠진 두 배열중 하나를 다 탐색했다면 아직 탐색하지 않은 나머지 배열은 그냥 그 순서대로 쭉 넣어주면 된다.

이때는 키 값비교는 하지 않으니 비교횟수 카운팅은 하지 않고, 데이터 쓰기 카운팅만 해주었다.

 

이 프로그램의 실행결과 아래와 같이 비교 횟수와 데이터 쓰기 횟수 카운팅 결과를 출력하였다.

 

데이터 종류에 상관없이 데이터를 쓰는 횟수는 크기에 따라 언제나 고정적이었다.

어쨌든 반씩 정렬된 데이터를 복사하여 넣고, 결국 모든 데이터를 순회하며 쓰는 것은 데이터가 최적으로 들어오든, 최악으로 들어오든 똑같기 때문이다.

 

이미 정렬된 데이터가 입력으로 주어지는 경우 실행결과는 아래와 같다.

 

키값 비교횟수가 감소하였으나, 데이터 쓰기 횟수는 바뀌지 않았다.

 

역순으로 정렬된 데이터가 입력으로 주어지는 경우는 아래와 같았다.

 

오히려 비교횟수가 더 감소하였다.

 

일단 개인적으로 merge sort 의 중요한 점이라고 생각되는 부분은, 데이터 쓰기 횟수가 항상 고정적으로 2NlogN 만큼 소요된다는 점이다.

한 level 에서 배열 복사에 N 번, 복사한 배열을 토대로 정렬된 배열을 만드는데 N 번 총 2N 번의 쓰기가 일어나며,

이 level 은 log N 번 반복된다.

 

N=100 으로 검증해보면 log100 = 6.xxx 이므로 200* log 100 = 대충 1200보다 크고 1400보다 작은 값이 나올 것이 예상되며, 실제로도 그렇게 나왔다.

 

비교횟수의 경우, 정렬한 한쪽 그룹의 최댓값이, 정렬한 다른쪽 그룹의 최솟값보다 작은 경우, N/2 번의 비교만으로 정렬할 수 있으며, 이를 log N 번 반복하므로 N/2 log N 번의 비교를 수행한다.

 

N = 100 으로 검증해보면, 50 log 100 = 50 * 6.xx = 300 ~ 350 사이의 값이 나오는 것을 알 수 있으며, 실제로도 그렇게 나왔다.

 

역순 정렬된 경우가 비교횟수가 더 작았던 이유는 b[i] < b[j] 로 비교하기 때문인데,

홀수개를 반으로 나눠서 새로운 졍렬 배열을 만드는 상황을 생각해보자.

역순 정렬이라면 6 7 8 9 / 1 2 3 4 5 를 합쳐서 새로운 정렬 배열을 만들 때, 6 7 8 9 를 새로운 배열에 넣고나서 반복문을 빠져나간다.

앞의 4개의 값이 모두 b[i] < b[j] 를 만족하지 않으므로, i는 변하지 않고 j 값만 변하기 때문에 4번의 비교가 일어난다.

 

이미 정렬된 배열이 들어오는 경우는 1 2 3 4 5 / 6 7 8 9 를 합쳐서 새로운 정렬 배열을 만들 때, 1 2 3 4 5 를 새로운 배열에 넣고 나서 반복문을 빠져나간다.

앞의 5개의 값이 모두 b[i] < b[j] 를 만족하므로, j 는 변하지 않고 i 만 변하기 때문에 5번의 비교가 일어난다.

 

따라서 merge sort 는 최악의 경우에도, 최선의 경우에도 n log n 의 시간복잡도를 갖는다고 알려져있다.

 

< 병합정렬 >

in-place : X

비교 횟수 (최대) : N log N

비교 횟수 (최소) : N/2 log N

쓰기 횟수 (최대) : 2N log N

쓰기 횟수 (최소) : 2N log N

 

---

퀵 소트

구현은 아래와 같다.

 

비교 횟수는 역순이거나 정순일 때, 반씩 가르지 못하고, 양끝단 하나만 잡고 가르다보니 오래 걸린다.

이런 최악의 경우에는 partition 수행하는데 O(N) 이 걸리는데, 이걸 N 번 반복하니까 O(N²) 이 걸린다.

최적의 경우에는 N 번 비교를 log N 번 반복한다. (N번 비교를 하는 건 고정이다.)

 

단 쓰기 횟수는 어떤 키값을 기준으로 좌우가 나눠지는 순간 딱 swap 을 수행하니까 어떤 중간값이기만 하면 swap을 실행한다.

 

swap은 최적의 경우 분할된 부분에 대해서만 swap 을 진행하므로, 2(N-1) 일 때 최적이고,

최악의 경우 O(N²) ?

평균적으로는 O(N) 인듯?

 

partition 에서 단 1번만 swap 할 수도 있고,

N/2 번 스왑할 수도 있다.

N/2 번 스왑을 N번 반복하면 최악은 N²/2 인데, 이건 말이 안되고,

보통 O(n)에 수행..?

무작위 데이터

이미 정렬된 데이터

역순 정렬 데이터

 

< 퀵소트 >

in-place : O

비교 횟수 (최대) : N²

비교 횟수 (최소) : N log N

쓰기 횟수 (최대) : N²

쓰기 횟수 (최소) : N

 

비록 쓰기 횟수에 대한 시간복잡도는 이해를 못하였으나, 머지소트랑 다르게, 쓰기 작업이 최악으로 일어나더라도 Partiion 한번에 N/2 이내로 일어남은 확실하다.

merge sort 에서는 2N 번이 확정적으로 일어났는데 말이다.

 

따라서 쓰기 횟수가 압도적으로 적어서 merge sort 보다 평균적인 정렬 소요 시간이 적게 걸린다.