오늘은 삽입 정렬을 구현해보기로 했다.
삽입 정렬은 정렬된 수와 다음 숫자를 비교하고,
정렬이 필요한 경우 필요하지 않을 때까지 앞의 수와 비교해 가면서 자리를 찾는다.
Try 1: 오직 직진
function insertionSort(arr){
let n = arr.length;
for (let i = 0; i < n; i++){
let now = arr[i];
for (let j = i+1; j>=1; j--){
if(arr[j] < now){
let temp = arr[j-1];
arr[j-1] = arr[j]
arr[j] = temp
}
else {break}
}
}
return arr
}이 코드는 예시 배열인 [4,6,2,9,1]을 오름차순으로 정렬하는 데 성공한 코드이다.
now를 정렬된 수로 삼아 다음 수와 비교하고, 순서를 바꿔야 할 경우에는 계속 앞으로 가면서 자리를 잡는다.
하지만 [5,7,1,6,2]를 입력했더니 결과값이 [ 2, 6, 1, 5, 7 ]로 제대로 작동하지 않았다.
[ 5, 7, 1, 6, 2 ]
[ 1, 5, 7, 6, 2 ]
[ 6, 1, 5, 7, 2 ]
[ 2, 6, 1, 5, 7 ]
[ 2, 6, 1, 5, 7 ]
[ 2, 6, 1, 5, 7 ]로그를 찍어 보았더니 갑자기 6이 앞으로 간다.
이 코드의 문제점은, 정렬이 필요하면 무조건 직진을 시킨다는 것에 있다.
처음에는 안쪽 for문에서 움직임을 제한하고 첫 for문 안에서 더 비교를 해야 하는지 고민했다.
그런데 그렇게 하면 어디까지 직진해야 하는지 갈피가 안 잡히고, 위치를 아는 now까지로 제한한 다음 밖에서 해결하려고 하면 어차피 한 자리밖에 못 가는데 for문을 이중으로 사용하는 의미가 없다.
삽입 정렬의 움직임을 보면 찔끔찔끔 확인하도록 고치는 것보다 Try1의 거침없는 형태가 더 유사하기에 결국 이 형태를 부수지 않고 고민해야 한다는 생각이 들었다.
그렇게 잘 생각해 보니, 문제 속에 답이 있었다.
'필요하지 않을 때까지 앞의 수와 비교'하는 것이다.
Try2: 브레이크 추가
function insertionSort(arr){
let n = arr.length;
for (let i = 0; i < n; i++){
let now = arr[i];
for (let j = i+1; j>=1; j--){
if(arr[j] < now && arr[j] < arr[j-1] ){
let temp = arr[j-1];
arr[j-1] = arr[j]
arr[j] = temp
}
else {break}
}
}
return arr
}의외로 방법이 간단했다. 더 가도 되는지를 &&으로 판단한다.
아까의 배열을 다시 입력해서 로그로 찍어 보면,
[ 5, 7, 1, 6, 2 ]
[ 1, 5, 7, 6, 2 ]
[ 1, 5, 6, 7, 2 ]
[ 1, 2, 5, 6, 7 ]
[ 1, 2, 5, 6, 7 ]
[ 1, 2, 5, 6, 7 ]숫자 하나씩 제자리를 찾는 과정을 확인할 수 있다.
그런데 잘 생각해보니까 2까지 자리를 잘 찾아갔는데 왜 로그가 한 번 더 찍히지? 싶었다.
(로그는 첫 for문에서 찍었으며, 마지막 줄은 함수 실행 결과 로그다.)
이 점을 개선해보았다.
Solution
function insertionSort(arr){
let n = arr.length;
for (let i = 0; i < n-1; i++){
let now = arr[i];
for (let j = i+1; j>=1; j--){
if(arr[j] < now && arr[j] < arr[j-1] ){
let temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
else {break}
}
}
return arr;
}now는 비교의 기준점이 되고 있으므로 마지막 자리 수는 now로 잡을 필요가 없다.
따라서 첫 for문의 조건을 n-1로 잡는다.
