[알고리즘] 삽입정렬
삽입정렬은 배열을 양분하고 왼쪽은 정렬상태, 오른쪽은 비정렬상태를 유지해 나가며 오른쪽(비정렬상태) 첫번째 요소를 왼쪽 정렬상태의 적절한 위치에 삽입하는 방법으로 요소들을 정렬한다
한줄요약
정렬된 왼쪽 배열에 새 것을(비정렬된 배열의 요소중 하나) 하나씩 끼워넣기(삽입) 한다.
특징
- stable sort
- 시간복잡도: O(n^2)
자바스크립트 코드
function insertionSort(a){
for(var i=1; i<a.length; i++){
console.log(a);
var tmp = a[i];
for(var j=i-1; j>=0 && a[j]>tmp; j--){
a[j+1] = a[j];
}
a[j+1] = tmp;
}
return a;
}
insertionSort([7,4,2,1,9,3]);
/*
[7, 4, 2, 1, 9, 3]
[4, 7, 2, 1, 9, 3]
[2, 4, 7, 1, 9, 3]
[1, 2, 4, 7, 9, 3]
[1, 2, 4, 7, 9, 3]
[1, 2, 3, 4, 7, 9]
*/
Comments