[알고리즘] 삽입 정렬에 관하여

• 가장 원시적인 방법중의 하나다
• 선택 정렬 보다 효율적이나 그래도 알고리즘 문제에 사용하기에는 느리다
• 적절한 위치에 삽입한다는 의미다

코드 (자바스크립트)

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    for (let j = i; j >= 0; j--) {
      if (array[j] < array[j-1]) {
        [array[j], array[j-1]] = [array[j-1], array[j]];
      }
    }
  } 

  return array;
}

 

시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N²) 이다
• 최선의 경우 (데이터가 거의 정렬된 상태) O(N)의 시간 복잡도를 가진다
  • 이때는 퀵 정렬보다 강력하다
  • 거의 정렬된 상태로 입력이 주어지는 문제라면 삽입 정렬이 더 효율적이다

설명

1. 삽입 정렬은 두 번째 데이터부터 시작한다
   • 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문
2. 두번째 데이터가 어떤 위치로 들어갈지 판단한다
3. 새번째 데이터가 어떤 위치로 들어갈지 판단한다
4. 모든 데이터가 정렬 될때까지 반복한다

 

참고

1. 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈: https://books.google.ca/books?id=vBz-DwAAQBAJ&source=gbs_book_other_versions 
2. 삽입 정렬 -  실전 알고리즘 강좌, 나동빈: https://www.youtube.com/watch?v=16I9Z7bS1iM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=4