[0927] Merge Sort & Quick Sort와 시간 복잡도

주어진 파일을 읽어와서 그 값으로 배열을 만들고, 만들어진 정렬이 되지 않은 배열을 머지소트와 퀵소트를 이용하여 결과값을 얻어내였다. 각각의 소트 별로 결과를 파일 출력으로 정렬된 배열의 정보를 파일로 만들었고, 걸린 시간은 nanoSecond메소드로 start와 end 시간을 각각 측정하여 걸린 시간을 알아내었다. 원래 과제 사항에서는 milleSecond 단위로 출력하라고 했으나, 이것을 이용하여 시간을 측정했을 때에는 유의미한 숫자를 구하기 어려웠으므로 nano 세컨드를 이용하여 시간을 출력하고 초 단위로 바꾸어 출력하였다. 이와 같이 단위를 바꾸게 된 점을 명시한다.

 

우선 초기의 데이터 셋은 위와 같다. 이것을 파일 입출력을 진행하여 하나의 배열에 다 담았다. 담은 배열의 이름은 array로 변수명을 선언해주었다. 이것으로 머지소트와 퀵소트를 각각 실행했다. 우선 머지소트부터 본다.

 

[Merge Sort]

머지소트는 간단히 말해서, 각각의 배열을 하나가 될때까지 쪼갠다음 그것들을 정렬하면서 다시 이어붙이는 소트이다. 간결하게 동작만을 설명하면 위와 같고, 이것은 크게 세 가지 동작으로 나뉘게 된다.

 

1. 분할

2. 정렬

3. 병합

 

첫번째, 분할의 단계에서는 Main함수를 보면 mid라는 변수에 처음 인덱스와 끝 인덱스를 더한 값을 r로 나누는 모습을 볼 수 있다. 이것은 배열의 중간 지점을 구하려는 것이며, 조건에 충족할 때까지 (끝 인덱스가 처음 인덱스 값보다 작을 때까지) 반복하면 각각의 범위들은 원소 하나를 지칭하게 된다. 이러한 나눠지는 과정을 두개의 재귀 문장으로 실행하게 되는데, 이것은 n개의 데이터를 2/n개로 나누고 4/n..을 반복하는 작업을 하게 된다. 이 부분이 재귀함수 Merge_Sort(A, p, mid)와 Merge_Sort(A, mid+1, r)이뤄진다. 이 부분을 다 수행하였으면 분할한 것들을 병합하여야 한다. 

 

두번째, 정렬 단계에서는 앞서 분할 단계에서 분할되었던 원소들을 붙이는데, 정렬해서 붙이게 된다. 인자로 첫 인덱스, 가운데 인덱스, 마지막 인덱스와 배열의 정보가 들어가게 되며 함수가 시작된다. Merge(A, p, mid, r)함수에서 일어나는 동작이 아래와 같이 시행된다.

그림으로 예시인 배열로 분할 이후부터의 동작을 표현하였다. 첫 라운드를 돌 때 위와 같이 동작하게 된다.

i와 j를 지정해 준 뒤 그 둘을 비교한다. 둘을 비교하는 이유는 하나씩 나눠진 상태이기 때문에 범위 안에서 동작하기 때문에 위와 같이 동작하게 된다. 그래서 array 배열의 i 인덱스 값과 j 인덱스에 있는 값을 비교하였을 때 j 인덱스에 있는 값이 i 인덱스에 있는 값보다 크다면 array[i]의 값을 newArray에 재배치하며 정렬을 하면서 넣어준다. 하지만 위의 케이스와 같은 경우 i의 인덱스이 있는 값이 더 크므로 더 작은 숫자 2가 3뒤에 배치되어야 한다. 그렇기 때문에 j 인덱스에 있는 값이 제일 첫번째 k=0일때 인덱스의 값으로 들어간다. 넣은 뒤에는 k++을 하여 다음 인덱스로 넘겨 위와 같은 비교 정렬을 반복한다. 그러나 정렬이 되지 않은 부분이 남아있을 수 있다. 모든 정렬 데이터가 짝수일 수는 없는 경우를 대비하여 while 문으로 나머지 숫자들을 처리해준다. 그리고 마지막으로 정렬된 newArray를 다시 원래 array로 복사를 해주며 동작을 끝낸다. 동작을 끝낸 결과는 다음과 같다.

 

