알고리즘 문제풀이 4

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

/**
 * 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}]
// This function is to help you test, and should not be incorporated in your solution.
// 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이다.