Ch.06 긍정적인 시나리오 최적화 (도서 요약 "누구나 자료구조와 알고리즘")

지금까지는 주로 최악의 시나리오에서 얼마나 많은 단계가 걸리는지에 초점을 맞췄지만, 최악의 시나리오 외에도 고려할 가치가 있는 상황들이 있다. 그래서 모든 시나리오를 고려할 수 있는 능력이 중요하다. 

6. 1  삽입 정렬

---

버블 정렬과 선택 정렬 둘 다 효율성이 O(N²)이지만, 실제론 선택 정렬이 두 배 더 빠르다.

 

'삽입 정렬(insertion sort)'은 또 다른 정렬 알고리즘이다.

 

삽입 정렬은 다음과 같은 단계를 따른다. 

 

(1) 첫 번째 패스스루에서 '임시로' 인덱스 1(두 번째 셀)의 값을 삭제하고, 이 값을 임시 변수에 저장한다. 이제 인덱스 1에 값이 없으므로 공백이 생긴다.

(2) 공백 왼쪽에 있는 값을 임시 변수에 저장한 값과 비교한다.

(3) 공백 왼쪽에 있는 값이 임시 변수에 있는 값보다 크면 왼쪽에 있던 값을 오른쪽으로 옮긴다. 자연스럽게 공백은 왼쪽으로 옮겨진다.

(4) 만약 공백이 배열의 왼쪽 끝에 도달하면 임시로 제거한 값을 현재 공백에 삽입한다. 비로소 시프트 단계가 끝나서 첫 번째 패스스루가 종료된다(공백이 맨 왼쪽에 도달하거나, 임시로 삭제한 값이 왼쪽 값보다 클 경우 패스스루를 종료한다).

 

(5) 두 번째 패스스루가 시작되면서 '임시로' 인덱스 2의 값을 삭제하고, 이 값을 임시 변수에 저장한다. 인덱스 2에 값이 없으므로 공백이 생긴다.

(6) 공백 왼쪽 값을 임시 변수에 저장한 값과 비교한다. 만약 공백 왼쪽 값보다 임시로 삭제한 값이 크면 그대로 임시 삭제 값을 공백에 삽입하고 패스스루를 끝낸다.

공백 왼쪽 값이 임시로 삭제한 값보다 크면 왼쪽 값을 오른쪽으로 시프트 한다. 

(7) 오른쪽으로 시프트 했다면 다음 값과 또 비교한다.

 

 

(8) 두 번째, 세 번째...  패스스루에서 위 단계를 반복하다가 마지막 인덱스에서 패스스루를 시작할 때 배열이 완전히 정렬된다.

6. 2  삽입 정렬 실제로 해보기

---

삽입 정렬을 자바 코드로 나타내면 다음과 같다.

 

public void insertionSort(int[] arr) {
    //  하나의 패스스루를 실행
    for(int i=1; i<arr.length; i++) {
        //  임시 변수 tempValue에 인덱스 1부터의 값을 저장
        int tempValue = arr[i];
        //  임시 변수와 값을 비교할 왼쪽 인덱스
        int position = i - 1;

        //  하나의 패스스루에서 비교하며 왼쪽으로 이동
        while(position >= 0) {
            if(arr[position] > tempValue) {
            arr[position + 1] = arr[position];
            position = position - 1;
            }
        else
            break;
        }
    //  마지막 공백에 임시 저장 변수의 값을 '삽입'
    arr[position + 1] = tempValue;
    }
    System.out.println(Arrays.toString(arr));
}

​

각 패스스루를 나타내는 루프를 시작한다. 매 루프가 하나의 패스스루를 뜻한다. i가 1부터 시작하는 이유는 인덱스 1부터 임시로 값을 삭제하기 때문이다.

 

