이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌2 - Algorithm - 일 년 전 등록 / 4달 전 수정

삽입 정렬

조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간에는 삽입 정렬에 대해 알아보겠습니다. 알고리즘에는 많은 유형이 있지만 주로 탐색정렬하는 것들이 많습니다. 탐색을 하기 전에는 미리 정렬을 해야 합니다. 정렬된 자료를 탐색하는 강력한 알고리즘이 있거든요. 정렬하는 방법도 여러가지가 있습니다. 그 중에 오늘은 삽입 정렬 차례입니다.

여러 개의 섞인 숫자가 있을 때, 그 숫자를 작은 순서부터 큰 순서로 정렬하는 겁니다. 삽입 정렬은 첫 숫자는 놔두고, 두 번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣습니다. 세 번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣습니다. 이렇게 끝까지 계속하면 정렬됩니다.

쉽게 설명하면 오른손에 쥔 정렬되지 않은 카드를 왼손에 정렬한다고 생각하시면 됩니다. 하나를 뽑아서 왼손에 놓고, 다음 카드는 먼저 뽑은 카드들과 비교하여 알맞은 위치에 넣어줍니다. 이렇게하면 결국 왼손에는 정렬된 카드만 남습니다.

코드로 보면 어려우니까 배열이 움직이는 과정을 쉽게 예를 하나 들어서 순서대로 봅시다. 크게 두 가지 과정이 있습니다. 첫째는 다음 숫자를 선택하는 과정이고, 둘째는 선택한 숫자를 이미 정렬된 숫자들과 비교해 알맞은 위치에 넣는 과정입니다.

[5, 6, 1, 2, 4, 3]과 같은 배열이 있습니다.
첫 번째는 넘어가고 두 번째부터 시작합니다. 숫자 6을 선택하고
[5, 6, 1, 2, 4, 3]
앞의 5와 비교하는데 5보다 크기 때문에 그냥 그 자리에 둡니다. 다음 숫자 1을 선택합니다.
[5, 6, 1, 2, 4, 3]
1은 앞의 5, 6보다 작기 때문에 5, 6 앞에 넣어줍니다. 다음 숫자 2를 선택합니다.
[1, 5, 6, 2, 4, 3]
2는 1보다는 크고, 5와 6보다는 작기 때문에 그 사이에 넣어줍니다. 다음 숫자 4를 선택합니다.
[1, 2, 5, 6, 4, 3]
마찬가지 과정으로 1,2와 5,6 사이에 넣어줍니다. 다음 숫자 3을 선택합니다.
[1, 2, 4, 5, 6, 3]
마지막으로 1,2와 4,5,6 사이에 3을 넣고, 다음 숫자가 없으므로 종료합니다.
[1, 2, 3, 4, 5, 6] 정렬이 완료되었습니다. 

이제 코드로 만들어볼까요? 배열(array)을 받는 함수(insertionSort)를 만듭시다. 일단 뽑을 숫자의 위치를 선택할 변수(i)가 필요할 것 같습니다. 그리고 뽑은 숫자 값을 저장할 변수(temp)도 필요하고요. 뽑은 숫자를 알맞은 위치에 넣을 때 사용할 변수(j)도 있어야할 것 같네요.

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]

코드가 복잡합니다. 설명을 위해 console을 넣었습니다. 잘 보면 크게 두 과정을 반복하고 있음을 알 수 있습니다. 숫자를 선택한 후 알맞은 위치에 넣습니다. 알맞은 위치에 넣는 과정이 좀 헷갈리는데, 정렬된 숫자들 중 큰 숫자부터 비교하면서 선택한 숫자가 정렬된 숫자보다 클 때까지 반복하고, 커지면 그 사이에 집어넣습니다. 즉, 선택한 숫자보다 큰 숫자들은 오른쪽으로 한 칸씩 밀어내고 빈 자리에 선택한 숫자를 넣는 겁니다.

삽입 정렬은 성능이 뛰어난 정렬은 아닙니다. 작은 수에서만 효과적인 경우가 많습니다. 첫 번째로 배우는 이유는 간단하기 때문입니다. 또한 이미 정렬되어 있는 배열에 새로운 원소를 집어넣어 다시 정렬할 때는 매우 효과적입니다. 새 원소를 처음부터 한번씩만 기존의 원소들과 비교하면 되니까요.

보통 반복문을 두 번 중첩해서 돌면 성능이 그리 좋지 않습니다. 정렬이 효과적인지 아닌지 판단하려면 복잡도라는 개념을 알아야합니다. 삽입 정렬은 다른 정렬에 비해 복잡도가 높기 때문에 효과적이지 못하다고 평가받습니다.

