정렬 알고리즘 중 삽입 정렬(Insertion sort)에 대해서 설명을 드리고, 백준 알고리즘에서 실전 문제를 푸는 것 까지 진행을 해볼게요.
삽입 정렬은 정렬 알고리즘을 처음 접하시는 분들도 매우 직관적으로 이해 할 수 있는 알고리즘 입니다.
매우 간단한 알고리즘인데요.
간단하게 설명을 드리면
삽입 정렬은 배열의 모든 요소를 하나씩 비교하면서,
비어있는 배열에 하나씩 옮기는 방식의 알고리즘 입니다.
이 옮기는 과정에서 정렬이 되도록 삽입 해줍니다.
즉, 올바른 위치에 계속해서 삽입(Insertion) 만 해준다면 우리는 정렬이 된 배열을 얻을 수 있습니다.
그림으로 설명해 드릴게요.
저희는 3, 1, 7 3개의 숫자가 있는 배열을 가지고 있고,
이 배열을 정렬을 하고 싶습니다.
오름차순으로 정렬을 하여 1, 3, 7 배열을 얻고 싶은거죠.
위에 설명대로 첫번째 3을 비어있는 배열에 옮기겠습니다.
첫번째 요소이고 옮길 곳은 배열이 비어있기 때문에 그냥 3을 옮겨놓습니다.
다음으로 1을 옮겨야 하는데요.
이미 3보다 큰 3이 배열에 들어가 있기 때문에
1은 3보다 앞에 삽입(Insertion) 되어야 합니다.
3을 한칸 뒤로 밀고 1을 넣으면 아래처럼 됩니다.
마지막으로 7을 넣어야 하는데,
복사본 배열과 비교를 해보니 모든 숫자가 7보다 작네요.
그럼 제일 끝에 삽입을 하면 되겠네요.
이렇게 정렬이 완료 되었습니다.
백준에서 관련 문제를 찾아보겠습니다.
많은 정렬 문제가 있지만, 삽입 정렬은 O(n^2)의 방법이기 때문에 시간제약이 적은 문제를 가서 풀어야합니다.
백준에서는 2750번: 수 정렬하기 문제에서 연습해보실 수 있습니다.
https://www.acmicpc.net/problem/2750
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
해설
저는 문제를 풀기에 앞서서 함수를 먼저 작성하였는데요.
정렬을 위한 Sort라는 함수를 작성하였고.
삽입정렬에서의 삽입 이라는 기능을 위한 insert라는 함수를 정의하였습니다.
Sort 함수에서는 기존 배열의 요소들을 하나씩 insert 함수를 사용하여 정렬을 하고,
insert 함수는 각 요소가 들어갈 위치를 찾고 삽입하는 역할을 수행합니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const N = parseInt(input[0]);
const list = [];
for(let i = 1; i <= N; i++) {
list.push(parseInt(input[i]));
}
// sort 함수 구현
function sort(unsortedList) {
const sortedList = []
for(let num of unsortedList) {
insert(sortedList, num)
}
return sortedList;
}
// 삽입 함수 구현
function insert(sortedList, num) {
let index = -1;
for(let i = 0; i < sortedList.length; i++) {
if(sortedList[i] < num) {
continue;
} else {
index = i;
break;
}
}
if(index < 0) {
sortedList.push(num);
} else {
sortedList = sortedList.splice(index, 0, num);
}
}
let sortedList = sort(list);
for(let num of sortedList) {
console.log(num);
}
|
cs |
