Algorithm & Data Structure(4) - 시나리오 최적화

kimseyoung·2023년 1월 13일
0

ComputerScience

목록 보기
5/8
post-thumbnail

삽입 정렬

지금까지 버블 정렬, 선택 정렬을 알아보았고, 선택 정렬이 버블 정렬 보다 약 두배 빠름 또한 알고 있다. 이번에는 삽입 정렬을 통해, 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아 보자.

#include<stdio.h>

int main() {

    int array[] = {1,2,3,4,7};
    int array_length = sizeof(array)/sizeof(int);
    
    for(int i = 1; i < array_length; i++) {
        int temp_value = array[i];
        int position = i -1;

        while (position >= 0) {
            if(array[position] > temp_value) {
                array[position +1] = array[position];
                position -= 1;
            }
            else {
                break;
            }
        }
        
        array[position+1] = temp_value;

        
    }

    for(int k = 0; k < array_length; k++) {
            printf("%d", array[k]);
    }


    return 0;
}

위는 삽입 정렬의 C코드이다. 삽입 정렬은 시프트라는 단계를 포함한다. while문 내부가 시프트 단계이다.(temp_value와 이전 값들을 모두 비교하여 이동시킨다.)
삽입 정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입 네종류가 되게 된다. 사입 정렬의 효율성을 분석하면 각 단계별 총합을 계산해야 한다.

먼저 비교를 살펴보자. 비교는 temp_value 와 그 왼쪽에 있는 값들을 비교할 때 마다 일어난다. 역순으로 정렬된 최악의 시나리오라면 각 패스스루마다 temp_value 왼쪽에 있는 모든 수를 temp_value와 비교해야 한다. temp_value 왼쪽에 있는 각 값이 항상 temp_value 보다 크기 때문이다. 따라서 각 패스스루는 맨 왼쪽 끝까지 진행되야 끝난다.

즉 최악의 상황에서 비교는 총 1+2+3+4+5+...+N-1번 일어난다.

즉, N^2/2 번 정도의 비교가 일어나게 된다.

그 다음 시프트의 경우도 최악의 경우 한번의 패스스루마다 비교 횟수만큼 시프트가 일어나게 된다. (예를 들어, 4번째 인덱스라면, 1,2,3번째 값을 모두 시프트 시켜야 한다.)

즉 N^2/2 의 비교와 N^2/2의 시프트가 일어나므로 N^2단계가, 비교와 시프트에서 소모되고, 패스스루는 항상 N-1번 일어나므로, 삭제 N-1번 삽입 N-1번이 일어나게 되므로

총 N^2+2N-2단계가 일어나게 된다. 이를 빅 오 표기법으로 표현하면, 상수는 무시하므로,

O(N^2+N)

으로 표현할 수 있다. 하지만, 빅 오는 다음과 같은 규칙이 또 있다.

다양한 차수가 한데 섞여 있을 때 빅 오 표기법은 가장 높은 차수의 N만 고려한다.

즉 N^4 + N^3 + N^2 + N 단계가 걸리는 알고리즘이 있을 때 N4만 중요하게 여기며 단순히 O(N^4)라고 부른다. 이는 이전에 상수를 버릴 때와 같은 개념이다. N^4의 변화에 나머지가 큰 영향을 주지 않기 때문이다.

시나리오 최적화

우리는 이러한 고민을 해봐야한다.
항상 최악의 상황이 발생할까? 당연히 아니다. 그래서 이젠 평균적인 상황을 살펴보자 삽입 정렬의 경우 최선, 평균, 최악의 상황에 걸리는 단계는 다음과 같다.

최선평균최악
NN^2/2N^2

즉, 우리가 최악만을 봐서 그렇지, 어떠한 상황이 일어날지는 모른다. 보통은 평균 시나리오를 따라가는것이 맞다. 다음은 선택 정렬의 최선, 평균, 최악 시나리오의 경우이다.

최선평균최악
N^2/2N^2/2N^2/2

선택 정렬의 경우 최선 평균 최악이 모두 같은 단계를 거친다. 최악의 경우 삽입 정렬이 2배나 더 느리지만, 평균은 같고, 최선의 경우는 삽입정렬은 선형 시간 알고리즘이 되어 성능의 비교가 안되게 된다. 이래서 때에 따라 적절한 알고리즘을 고르는 것이 좋다. 이미 거의 정렬된 데이터는 당연히 삽입 정렬이 좋을것이고, 가늠이 안된다면, 선택정렬이 좋은 선택이라고 할 수 있겠다.

profile
Full Stack Web & Machine Learning (Big Data Analyst, ADsP)

0개의 댓글