빅 오 표기법 4. 삽입 정렬

기준 인덱스 다음 원소값을 임시 변수에 저장해 그 값을 왼쪽 원소들과 차례로 비교해 임시 변수의 값이 왼쪽 원소값보다 작다면 앞으로 시프트시키며 정렬한다.

 

 

패스스루1

인덱스 1의 값 2는 임시변수에 저장

4

2

7

1

3

앞의 원소값들과 비교 후 시프트한 후 저장

2

4

7

1

3

 

 

패스스루2

인덱스 2의 값 7은 임시변수에 저장

2

4

7

1

3

앞의 원소값들과 비교 후 시프트한 후 저장 (임시변수값이 더 크다 고로 그대로 저장)

2

4

7

1

3

 

 

패스스루3

인덱스 3의 값 1은 임시변수에 저장

2

4

7

1

3

앞의 원소값들과 비교 후 시프트한 후 저장

1

2

4

7

3

 

 

 

패스스루4

인덱스 4의 값 3은 임시변수에 저장

1

2

4

7

3

앞의 원소값들과 비교 후 시프트한 후 저장

1

2

3

4

7

 

 

삽입정렬은 버블정렬, 선택정렬과 달리 삭제(임시변수에저장), 비교, 시프트, 삽입 4개의 단계종류가 있다.

비교는 각 패스스루가 진행될때마다 1씩 증가한다. 1 + 2 + ...  (N - 1) = 의 비교가 일어난다.

시프트도 마찬가지로 1 + 2 + ...  (N - 1) = 의 시프트가 일어난다.

 

삭제와 삽입은 항상 패스스루당 1번만 일어나니 N - 1 = 의 삭제 삽입이 일어난다.

모든 단계를 더하면 N^2/2 + N^2/2 + N-1 + N-1 = N^2+2N 의 단계가 일어난다.

 

 

잠시 집고 넘어가겠다.

예를 들어 N^4 + N^3 + N^2 + N 단계가 있을때 빅 오 표기법에선 단순히 O(N^4) 라고만 표기한다.

그 이유는 가장 큰 차수가 끼치는 영향이 다음 큰 차수보다 훨씬 크기 때문이다.

N	N^2	N^3	N^4
2	4	8	16
5	25	125	625
10	100	1000	10000
100	10000	1000000	1000000000
1000	1000000	1000000000	1000000000000

 

 

다시 돌아와서 결국 N^2+2N 은 N^2단계 이다. 결론적으론 버블, 선택, 삽입정렬 모두 N^2단계 이다.

 

하지만 지금까진 최악의 시나리오만을 대상으로 했을때에는 선택정렬이 가장 효율적이고 버블, 삽입정렬은 덜 효율적인걸 알수있다. 그러나 평균적인 시나리오를 가장했을때는 결과가 달라진다.

 

 

삽입정렬은 최악의 시나리오일땐 O(n^2)이지만 평균일땐 O(n^2/2)이고 최선일땐 O(n)이 된다.

반면 선택정렬은 최악이나 최선이나 항상 O(n^2/2) 이다. 즉, 경우에 따라 삽입과 선택정렬을 써야된다.

 

 

function intersection(first_array, second_array) {
	var result = [];
    for(var i = 0 ; i < first_array.length ; i++) {
    	for(var j = 0 ; j < second_array.length ; j++) {
        	if(first_array[i] == second_array[j]) {
            	result.push(first_array[i]);
        		break;
            }
        }
    }
}