위의 결과처럼 정렬이 잘 되어있는 모습을 확인하였다. 또한 시간은 초 단위로 0.00028초가 걸렸다. 시간과 시간 복잡도에 대해서는 Quick Sort 까지 분석을 하고 종합적으로 두 개를 같이 분석하겠다. 

 

[Quick Sort]

Quick Sort는 pivot을 하나 정해서, 그것과 비교를 하며 작은 값, 큰 값을 찾아서 정렬을 해나가는 정렬이다.

본인이 구현한 경우는 pivot이 제일 왼쪽에 있는 [0] 인덱스의 값을 피벗으로 지정하였다. 그리고 피벗보다 큰 수를 찾아서 담는 변수 b를 pivot+1의 인덱스에 지정해놓았고, 피벗보다 작은 수를 찾아서 담는 변수 배열의 마지막 인덱스에 지정해놓았다. 이것이 각각의 조건에 만족할때까지 while문을 돌면서 b는 피벗보다 큰 수를 찾아서 담을 것이고, s는 피벗보다 작은 변수를 찾아서 담을 것이다.

정확히 말하면, 큰 수와 작은 수를 찾으면 그 수들이 있는 위치를 담은 변수가 될 것이다. 그럼 이 변수중에서 b의 인덱스가 s보다 커지면 둘이 방향이 엇갈린 격이 되므로 이때는 s의 인덱스에 있는 수와 pivot 인덱스에 있는 수를 swap 한다. (위치를 바꾼다) 그러나, 엇갈리지 않은 경우 else 문이 실행되어 그냥 b와 s의 위치가 바뀌게 된다. merge sort와 비슷한 재귀 용법으로, 이렇게 해서 범위를 분할하고 숫자들을 정렬한다. 정렬한 결과는 아래의 사진과 같았다.

 

 

 

위와 같은 정렬 결과를 확인했으므로 정렬 동작이 잘 작동되는 것을 확인했다. 그럼 이제 각각의 소트에 대한 실행 시간을 확인하고 시간 복잡도를 계산해보자.

 

우선 머지소트를 5번 실행한 결과이다. 소트를 실행하기 전 3번을 먼저 돌리고 그 다음에 나온 5번으로 평균을 내었다.

Merge Sort를 돌렸을 때 0.00013초 정도의 평균 수행 시간을 구할 수 있었다. 다음은 QuickSort의 결과이다.

위의 결과와 같이 평균 수행시간은 0.0006초로 0.00013초인 MergeSort의 수행시간보다 더 빠른 것을 알 수 있다.

퀵소트가 머지소트보다 더 빠르게 동작을 수행할 것이라는 예상 결과를 증명할 수 있었다. 그렇다면 왜 이러한 결과가 나올까? 이유를 알기 위해서 머지소트와 퀵소트의 시간 복잡도를 구해보자.

 

[Marge Sort의 시간 복잡도]

제일 처음에 크기가 N인 배열을 반으로 쪼개서 분할을 한다. 하면 n/2 n/2의 동작을 하고, 그 다음에 나눠지는 범위는 n/4개 짜리가 4개가 나눠지고, 그 다음은 n/8짜리가 여덟개가 나오게 된다. 우리는 100개의 데이터 셋을 했기 때문에 범위가 7번 만에 나눠지는 것을 볼 수 있다. 이렇게 나눠진 배열은 합병 단게에 들어가게 되는데 여기서 부터가 알고리즘 시간 복잡도를 고려해야 할 구간이다.

 

합병단계를 들어가기 전에, 전의 분할 과정은 매번 밑이 2인 logN만큼을 반복해야 한다는 것을 볼 수 있다.

레코드 수가 n일때를 고려헀을 때, 2의 거듭제곱이 반복되는 모습을 볼 수 있다. 

