[알고리즘] 3-2. 분할 정복을 이용한 정렬

분할 정복법

-> 작은 크기의 동일 문제로 분할 후 순환적으로 해결

-> 작은 문제의 해를 합쳐 원래 문제의 해를 구한다.

 

 

합병정렬

1. 데이터가 저장된 배열을 절반으로 나눈다

2. 각각을 순환적으로 정렬

3. 정렬된 두 개의 배열을 합쳐서 전체를 정렬

 

mergeSort(A[], p, r)
{
 if (p<r) then {
  q <- (p+q)/2;
  //p,q의 중간 지점 계산
  
  mergeSort(A, p, q);
  //전반부 정렬
  
  mergeSort(A, q+1, r);
  //후반부 정렬
  
  merge(A, p, q, r);
  //합병

merge(A[], p, q, r)
{
 정렬되어 있는 배열을 합쳐서 [p~q와 q+1~r]
 정렬된 배열 만든다. [p~r]
}

 

 

퀵 정렬

1. 배열을 elements in lower parts <= elements in upper parts로 나눈다

2. 각 부분을 순환적으로 정렬

3. 끝

 

1. 정렬할 배열의 마지막 수를 기준으로 삼는다.

2. 기준보다 작은 수는 기준 왼쪽에 나머지는 기준 오른쪽에 오도록 재배치 (분할)

3. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬

 

 

quickSort(A[], p, r)
{
 if (p<r) then {
  q = partition(A,p,r);
  //분할
  
  quickSort (A,p,q-1);
  //왼쪽 부분배열 정렬
  
  quickSort (A,q+1,r);
  //오른쪽 부분배열 정렬
 }
}

partition(A[], p, r)
{
 배열 A[p..r]의 원소를 A[r] 기준으로 양쪽으로 재배치
 A[r]의 위치를 반환
}

 

//partition

//p~r까지의 배열
//pivot보다 작은 값들 [p부터 i]
//큰 값들

//검사하려는 값 : j
//r번째 값 : x

if A[j]>=x
 j<-j+1;
else
 i<-i+1;
 exchange A[i] and A[j];
 j<-j+1;

 

Partition (A, p, r)
{
 x <- A[r];
 i <- p-1;
 for j <- p to r-1
  if A[j] <= x then
  i <- i+1;
  exchange A[i] and A[j];
 exchange A[i+1] and A[r];
 return i+1;
}

 

분할에 따라 복잡도 결정

최선의 경우 : 절반으로 분할되는 경우

최악의 경우 : 한쪽이 0으로 분할되거나 이미 정렬되어 있었을 경우

 

 

피봇 선택 경우의 수

1. 첫번째 값이나 마지막 값을 피봇으로 선택

2. Median of Three : 첫번째 값, 마지막 값과 가운데 값 중에서 중간값을 피봇으로 선택

3. Randomized Quicksort : 피봇의 랜덤 선택 [O(NlogN)의 시간복잡도를 갖는다.]