오늘 배운 것
삽입 정렬(Insertion Sort)
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. <위키백과>
- 우선 난 위키백과의 삽입정렬에 대한 정의를 보고 아무것도 이해하지 못했다...
- 그래서 삽입정렬을 그림으로 표현한 것을 보았는데
- 여전히 감이 안잡혀서 여러 블로그를 순회하기 시작했다.
- 삽입정렬의 핵심은 배열의 모든 요소를 순회하면서 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하는 방식이라는 것이었다.
구체적인 개념
- 삽입 정렬은 두 번째 요소부터 시작해서 앞(이미 정렬된 배열 부분)의 요소들과 비교하여 적절한 위치에 삽입하게 되는데, 이때 원래 자리에 있던 요소는 뒤쪽으로 옮긴다.
- 첫 번째 요소는 이미 정렬이 되어있다고 가정을 하고, 두 번째 요소부터 비교를 시작하게 된다.
- 두 번째 요소는 이미 정렬된 배열(1번 요소)과 비교를 하고, 다음번으로 세 번째 요소는 이미 정렬된 배열(2번 요소, 1번 요소), 다음으로 네 번째 자료는 이미 정렬된 배열(3번 요소, 2번 요소, 1번 요소)과 비교한 후 자료가 삽입될 위치를 찾게 된다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
- 예시
구현 코드(JavaScript)
- 내가 구현한 코드
//오름차순 정렬을 삽입 정렬 방식을 이용해 구현해보고자 한다.
var insertionSort = function(array) {
let j;
for(let i = 1; i < array.length; i++){ //비교를 시작할 두 번째 요소 지정
let currentElement = array[i] //새로운 변수에 비교할 값을 담는다.
//이미 정렬된 배열과 비교해야 하므로, 비교할 값보다는 idx가 낮아야 할 것이다.
for(j = i-1; j >= 0; j--){
//비교할 값보다 앞선 값이 더 크면
if(currentElement< array[j]){
//오른쪽에 할당한다.
array[j+1] = array[j]
//비교할 값보다 작으면(잘 정렬이 되어있으면), for문을 나간다.
}else{
break;
}
}
//남아 있는 빈칸에 비교할 값을 담는다.
array[j+1] = currentElement
}
return array;
};- 제로초님의 블로그의 예시
var insertionSort = function(array) {
var i = 1, j, temp;
for (i; i < array.length; i++) {
temp = array[i]; // 새로운 숫자를 선택함
for (j = i - 1; j >= 0 && temp < array[j]; j--) { // 선택한 숫자를 이미 정렬된 숫자들과 비교하며 넣을 위치를 찾는 과정, 선택한 숫자가 정렬된 숫자보다 작으면
array[j + 1] = array[j]; // 한 칸씩 뒤로 밀어낸다
}
array[j + 1] = temp; // 마지막 빈 칸에 선택한 숫자를 넣어준다.
}
return array;
};
insertionSort([5, 6, 1, 2, 4, 3]); // [1, 2, 3, 4, 5, 6]
//for문 조건식 안에 비교할 조건문을 넣어버리면,
//그것을 만족하지 못했을 때 곧바로 반복문이 끝나버리기 때문에
//내가 구현한 코드에서처럼 break를 따로 써줄 필요가 없었다.참고문헌
다 늦은 밤, 달밤의 개발일기