정렬을 평가할 때, 복잡도라는 개념을 사용한다고 했습니다. 주로 정렬하는 데 걸리는 시간의 복잡도를 따집니다. 정렬을 할 때 얼마나 시간이 걸리는 지가 중요한 데 이를 평가하는 기준으로 여러가지 표기법이 있습니다. 이것들을 다음 시간에 알아보겠습니다.

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

4개의 댓글이 있습니다.
4달 전
마지막부분에 이해가 가지 않아서... 이런 짓을 했는데, 지금은 이해가 갔습니다.
j의 값이 왜 한번 더 줄었는지 몰랐는데, 깊이2 for문(이름은 걍 제가 지었습니다)에서 j--로 인해서 그런 것인 듯.. 으로 이해. 여튼, 잘 봤습니다. 이제 시작하는지라 이런 강의가 참 감사합니다.

var insertionSort = function(array){
console.log("현재 array의 값은 ", array, "입니다. 이제 우리는 삽입정렬을 할 것입니다.")
var i = 1, j, temp, k;
for (i; i < array.length; i++){ //깊이1 for문
temp = array[i];
k=0;
console.log("** ", i, "번째로 실행되는 깊이1 for문입니다 **");
console.log("첫번째 for문의 현재 i의 값은 ", i, "이고 array의 길이는 ", array.length, " 입니다.")
console.log("따라서 array[", i,"]의 값은 ", array[i], "이고 현재 temp의 값은 ", temp, "입니다.");
for (j=i-1; j>=0 && temp < array[j]; j--){ //깊이2 for문
k= k+1;

array[j+1]= array[j];
console.log("** 현재 ", i, "-", k, "번째 깊이2 for문이 실행되었습니다.**");
console.log("array - 현재 i의 값은 : ", i, ", 현재 j의 값은 : ", j, ", 현재 array[", j, "] 값은", array[j], ", 현재 temp의 값은 : ", temp);
if (j>=0 && temp < array[j]) {
console.log("조건문 j>=0 && temp < array[j] 을 만족합니다.")
console.log("따라서 array[", j,"]의 값 ", array[j], "는 array[", j+1,"]에 대입됩니다.")
}


}
array[j+1] = temp;
console.log("... 깊이2 for문의 조건문 j>=0 && temp < array[j] 을 만족하지 않아 ", i, "-", k, "번째 깊이2의 for문이 종료되었습니다.")
console.log("현재 i의 값은 ", i, "현재 j의 값은 ", j, " 입니다.")
console.log("현재 위치는 깊이2 for문을 마치고 깊이1 for문의 하단입니다. 여기서 temp의 값", temp, "는 array[", j+1,"]에 대입됩니다.")
console.log("깊이1 for문을 마친 현재 array의 값은 ", array, "입니다.")
}
console.log(array);
return array;
}
insertionSort([5,6,1,2,4,3]);
4달 전
이중 for문이라고 부릅니다.
4달 전
안쪽 포문의 조건식에서 콤마연산자(,)가 사용되었는데
콤마연산자(,)는 항상 마지막 연산값을 넘겨주므로, j>=0은 있으나마나 아닌가요?
(array[-1]의 값보다 작은 값이 array에 있다면, 버그가 날것 같습니다.)
4달 전
아아 &&의 오타입니다. 감사합니다.
4달 전
재귀함수 참고해서 알고문제를 풀어봣어요.
```
// 1 ~ 10,000의 수자 중 8이 등장하는 횟서 ㄱㅜ하기.
//1 부터 10,000까지 8이라는 숫자가 총 몇번??
//8이 포함되어 잇는 숫자의 갯수를 카운팅 하는것이 나리ㅏ 8이라는 숫자를 모두 카운팅
//예를들어 8808은 3, 8888 4로 카운팅.

/*function getCountsMine() {
var array;
var eight = [];

for (var i = 1; i <= 10000; i++) {
//var num = i;
var string = i.toString();
array = string.split('');
//array = [1] ... [8]
for (var k = 0; k <= i; k++) {
if (array[k] == 8) {
var eightArray = array.join();
eight.push(parseInt(eightArray));
}
}
}

return eight.length;
//4000
}
```
4달 전
엥? 재귀함수 부분이 없는데요?
8달 전
선택된 수가 더 큰지 작은지 판별할 조건문이 없어보이는데...
8달 전
for문 안에 temp < array[j]가 있습니다~
8달 전
아.. 저런방법이 있군요!