Java Script를 공부하고 있는 예비 개발자입니다.
공부한 내용을 토대로 정리하고 있으니,
잘못된 부분이 있으면 알려주시면 감사드리겠습니다.
겸허한 마음으로 배우겠습니다 :)

What I learned Today :)

  😂  삽입 정렬 (Insertion Sort)

삽입 정렬이란
sort 방식의 한 종류로
정렬이 될 대상이
이미 정렬이 된(왼쪽 빨간 박스) 리스트에 있는 곳으로
최측근 왼쪽부터 하나하나 대소비교를 하며 왼쪽으로 이동하면서 자신의 위치를 찾고 그 자리에 삽입이 되는 정렬을 말한다.

장단점

• 장점
  안정한 정렬 방법
  최선의 경우 O(n)이라는 시간복잡도를 만들어 낼 수 있다.
  정렬할 자료들이 적을 수록 유리하다.
  알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
  대부분의 자료들이 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
  성능이 좋아 다른 알고리즘에 사용이 가능하다.
  
  
• 단점
  비교적 많은 자료들을 이동시켜 자료들이 많을 수록 불리하다.
  그래서 최악의 경우 O(n^2)의 시간복잡도가 형성된다.(양에 따라 편차가 심한 편)

자, 그럼 아래 그림으로 어떻게 돌아가는지를 내가 공부하면서 그려본 그림과
구현 코드를 살펴보겠다.

시간 복잡도: O(n^2)

합병 정렬을 할 때 시간 복잡도:
처음에 나는 합병 정렬에 도움을 줄 helper function으로 일반 sort정렬을 코드를 구현 후 재귀를 사용했으나, 이 과정에 재귀 + 이중 for문을 사용했어서 엄청난 최악의 시간복잡도가 형성이 되었던 것 같다. 테스트 케이스가 무지 느리게 돌다 결국 시간초과라는 멘트를 날렸으니 말이다.
(사실 정확한 이유를 모르겠다. 아직 갈 길이 멀군..)
그래서 부트캠프에서 요구한 삽입정렬을 시도해봤다.

부트캠프 said

병합 단계에서 삽입 정렬을 사용하여 구현할 수 있습니다. 
이 경우 시간 복잡도는 훨씬 낮아지게 됩니다.
왜 그런 것일까요? 

본인은 helper function으로 bubble sort 방식을 택해 구현해보려 했지만 시간초과가 발생해 첫번째 시도에 무참히 실패했었다.

그래서 상단 그림으로 정리를 해보면서 삽입정렬에 대한 공부를 해보았으니 그림을 보며 미래의 내가 다시 참고해보길 바란다.

[삽입 정렬(insertion Sort)]

const insertionSort = function (array) {
  for(let i = 1; i < array.length; i++) {
    let temp = array[i];
    let j = i-1;
    
    while(j >= 0 && array[j] > temp) {
      array[j+1] = array[j];
      array[j] = temp;
      j--;
    }
  }
  return array;
}



처음에는 이중 for문을 이용한 재귀 -> 그냥 for문으로  -> while 
위처럼 코드를 계속 엎었다. 
아직도 이해가 안되는건 for문으로 사용했을 때와
위와 같이 while로 사용했을 땐 리팩토링을 했을 뿐 달라진게 없다.

음... 무슨 차이인지 모르겠다. 
시간복잡도 공부를 더 해봐야 할 것 같다. 

하.. 눈물..

추후에 이 삽입정렬을 이용한 합병정렬을 간략하게 적어보겠다.
(정렬 문제를 한 번에 정리하여 비교해보는 것도 나쁘지 않을 것 같군..)