# 알고리즘 문제풀이 4

hyunju-song·2020년 10월 4일
0

## ALGORITHM

목록 보기
4/14

삽입정렬과 관련된 알고리즘 문제
보통 이런 문제들은 그 유형을 외워두는것도 나쁘지 않은 것 같다.

/**
* Insertion sort is a basic sorting algorithm.
*
* Insertion sort iterates over an array, growing a sorted array behind the current location.
* It takes each element from the input and finds the spot, up to the current point,
* where that element belongs. It does this until it gets to the end of the array.
*
* Insertion sort should be implemented as a stable sort. This means that equal elements
* should retain their relative order. Numbers, as primitives, give us no way to check this,
* so we'll be sorting objects with a value field, on which they will be sorted, like so:
*
* [{value: 10}, {value: 5, order: 1}, {value: 5, order: 2}]
*
* A stable sort must return {value: 5, order: 1}, {value:5, order: 2} in that order.
*
* ---
*
* EXTRA CREDIT:
*
* Refactor your sort to (optionally) take an explicit comparator function
* as its second argument, so that callers can define arbitrary ways to sort elements.
* See [Array.prototype.sort](http://devdocs.io/javascript/global_objects/array/sort)
* for an example of how this works (excerpt below):
*
* > If comparator(a, b) is less than 0, sort a to a lower index than b, i.e. a comes first.
* > If comparator(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements.
* > If comparator(a, b) is greater than 0, sort b to a lower index than a.
*
* If no comparator is given, just sort the elements using < or >.
**/

// Example usage:
// insertionSort([{value: 2}, {value: 1}, {value: 3}]);
// yields [{value: 1}, {value: 2}, {value: 3}]
// It will transform an array of numbers into an array of valid objects.
var testingTransform = function(array) {
var transform = [];

for (var i = 0; i < array.length; i++)
transform.push({ value: array[i], i: i });

return transform;
};

처음 풀었던 알고리즘 방식이다.
버블정렬과 유사하게 풀이를 했다. 하지만 과연 삽입정렬의 개념에 맞는
알고리즘 코드일까에 대해서 고민을 해보아야 했다.

var insertionSort = function(array) {
//array = testingTransform(array)
//새로운 배열을 한바퀴 돌기
//여기서 for문을 두 번 도는 이유는 :
//첫번째 반복문은 어떻게 보면 배열의 길이 만큼 앞의 수와 뒤의 수의 크기 비교 후 자리변경하는 걸
//반복하겠다는 의미인 것 같다.
for(let i=0; i<array.length; i++){
for(let j=0; j<array.length-1; j++){
if(array[j].value > array[j+1].value) {
//즉 배열에서 앞의 값이 뒤의 값보다 크면, 앞의 값과 뒤의 값의 자리를 바꿔줘야 한다.
let front = array[j];
array[j] = array[j+1];
array[j+1] = front;
}
}
}
return array;
};

삽입정렬에 대한 설명 참고 링크

가령, 버블 정렬은 버블처럼 볼록볼록한 모양을 띄면서, 각 요소들이
뒤로 간다. 하지만 삽입 정렬은 0번째 인덱스에서 자기 이전 인덱스 값까지의 수들과 역순으로 비교해서(즉 이전 인덱스부터 0번째 인덱스까지)
크기 비교를 해서 자기 자리를 찾아서 "삽입"된다는 개념이다.

그렇다면 같은 문제를 푼 동기분의 코드는 어떨까?

var insertionSort = function (array) {
// Your code goes here. Feel free to add helper functions if needed.

for (let i = 1; i < array.length; i++) {
//전체적인 배열을 돌면서 (ex) i=4
//여기서 i가 1부터 도는 이유는, 삽입정렬은 자기 앞의 요소들과 비교를 하는데,
//0번째 인덱스는 앞에 요소가 없어서 비교할 대상이 없기 때문.
let re_idx = i;
//(ex)re_idx = 4
//여기서 만약에 인덱스를 재선언 안해주면, 아래에서 재순환할때 i 인덱스가 꼬여버린다.
for (let j = i - 1; j >= 0; j--) {
//현재 위치한 인덱스의 요소 이전부터 0번째 인덱스까지 역순으로 순회한다.
//(ex) j = 3
if (array[j] > array[re_idx]) {
//현재 위치한 인덱스의 요소보다 앞의 요소가 더 크면
let compare_ele = array[re_idx];
//비교하고자 하는 요소를 따로 선언해준다.
array[re_idx] = array[j];
//그리고 앞의 요소를 현재위치로 옮겨와준다.
array[j] = compare_ele;
//그리고 그 앞의 자리에 비교하고자 하는 요소를 넣어준다.
re_idx = j;
//만약에 인덱스 번호를 재정의 안해주면, re_idx는 계속 i(즉, 4이고)
//그러면 compare_ele은 결국 뒤로 옮겨준 기존 비교 요소보다 더 큰 요소가 되어버린다.
//따라서 재정의 해줘야한다.
}
}
}
return array;
};

### 삽입정렬의 시간복잡도 및 효율성

요소가 적을 경우, 코드도 이해하기 쉽고 효율적인 측면에서도 좋다.
하지만 요소가 많을 경우, 버블정렬처럼 요소의 이동이 많아서 비효율적이다.
삽입정렬 또한 시간 복잡도는 최악의 경우 n^2이다.

코드 한 줄로, 세상의 가치를 만들자🌟