Blog

[알고리즘] 삽입정렬

On 8 10월, 2016 By With 0 Comments

삽입정렬
리스트의 2번째 값(index:1)부터 1씩 증가 하면서 해당 index보다 이전의 모든 값들을 순회하며 값 비교를 통한 정렬을 수행한다.
최대 시간복잡도(비교연산 횟수)는 리스트n-1팩토리얼로 구할 수 있으며 실제 복잡도는 구현 로직 내에서 값 비교 연산 횟수를 구하여 확인할 수 있다.

삽입정렬
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 삽입정렬
var aData = [8,5,1,7,3,9],
    count = 1;
 
for(var i=1, len=aData.length; i<len; i++){
    for(var j=0; j<i; j++){
        if(aData[i] < aData[j]){
            count++;
            temp = aData[i];
            aData[i] = aData[j];
            aData[j] = temp;
        }
    }
}
 
function ft(n){
    if(n==1) return n;
    return n+ft(n-1);
}
 
console.log('최대시간복잡도',ft(aData.length-1)); // 15
console.log('실제시간복잡도',count); // 8

*해당 포스트는 알고리즘 학습을 위한 포스트로 정확하지 못한 개념과 코드가 있을 수 있습니다. 익숙한 언어인 js로 코드를 작성하였는데 개념이나 적절하지 못한 코드는 코멘트 들아주시면 감사하겠습니다 ^^

 

, , , ,