for(int i=1; i<arr.length; i++) {

 

각 패스스루마다 "제거 중인" 값을 tempValue라는 변수에 저장한다.

 

int tempValue = arr[i];

 

position이라는 변수를 만들어 tempValue의 바로 왼쪽 인덱스에서 시작시킨다. position은 tempValue와 비교할 각 값을 나타낸다.

 

int position = i - 1;

 

패스스루를 통과하면서 position은 계속 왼쪽으로 움직이며 각 값을 tempValue와 비교하는데, position이 0보다 같거나 큰 동안에만 실행되는 안쪽 while 루프를 시작시킨다.

position과 position - 1 값을 비교해서 position - 1의 값이 더 크면 왼쪽 값을 오른쪽으로 시프트 한다.

이어서 다음 왼쪽 값을 다음 while 루프의 tempValue와 비교할 수 있도록 position 값을 1 감소시킨다.

 

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

 

각 패스스루의 마지막 단계는 공백에 tempValue를 '삽입'하면 된다.

 

arr[position + 1] = tempValue;

6. 3  삽입 정렬의 효율성

---

선택 정렬은 '삭제', '비교'와 '시프트', '삽입'이라는 네 종류의 단계를 가진다. 삽입 정렬의 효율성을 분석하려면 각 단계별 총합을 계산해야 한다.

 

먼저 '비교'는 공백 왼쪽에 있는 값과 tempValue를 비교할 때마다 일어난다. 최악의 시나리오라면 tempValue 왼쪽에 있는 각각의 값들이 항상 더 크기 때문에, 각 패스스루마다 tempValue는 왼쪽에 있는 모든 수와 비교해야 한다. 따라서 각 패스스루는 공백이 배열의 왼쪽 끝으로 가야만 끝날 수 있다.

 

첫 번째 패스스루에서는 인덱스 1의 왼쪽에 값이 하나뿐이므로 최대 1번의 비교가 일어난다. 두 번째 패스스루에서는 최대 2번의 비교가 일어난다. 마지막 패스스루에서는 tempValue 스스로를 제외한 배열 내 모든 값을 비교해야 하기 때문에 최대 N - 1번의 비교가 발생한다.

 

총 비교 횟수는 1 + 2 + 3 +..... + N - 1번이다.

그래서 원소가 5개인 배열이면, 1 + 2 + 3 + 4 = 최대 10번 비교한다. 대략 N² / 2번의 비교가 일어나는 것이다.

 

'시프트'는 값을 한 셀 오른쪽으로 옮길 때마다 일어난다. 최악의 시나리오에선 비교가 일어날 때마다 값을 오른쪽으로 시프트 해야 하므로 비교 횟수만큼 시프트가 일어난다. 고로 N² / 2번의 시프트가 발생한다.

 

배열로부터 tempValue를 삭제하고, 다시 삽입하는 작업은 패스스루당 한 번 일어난다. 패스스루는 항상 N - 1번이므로 결국 N - 1번의 '삭제'와 N - 1번의 '삽입'이 있다.

 

이 모든 단계를 합하면 다음과 같다.

 

N² + 2N - 2단계

 

빅 오에는 상수를 무시해서 O(N² + N) 단계로 단순화시킬 수 있다. 그러나 여기서 새로운 규칙이 또 있다.

 

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

 

즉, N⁴ + N³ + N² + N¹단계가 걸리는 알고리즘이 있을 때 N⁴만 중요하게 여겨서 단순히 O(N⁴)라고 부른다. 그 이유는 N이 증가할수록 어떤 N차수보다 N⁴의 비중이 훨씬 더 커져서 작은 차수는 미미해 보이기 마련이다. 그래서 낮은 차수의 N을 무시한다.

 

삽입 정렬에서도 O(N² + N) 대신 O(N²)으로 표현식을 더 단순화한다.

 

여기까지 보면, 버블 정렬도, 삽입 정렬도, 선택 정렬도 모두 O(N²)이다. 조금 더 들여다보면 선택 정렬이 N² / 2 단계로 더 빠르다고 생각할 수 있다. 

 

하지만 그렇게 간단하지 않다.

6. 4  평균적인 경우

---

최악의 시나리오에서는 '삽입 정렬(insetion sort)'이 '선택 정렬(selection sort)'보다 느리다. 하지만 최악의 시나리오 또는 최선의 시나리오는 드물게 발생하고 실제로는 대부분 평균 시나리오가 일어난다.

 

 

모든 시나리오에서 삽입 정렬을 검토해 보자.

 

- 최악의 시나리오 : 각 패스스루마다 모든 값을 비교하고 시프트를 하기 때문에 총 N²의 비교와 시프트가 발생했다.

 

- 최선의 시나리오 : 에선 각 값이 이미 올바른 위치에 있으므로 패스스루당 한 번의 비교만 하고, 시프트는 한 번도 일어나지 않아서 N단계이다.

 

- 평균 시나리오 : 대체적으로 데이터의 반을 비교하고 시프트 할 것이다. 최악의 시나리오의 절반, 즉 N² / 2단계가 걸린다고 말할 수 있다. (빅 오 관점에서는 모두 O(N²)이지만)

 

정리하면 최악의 시나리오(N²단계), 최선의 시나리오(N단계), 평균 시나리오(N² / 2단계)가 걸린다. 따라서 삽입 정렬은 시나리오에 따라 성능이 크게 좌우된다.

 

이에 반해, 선택 정렬은 최악부터 평균, 최선의 시나리오 모두 N² / 2단계가 걸린다. 각 패스스루마다 무조건 선택된 인덱스의 오른쪽에 있는 값들 모두와 비교해야 하기 때문에 특정 시점에서 미리 끝낼 수가 없다.

 

선택 정렬과 삽입 정렬의 효율성 비교

 

그래서 경우에 따라 선택 정렬과 삽입 정렬의 우위가 달라진다. 데이터가 어떨지 전혀 알 수 없다면 기본적으로 평균적인 경우이며 둘 다 같다.

6. 5  실제 예제

---

예제로 두 개의 배열에 공통적으로 들어있는 값을 구하는 메서드를 만들어보자.

 

public void intersection(int[] arr, int[] arr2) {
    ArrayList<Integer> list = new ArrayList<>();

    for(int i=0; i<arr.length; i++) {
        for(int j=0; j<arr2.length; j++) {
            if(arr[i] == arr2[j]) {
                list.add(arr[i]);
            }
        }
    }
    System.out.println(list);
}

 

위 알고리즘은 '비교'와 '삽입' 두 종류의 단계를 포함한다.

만약 두 배열의 크기가 같고 배열 크기가 N이면 N²번의 '비교'를 수행한다. 예를 들어 두 배열이 각각 5개의 원소를 포함한다면 총 25번의 비교를 해야 끝난다. 이러한 교집합 알고리즘의 효율성은 O(N²)이다. '삽입'의 경우 최대 N단계가 걸리지만 N은 N²에 비해 차수가 낮으므로 무시돼서 알고리즘 상 여전히 O(N²)이다.

 

두 배열에 공통 값이 있다면 두 번째 배열의 모든 원소와 비교하지 않아도 된다. 동일한 값이 있다는 것이 확인되면 그 값은 더 이상 비교가 불필요하다. 그래서 뒤에 break; 를 추가해 안쪽 루프를 짧게 끝낼 수 있고 단계까지 절약할 수 있다. 

 

public void intersection(int[] arr, int[] arr2) {
    ArrayList<Integer> list = new ArrayList<>();

    for(int i=0; i<arr.length; i++) {
        for(int j=0; j<arr2.length; j++) {
            if(arr[i] == arr2[j]) {
                list.add(arr[i]);
                break;    //  break를 통해 불필요한 비교를 멈춘다
            }
        }
    }
    System.out.println(list);
}​

6. 6  마무리

---

최선의, 평균의, 최악의 시나리오를 구분하는 능력은 핵심 기술이다. 최악의 경우를 대비하지만 대부분은 평균적인 경우가 더 많이 일어난다.

---

'누구나 자료구조와 알고리즘' / 저자: 제이 웬그로우

해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.

오로지 학습용으로 작성하였음을 밝힙니다.

더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.