예를 들어, 레코드 n개가 우리가 실험했던 100개라고 가정했을 경우, 나눠지는 범위는 다음과 같다.

 

n = 100 -> 2^6 + 36

n = 50 -> 2^5 + 18

n = 25 -> 2^4 + 9

n = 12 -> 2^3 + 4 ...

 

상수는 제외하고 바라본 시선에서, 보면 2의 거듭제곱만큼씩 나눠지는 것을 볼 수 있다. 

n이 2^k씩 감소하는 것을 보면, k는 즉 횟수가 되고 이것은 순환호출 비교 깊이가 된다. 그렇기 때문에 k=log2N이 되는 것이다. 

 

또 고려해야 할 것이 있다. 합병 단계에서의 비교 연산이다.

예를 들어 생각해보았다. 크기가 1인 부분배열을 합치려면 n=8개일 경우 최대 4번을 실행해야한다. 그렇다면 8번의 연산이 실행되어야 한다. 그리고 크기가 2인 부분배열을 합치려면 최대 2번의 비교 연산을 해야한다. 이와 같이 비교 연산의 횟수는 n인 것을 알 수 있다.

 

최종적으로, 위의 내용들을 고려하였을 때, 머지 소트는 순환호출 깊이 만큼의 합병 * 각 합병 단계의 비교연산으로 시간 복잡도를 구할 수 있으며 이와 같이 계산하였을 경우 nlog2n이 나오게 된다. 그러나 아직 시간 복잡도가 완성되지 않았다. 마지막 이동 횟수를 따지지 않았다. 정렬을 위해 임시 배열을 만들었기 때문에 이것을 옮기는 작업이 필요하다. 요소 개수가 n인 경우 다시 2n을 이동해야 하므로, 이것의 시간 복잡도는 2nlog2n이 된다. 그렇기 때문에 최종적으로 식은 nlog2n + 2nlog2n = 3nlogn이 되지만 빅오(O)를 사용하여 시간복잡도를 구하면 최고차항만이 살아남아 표현되게 되므로 최종적인 시간 복잡도는 O(nlog2n)이 머지소트의 최종 시간 복잡도가 된다. 이 머지 소트의 장점은 best case, worst case, average case 모두 다 시간 복잡도가 O(nlog2n)으로 동일하다는 점이다.

 

[Qucik Sort의 시간 복잡도]

나눠지며 정렬을 한다는 점에 서 머지 소트와 동작이 유사하게 보일 수 있다는 점때문에, 비슷한 원리로 순환 호출의 깊이를 따지면 k = log2n이라는 것을 알 수 있다. 각 순환 호출 단계의 비교 연산을 보면, pivot과 모든 원소를 거의 모두 한 번씩 비교해야 하기 때문에 평균 n번 정도의 비교가 이뤄 질 것이다.

 

최종적으로 이것 역시 순환호출의 깊이 * 각 순환호출 단계의 비교연산 = nlog2n이 나오게 된다. 

이동횟수는 비교 횟수보다 적으므로 무시할 수 있으며 이것은 어디까지나 최선의 경우 T(n) = O(nlog2n)이 된다.

 

그러나 이 소트의 문제는 최악의 경우이다. 최악의 경우는 리스트가 계속 불균형하게 나눠지는 경우이다. 

비교 횟수는 만약 최악의 경우에는 레코드 개수가 n이고, 이것을 거듭제곱이라고 가정했을 때(n=2^k) 순환 호출의 깊이는 n이 되게 된다. 또한, 순환 호출 단계에서 거의 모든 레코드와 비교하는 것은 변함이 없으므로 결국 평균 n번은 변하지 않는다. 이것으로 보았을 때 worst case의 시간 복잡도는 O(n^2)이 되는 것을 알 수 있다.

이러한 케이스만 아니라면 다른 정렬 알고리즘과 비교했을 때 가장 빠르다. 

 

이러한 시간 복잡도로 보아, 퀵 소트가 머지 소트보다 빠르게 실행되는 케이스로 정렬이 완료되었음을 볼 수 있었다.