Javascript 코드로 보는 알고리즘 선택 정렬(insertion sort) 학습하기

Insertion Sort 살펴보기

요약

• 앞에서부터 순서대로 자기 위치를 찾아 값을 삽입하여 정렬하는 알고리즘
• 정렬했던 모든 값들과의 비교가 정렬이 끝날때까지 반복된다.
• 시간 복잡도
  - 최고의 경우 O(n) -> 비교 해보는 로직만 돌고 교환하지 않은 경우
  - 최악의 경우 O(n²) -> 모든 값들의 위치를 변경하는 작업을 하는 경우

삽입 정렬은 아래의 gif를 참조하면 좋습니다.

정렬할 값들을 앞쪽의 값들과 전부 비교하면서 자신의 위치를 찾아 삽입하는 작업이 이루어집니다.

그럼 코드를 보러 가볼까요?

설명보다는 먼저 코드를 직접 한번 돌려보세요! 삽입 정렬이 무엇인지 이해하기가 빠르실거에요!

그럼 코드 설명에 들어가보겠습니다!

우선은 4번째 줄 부터 보도록 하겠습니다.
여기서는 정렬을 하려는 배열 전체를 한번만 loop하는 것입니다.
보시면은 mainIndex 가 1부터 시작하는데 그것은 0부터 시작할 필요가 없기 때문입니다. 0부터 시작을 하면 앞쪽에 위치한 다른 값이 없으니 비교 작업을 진행할 필요가 없으니까요.

다음은 12번째 줄을 보시면 정렬 대상값(targetValue)와 앞쪽에 있는 값들과 비교를 하는데 만약에 앞의 정렬 대상값과 같거나 크다면 자리를 바꿔줄필요가 없으니 더 앞쪽에 있는 값과의 비교로 넘어갑니다. (31번째 줄에서는 정렬 대상값보다 작은 경우이고 같은 일이 일어납니다.)

16~24번째 줄을 보시면 여기서 교환 작업이 일어나는 것을 알 수 있습니다!
16번째 줄은 앞쪽에 있던 값을 한칸 앞으로 당기는 것이고 그 이후에 원래 있던 값에 정렬 대상값을 넣어줘서 한칸 씩 앞으로 옮기는 것입니다.

직접 실행해본 코드

참고 문서

- https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html
- https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/insertion-sort
- https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif