210628 합병 정렬(merge sort) & 퀵 정렬(quick sort)

합병 정렬(merge sort) : 

 

안정적, 분할 정복 알고리즘(문제를 작은 문제로 분리하고 각각 해결하여 합쳐서 문제를 해결하는 방법) 중 하나

리스트의 길이 0 또는 1이면 정렬된 것으로 취급, 아닌 경우는 비슷한 크기로 잘라 두 개의 리스트로 만듬

각 부분 리스트 재귀적으로 합병 정렬을 통해 정렬함

두 부분 리스트 합병 반복함 

 

단:  만약 배열로 구성한다면 임시 배열 필요 , 제자리 정렬 아님

데이터의 크기가 큰 경우에는 이동 횟수가 많아 매우 비효율적

장 : 안정적인 정렬 방법, 데이터의 분포에 영향 덜 받음, 입력 데이터에 영향 덜 받음

레코드를 연결 리스트로 구성하면, 링크 인덱스만 바꾸면 되기에 데이터의 이동은 무시할 수 있을 정도로 작아짐, 제자리정렬로 구현 가능

큰 데이터 다를 때 연결 리스트 사용하면 합병 정렬은 다른 어떤 방법 보다 효율적

 

시간 복잡도

순환 호출의 깊이 (합병 단계의 수) : 레코드의 개수 n이 2의 k 승일 때 깊이는 k 즉, k = log2(n)

각 단계의 비교 연산은 배열의 갯수 * 배열의 크기 이기에 n 번 비교 연산 수행함

각 단계의 이동 연산은 할 경우에 요소의 개수 n * 2 (복사 & 이동) 

=> nlog2(n)+2nlog2(n)=3nlog2(n) => O(nlog2(n)), 오메가(nlog2(n))

 

합병 정렬

 

 

 

 

 

 

퀵 정렬(quick sort)

불안정적, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬

분할 정렬 정복 알고리즘 중 하나, 평균적으로 빠른 수행 속도, 퀵은 합병과 다르게 리스트를 비균등하게 분할

 

리스트 중 한 요소를 피벗(pivot)으로 지정 

피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다. 

피벗보다 작은 요소들 과 큰 요소들이 각각 부분 리스트가 되어 이 두 부분 리스트를 순환 호출로 퀵 정렬을 다시함

부분 리스트들이 분할이 불가능할 때(크기 0 or 1)까지 반복함

 

장 : 속도가 빠름, 같은 시간 복잡도를 가지는 정렬 중에서도 가장 빠름

추가 메모리 공간 필요 X , O(log n)만큼의 메모리 필요

단 : 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다

피벗을 잘 정하는게 중요

 

시간복잡도

Best :

순환 호출의 깊이 = log2(n) 

비교 횟수 : n번  => n * log2(n)

이동 횟수 : 비교 횟수보다 작아 무시 가능

오메가(nlog2(n))

 

Worst(리스트가 계속 불균형+ 이미 정렬된 리스트에 정렬 실행하는 경우) : 

순환 호출의 깊이 = 레코드 개수가 2의 k 인 경우 => 깊이는 n

비교 횟수 : n번

이동 횟수 : 무시가능

O(n^2)

 

퀵 정렬