[출처 : http://blog.naver.com/holywater86/50098587938]
4. 병합정렬
1) 방법
(1) 입력을 n/2 으로 나눈다
(2) 전반부 / 후반부 정렬 (재귀)
(3) 두 부분 병합
2) 수행시간 : O(nlogn)
3)
Merge_Sort(A,p,r)
{
if(p<r)
{
q <- (p+r)/2 내림;
Merge_Sort(A,p,q) //전반부 정렬
Merge_Sort(A,q+1,r) //후반부 정렬
Merge(A,p,q,r) //병합
}
}
Merge(A[], p, q, r)
{
//비교 후 temp에 쓰기
i ←p; j ← q+1; t ← 1;
while(i ≤ q and j ≤ r)
{
If(A[i] ≤ A[j])
tmp[t++] ← A[i++];
else tmp[t++] ← A[ j++];
}
//나머지 쓰기
while(i ≤ q)
tmp[t++] ← A[i++];
while( j ≤ r)
tmp[t++] ← A[ j++];
//temp에서 옮기기
i ← p; t ← 1;
while( j ≤ r)
A[i++] ← tmp[t++];
}
5. 퀵정렬
1) 방법
(1)기준원소를 중심으로 작은값/큰값 두 부분으로 나눔
(2)전반부/ 후반부 정렬 (재귀)
2) 수행시간: 최선,평균 O(nlogn), 최악 O(n^2)
3) 특징 :
원 배열을 두부분으로 나누는 것은 병합정렬과 같으나 방법이 다르며
가장 큰 차이점은 퀵소트는 마지막에 병합하는 과정이 없다
평균적으로 가장 빠르며 가장 많이 사용하는 정렬이다.
4)
QuickSort(A[], p, r)
{
if(p < r)
{
q ← Partiton(A, p, r);
QuickSort(A, p, q-1); // 전반부 정렬
QuickSort(A, q+1, r); // 후반부 정렬
}
}
Partition(A[], p, r)
{
x ← A[r]; //기준원소
i ← p-1; //파티션 플래그
for j ← p to r-1
if(A[ j] ≤ x)
A[++i] ↔ A[ j];
A[i+1] ↔ A[r]; //기준원소 삽입
return i+1;
}