03. 3차시 교육

01.cpp - 버블소트(거품정렬)

#include <stdio.h>
#include <algorithm>
using namespace std;
//bubble sort
int arr[100];
void f(int n){
    for(int i=0; i<n-1; ++i){
        if(arr[i]>arr[i+1]){
            swap(arr[i], arr[i+1]);
        }
        if(i==n-2){
            i=-1;
            n-=1;
            continue;
        }
    }
}
 
int main(){
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; ++i){
        scanf("%d", &arr[i]);
    }
    f(n);
    for(int i=0; i<n; ++i){
        printf("%d\n", arr[i]);
    }
}

버블 소트입니다. 이중for문을 저런식으로 구현해봤습니다. 변수 하나 적게 쓰는것 말고는 다른 이점은 없는것 같습니다 ㅎㅎ..

big-O 표기법 정리

T({n(n-1)/2}) => O(n^2);

T : 시간을 자세히 계산.

O : T()에서 차수가 가장 큰 항에서 계수를 떼고 뒤에 있는 항들 모두 떼고 남은 것만 본다.

아래는 정석입니다.  void f(int n)에 들어간답니다.

for(int i=0; i<n-1; ++i){
    for(int j=0; j<n-1; ++j){
        if(arr[j]>arr[j+1])
            swap(arr[j], arr[j+1]);
    }
}

02.cpp - 퀵소트

//partition:기준값 기준으로 작은거 앞으로 큰거 뒤로. 각각의 순서는 상관 없음. 그리고 p기준으로 앞/뒤 나눔
//
#include <cstdio>
#include <algorithm>
using namespace std;
//qsort(void *base, size_t nel, size_t width)
//이거와 compare() <=요거는 필요 없을것같아서 안씁니다~ 저거 외울바에는 다른거 쓰면 됩니다.
 
int partition(int *arr, int P, int R){
    int pivot=arr[R];
    int i=P-1;
 
    for(int j=P; j<R; ++j){
        if(arr[j]<pivot){
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i+1], arr[R]);
    return i+1;
}
 
void QuickSort(int *arr, int P, int R){
    if(P>=R) return;
    int q=partition(arr, P, R);
    QuickSort(arr, P, q-1);
    QuickSort(arr, q+1, R);
    return;
}
 
int main(){
    int n;
    int arr[10000];
    scanf("%d", &n);
    for(int i=0; i<n; ++i){
        scanf("%d", &arr[i]);
    }
    QuickSort(arr, 0, n-1);
    for(int i=0; i<n; ++i){
        printf("%d ", arr[i]);
    }
}

퀵소트 입니다. Quick Sort

어떻게 작동하는지 설명 해드리겠습니다.

1. 함수 설명

(1) partition(int *arr, int P, int R)

int *arr => call by reference. 전역변수와 같은 역할을 하죠~

int P  =>  검사 시작 인덱스

int R  =>  검사 끝 인덱스

pivot : 기준점. 아무곳이나 찍어도 되지만 알고리즘 설계의 편의를 위해서 맨 마지막 인덱스로 설정합니다.

이제 기준점을 가운데 두고 양 옆으로 왼쪽으로는 기준점보다 작은 수들이, 오른쪽으로는 기준점보다 큰 수들이 오게 합니다.

이제 j가 점점 증가하면서 arr[j]가 가리키는 수가 pivot보다 작을 때 arr[i+1]과 arr[j]의 자리를 바꿉니다.

<설명>

i는 P-1의 위치에, j는 P의 위치에 놓습니다. pivot은 맨 마지막에 놓습니다.

첫번째 경우에선 arr[j]가 pivot보다 큽니다. 그냥 넘어갑니다.

arr[j]가 pivot 보다 작습니다.

 arr[i+1]과 arr[j]를 바꿔줍니다. 이 방법을 계속 반복합니다.

4를 기준으로 왼쪽엔 4보다 작은 숫자들이, 오른쪽엔 4보다 큰 숫자들이 온 것을 알 수 있습니다.

이제 pivot을 기준으로 왼쪽과 오른쪽 부분을 다시 퀵소트 해줍니다. return 조건은 먼저 있어야 할 P가 R보다 크거나, 둘이 같을 때(비교할 필요가 없으므로) 입니다.

03.cpp - Quick Select

//quickselect
//+Deterministic selection : O(n) =>
//모든 배열 5개로 쪼개고 쪼갠것 중에 중간값 다 구하고 그것들의 중간값을 다 구하고
//그 중간값들을 정렬하면 그것에서의 중간값은 최소 25%~75%가 확정된다.
#include <cstdio>
#include <algorithm>
using namespace std;
int want;//want는 정렬했을 때(오름차순) 앞에서 몇등인지를 구하는겁니다. 1등==제일 작은 수.
int partition(int *arr, int P, int R){
    int pivot=arr[R];
    int i=P-1;
 
    for(int j=P; j<R; ++j){
        if(arr[j]<pivot){
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i+1], arr[R]);
    return i+1;
}
 
void QuickSort(int *arr, int P, int R){
    if(P>=R) return;
    int q=partition(arr, P, R);
    if(q==want){
        return;
    }
    else if(want<q){
        QuickSort(arr, P, q-1);
    }
    else{
        QuickSort(arr, q+1, R);
    }
    return;
}
 
int main(){
    int n;
    int arr[10000];
    scanf("%d", &n);
    for(int i=0; i<n; ++i){
        scanf("%d", &arr[i]);
    }
    scanf("%d", &want);
    want--;
    QuickSort(arr, 0, n-1);
    printf("\n%d", arr[want]);
}

퀵소트를 활용한 quickselect입니다. 퀵소트와 동작 방식은 같지만 이진탐색 방식과 거의 같은 방식인 중간값의 인덱스보다 찾고자 하는 인덱스가 더 작으면 왼쪽으로 퀵소트, 아니면 오른쪽으로 퀵소트를 해서 더 빠르게, 시간낭비 없이 찾는 방식입니다.

*Deterministic Selection

더욱 획기적으로 탐색 시간을 단축시킬 수 있는 알고리즘입니다.

1. 원소들의 배열을 5개의 배열로 쪼갭니다. 각각의 배열을 S[0]. S[1]. ... , S[i]로 놓습니다.

2. S[i]에서 각각의 배열의 중간값을 찾고, 그 값을 X[0]. X[1]. ... , X[i]에 저장합니다.

3. X[0], X[1], ... , X[i]에서 중간값을 찾습니다. 그 중간값을 partition 함수의 값으로 놓고 이때부턴 quickselect의 방식을 따르면 됩니다.

결과적으로 Big-O표기법에 따르면 O(n)의 시간이 걸리게 됩니다. Awesome!