03-divide and conquer -Quick sort

Divide and conquer 하는법

 

1. 어떤 문제를 작게 쪼개야 할 때.

 

2. 충분히 작지 않으면 충분히 작아질때까지 쪼개기.

 

3. 필요하다면 합쳐서 필요한 답 찾기

 

*Divide and conqure 쓰면 안될 때
-버블정렬이 더 빠를 때
-나누었더니 나누어진 사이즈가 원래 사이즈와 거의 같을 때.
-나누었더니 그 문제의 크기만큼 작은 문제들로 나누어질때.(ex. 펙토리얼)

---

새 기술 : 퀵소트 Quick sort

아무배열이 들어오면 그중 아무 숫자나 하나 잡아서 그 숫자를 기준으로 정렬을 한다.

빨간 막대가 pivot 이다. 이막대를 기준으로 범위 내 수들을 정렬한다.

최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

예를 들어

 17 22 27 12 15 37 54 가 있다고 하고

아무튼 피봇으로 22를 고르면

17 12 15             [22]              27 37 54 이렇게 큰거 작은거로 나누고

이렇게 나눠졌으니까 22앞에 3개 뒤에 3개는 무조건 고정이다.

그다음 피봇으로 15같은거 고르면

12           [15]           17       [22]      27 37 54 이렇게 오고

12보다 작은거 없으니까 12 고정, 15와 22사이에도 17뿐이니까 고정쓰.

[12 15 17 22] 고정이고 그다음에 그냥 37을 피봇으로 잡고싶으니까 잡아버리면

딱 정렬이 된다.

물론 코드는 이렇지 않습니다.

#include <iostream>
#define SWAP(x, y) ( (x)^=(y), (y)^=(x), (x)^=(y) ) //use XOR
#define MAX 101010
int arr[MAX] = {0,};
using namespace std;
/********************************************
pivot을 찾고 pivot기준으로 정렬해주는 partition
반환값은 최종 pivot의 위치를 반환.
********************************************/
int partition(int arr[], int left, int right){
    int pivot, low, high;
    pivot = arr[left];
    cout << "now pivot : " << pivot << endl;
    low = left + 1;
    high = right;
    do{
        while(low <= right && arr[low] < pivot){
            low++;
            
            cout << "looking : "<<arr[low] << "<-- low"<<endl;
        }
        while(high >= left && arr[high] > pivot){
            high--;
            cout << "looking : "<<arr[high] << "<-- high"<<endl;
        }
        if(low < high){
        //before cross
            cout << "swap : " << arr[low] <<" , " << arr[high] << endl;
            SWAP(arr[low], arr[high]);
        }
    } while(low < high);

    if(high!=left) {
        SWAP(arr[high], arr[left]);
    }
    return high;
}
void quicksort(int arr[], int left, int right){
    if(left < right){
        int q = partition(arr, left, right);
        //1. arr[q] is sorted.
        //2. arr[left~q-1]까지는 arr[q]보다작음.
        //3. arr[q+1~right]까지는 arr[q]보다 크다.
        quicksort(arr,left, q-1);
        quicksort(arr, q+1, right);
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n ; i++){
        cin>>arr[i];
    }
    quicksort(arr, 0, n-1);
    for(int j = 0 ; j < n ; j++){
        cout << arr[j] << " ";
    }
    cout << endl;
}

주석 너무 잘들어가있어서 한번 돌려보면 알겠지만

아니다 돌려보겠다 위에적었던 저걸

7
17 22 27 12 15 37 54

피봇을 첫번째걸로 잡았다.

그러면 low는 뒤에서 high은 앞에서

하나씩 보면서 pivot을 기준으로

low ->피봇보다 작으면 통과, 크면 멈춤.

high -> 피봇보다 크면 통과, 작으면 멈춤.

둘다 멈춤일 경우 -> 교체함.

가다가 가다가 교차할경우 -> 한칸 더 가서 high가 low보다 작으면

high가 pivot가 되고, pivot이 high자리로 가서 다시 시작한다.