Insertion Sort

삽입정렬

삽입 정렬(Insertion Sort)은 간단하지만 효율적인 정렬 알고리즘 중 하나입니다.

삽입 정렬은 이름에서 알 수 있듯이 각 숫자를 적절한 위치에 "삽입"함으로써 작동합니다.

이 정렬 방식은 주로 작은 데이터 세트에 대해 사용됩니다.
삽입 정렬은 각 반복에서 하나의 데이터 요소를 선택하고, 이미 정렬된 배열 부분에서 해당 요소가 들어갈 올바른 위치를 찾아 그곳에 요소를 삽입함으로써 동작합니다. 이 과정은 모든 데이터 요소가 처리될 때까지 반복됩니다.

장점

1. 간단하고 이해하기 쉽다.
2. 대부분의 경우에는 불필요한 작업이 적다.
3. 작은 배열 또는 대부분 정렬된 배열에 효율적이다.

단점

1. 배열의 크기가 클수록 성능이 저하된다.
2. 배열의 크기가 클 경우, 다른 정렬 알고리즘(예: 퀵소트, 병합 정렬 등)에 비해 훨씬 비효율적이다.

시간 복잡도

• 최선의 경우 (완전 정렬이 되어있는 상태): O(n)
• 평균 및 최악의 경우: O(n^2)
• 실제 계산
  ${n(n-1) \over 2}$

적합한 상황

1. 작은 데이터 세트를 정렬할 때
2. 이미 대부분 정렬된 배열을 다룰 때

부적합한 상황

1. 매우 큰 데이터 세트를 정렬할 때

삽입 정렬 구현

JS

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

let arr = Array.from({ length: 10 }, () => Math.floor(Math.random() * 10));
const result = insertionSort(arr);

console.log(result);

Python

로직

    do
    
      swapped = false
    
      for i = 1 to indexOfLastUnsortedElement-1
    
        if leftElement > rightElement
    
          swap(leftElement, rightElement)
    
          swapped = true; ++swapCounter
    
    while swapped

구현1

    def insertionSort(data):
        for i in range(0, len(data)-1):
            for j in range(i+1, 0, -1):
                #print('i=', i, 'j=', j, ' j-1=', j-1)
                if data[j-1] > data[j]:
                    data[j], data[j-1] = data[j-1], data[j]
                else:
                    break
        return data
    
    # 테스트
    import random
    data = random.sample(range(100), 100)
    print(data)
    print(insertionSort(data))

구현2

    import random
    data = random.sample(range(100), 50)
    
    for i in range(0, len(data)-1):
        j = i+1
        while j > 0 :
            if data[j-1] > data[j]:
                data[j-1], data[j] = data[j], data[j-1] 
                j=j-1
            else:
                break
            
    print(data)

코드 디버깅 참고: Live Programming Mode - Python Tutor - Visualize Python and JavaScript code