728x90

분할정복

           > 1. 주어진 문제의 입력을 나눌수 없을 때까지 두개이상 작은 문제로 순환적으로 분할

              2. 작은 문제들을 각각 해결

              3. 그해를 결합하여 원래 문제의 해를 구하는 방식

분할 > 정복  > 결합

이진탐색 : n개 -> n/2 + (n/2) 분할 -> (n/4) + n/4 + (n/4 + n/4) 분할한 것의 일부만 사용

합병정렬 : n개 -> n/2 + n/2 분할 -> n/4 + n/4 + n/4 + n/4

퀵정렬 :   n개 -> a + b 분할 ->c+d+e+f

선택문제: n개 ->  a + (b) 분할 ->(c)+d+(e+f) 분할한 것의 일부만 사용


퀵정렬

> 특정원소 기준으로 주어진 배열을 두 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식

> 특정원소 : 피벗 pivot : 두 부분배열로 분할할떄 기준이 되는 특정원소, 보통 주어진 배열 첫번째 원소 지정

                                  피벗이 제자리를 잡도록 하여 정렬하는 방식

A[] = {30, 45, 20, 15, 40, 25, 35, 10}

30: 피벗.    분할 후 {25, 10, 20, 15, 30 , 45, 35, 45}

분할 : 피벗을 기준으로 주어진 배열을 두 부분배열로 분할

정복 : 두 부분배열에 대해서 퀵 정렬을 순환저그로 적용하여 각 부분 배열을 정렬

결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

-순환형태-

QuickSort(A[] , n)
{
    if(n>1){
        pivot = Partition(A[0..n-1], n);//두 부분배열로 분할
        QuickSort(A[0..pivot-1],pivot);// 왼쪽 부분배열에 대한 순환 호출
        QuickSort(A[pivot+1..n-1],n-pivot-1);//오른쪽 부분배열에 대한 순환 호출
    }
}

-분할함수 Partition-

int Partition(A[] ,n)
{

    Left = 1; Right = n-1;

    while (Left <Right){ //피벗A[0]
       //피벗보다 큰 값의 위치를 찾음
       while(Left <n && A[Left] < A[0]) Left++;
       //피벗보다 작은 값의 위치를 찾음
       while(Right >0 && A[Right] >= A[0]) Right++;
       
       if(Left< Right)교환(A[Left]<=>A[Right])
       else 교환(A[0] <=>A[Right]) //피벗과 right 교환

   }
    return Right;
}

몇번 비교?

Θ(n):  n번비교 : 데이터 갯수에 비교. 

성능

T(n) : 입력 크기 n에 대한 탐색 가정에서의 모든 비교횟수의 합. 

     = 맨 바깥 수준에서의 비교횟수 + 순환 호출에서의 비교횟수. 

-퀵 정렬 수행시간-

한번의 분할 Partition()

+ 두번의 Quick Sort()순환호출

T(n)=T(왼)+T(오) +Θ(n) (n>1)

T(1)=Θ(1) 

- 최악의 경우

오름차순 내림차순

10 20 30 40 50  //pivot 10

10 20 30 40 50  

10 20 30 40 50  

10 20 30 40 50  

10 20 30 40 50  

10 20 30 40 50 

50 40 30 20 10 //pivot 50

10 40 30 20 50

10 40 30 20 50

10 20 30 40 50

10 20 30 40 50

10 20 30 40 50    //n번


피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열로 분할 되는 경우

> 극심한 불균형적 분할 = 피벗이 최소값 or최대값일 떄.

                               = 입력데이터 정렬되어 있고, 피벗이 배열 처음 원소로 지정할떄. 

T(n) =T(n-1) +T(0) + Θ(1)  (n>0) T(0)=0

T(n) = T(n-1)+Θ(n)

T(n)=T(n-1) +Θ(1)

T(n) = O(n^2) 

- 최선의 경우

피벗을 중심으로 항상 동일한 크기의 두 부분 배열로 분할 되는 경우. =피벗이 중간값

T(n)=T(n/2) +T(n/2) + Θ(n)  (n>1)

T(1)=1

T(n) = 2T(n/2) +Θ(n)

T(n) = O(nlogn)

- 부분배열의 모든 분할 비율에 따른 수행 시간의 평균

T(1) =T(0)=0

T(n)=O(nlogn)

>피벗 선택의 임의성만 보장되면 평균적인 성능을 보일 가능성이 매우 높음.

> 배열에서 임의로 값을 선택해서 배열의 처음 원소와 서로 교환한 후 정렬 수행. 

   >> 가운데 임의의 데이터를 처음으로 놓고 실행 >> 최악의 경우 발생 안함.  

 

 

 

 

 

 

 

'Made by Miseong > 2019 알고리즘' 카테고리의 다른 글

1. 분할정복 - 이진탐색  (0) 2019.08.04
2019알고리즘  (0) 2019.08.04

+ Recent posts