- Merge Sort
정렬할 배열을 재귀적으로 정확히 반으로 나누면서 정렬과 병합을 반복하는 형식으로 정렬하는 방법
pseudo code
mergeSort(A[], p, r) { // A[] : 정렬할 원 배열, p: 현재 함수에서 가리키는 배열의 처음 위치, r: 배열의 마지막 위치
if(p<r) { // p가 r보다 작을 경우. 즉, 더 이상 나눌 수 없을 때 까지 분할을 실행
q = (p+r) / 2; // 배열의 위치 p와 r을 이용해서 중간 값 q를 구함
mergeSort(A, p, q); // 반으로 나눈 왼쪽 재귀적 실행
mergeSort(A, q+1, r); // 반으로 나눈 오른쪽 재귀적 실행
merge(A, p, q, r); // 왼쪽과 오른쪽을 병합
}
}
동작 예)
- Quick Sort
정렬할 배열을 재귀적으로 나누되, 기준점(pivot)을 설정하여 더 큰 값과 작은 값으로 나눠서 정렬하는 방법
pseudo code
quickSort(A[], p, r) { // A[] : 정렬할 원 배열, p: 현재 함수에서 가리키는 배열의 처음 위치, r: 배열의 마지막 위치
if(p<r) { // p가 r보다 작을 경우. 즉, 더 이상 나눌 수 없을 때 까지 분할을 실행
q = partition(A, p, r); // pivot을 기준으로 왼쪽과 오른쪽 부분배열로 분할
quickSort(A, p, q-1); // pivot의 왼쪽 부분배열 재귀적 실행
quickSort(A. q+1, r); // pivot의 오른쪽 부분배열 재귀적 실행
}
}
동작 예)
기준점(pivot)은 어떤 값으로 해도 상관 없으나, 현재는 각 분할의 가장 오른쪽 값으로 설정했을 경우
i : 기준점보다 작은 값들의 마지막 배열 위치
j : 현재 확인중인 배열 위치
x : 기준점
1. 배열의 처음부터 j번째의 값과 기준점의 값 x를 비교하여 A[j]가 같거나 크면 pass, 적으면 A[i+1] 값과 A[j] 값을 치환한 다음 i를 1 더해줌
(i 앞의 값들은 모두 기준값보다 작고 뒤의 값들은 모두 크도록 만듬)
2. 배열의 값을 전부 확인한 경우에 A[i+1] 값과 A[x] 값을 치환
(기준값을 기준값보다 작은 부분배열과 기준값보다 큰 부분배열의 사이에 위치시킴)
Merge Sort 보다 Quick Sort가 빠른 이유
- 병합 과정에서 유리함
Merge Sort는 병합 과정의 왼쪽과 오른쪽 데이터를 합치는 동작에서 정렬을 한 번 더 진행해야 한다.
또한, 해당 정렬을 진행하는 과정에서 임시 배열을 하나 생성해야 함.
하지만 Quick Sort의 경우에는 원 배열을 부분배열로 분할하기는 하지만 병합이라는 과정이 없기 때문에
임시 배열을 만들거나 병합 시에 데이터를 재 정렬할 필요가 없음.