본문 바로가기
Data Structure

삽입 정렬(Insertion sort)의 정의, 작동 방식 및 장단점과 복잡도

by wonderful_mommy 2023. 7. 14.
반응형

삽입 정렬은 요소를 오름차순 또는 내림차순으로 정렬하는 데 사용되는 간단하면서도 효율적인 정렬 알고리즘입니다. 입력 배열을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나누어 작동합니다. 알고리즘은 정렬되지 않은 부분에서 각 요소를 반복적으로 가져와서 정렬된 부분의 올바른 위치에 삽입합니다. 이 글에서는 삽입 정렬의 작동 방식, 시간 및 공간 복잡성, 장단점, 실제 예제, 구현 세부 사항 등에 대해 살펴봅니다.

삽입정렬_프로그래밍_화면

삽입 정렬의 작동 방식

삽입 정렬을 이해하기 위해 기본 개념부터 살펴봅시다. 정렬되지 않은 카드 더미가 있다고 가정해 보겠습니다. 삽입 정렬을 사용하여 카드를 정렬하려면 빈 왼손으로 시작하여 정렬되지 않은 부분(오른손)에서 한 번에 한 장씩 카드를 골라 정렬된 부분(왼손)의 올바른 위치에 삽입하면 됩니다. 모든 카드가 정렬된 순서가 될 때까지 이 과정을 반복합니다.

 

삽입 정렬을 위한 단계별 알고리즘은 다음과 같이 요약할 수 있습니다.

  1. 정렬되지 않은 첫 번째 요소를 가져와 정렬된 부분의 요소와 비교합니다.
  2. 현재 요소에 적합한 위치를 찾을 때까지 정렬된 부분을 오른쪽으로 이동합니다.
  3. 정렬된 부분의 올바른 위치에 요소를 삽입합니다.
  4. 나머지 정렬되지 않은 요소에 대해 1~3단계를 반복합니다.

시간 복잡도

삽입 정렬의 시간 복잡도는 O(n^2)이며, 여기서 n은 정렬되는 배열의 요소 수입니다.

최악의 경우, 입력 배열이 역순인 경우 정렬되지 않은 부분의 각 요소를 비교하여 정렬된 부분의 시작 부분으로 이동해야 합니다. 이 경우 정렬되지 않은 부분의 각 요소에 대해 정렬된 부분을 반복하여 올바른 위치를 찾는 중첩 루프 구조가 생성됩니다. 이로 인해 시간 복잡도는 O(n^2)가 됩니다.

최적의 경우, 입력 배열이 이미 정렬되었거나 거의 정렬된 경우에도 알고리즘이 배열을 반복해야 하지만 요소를 이동할 필요는 없습니다. 이 경우 시간 복잡도가 O(n)으로 감소하여 더 효율적입니다.

삽입 정렬의 평균 시간 복잡도는 O(n^2)입니다. 이는 평균적으로 정렬된 부분에 있는 요소의 약 절반에 대해 각 요소를 비교하고 이동해야 하기 때문입니다.

삽입 정렬은 시간 복잡성이 이차적이므로 입력 배열의 크기가 커지면 성능이 빠르게 저하될 수 있다는 점에 유의할 필요가 있습니다. 대규모 데이터 집합의 경우 병합 정렬 또는 빠른 정렬과 같은 다른 정렬 알고리즘이 평균 및 최악의 경우 시간 복잡성이 더 우수하므로 일반적으로 선호됩니다.

 

공간 복잡도

삽입 정렬의 공간 복잡도는 O(1)이며, 이는 입력 크기에 관계없이 일정한 양의 추가 공간을 사용한다는 의미입니다. 삽입 정렬은 메모리를 크게 추가하지 않고 원래 배열 내의 요소를 재배열하는 방식으로 작동합니다. 제자리에서 정렬을 수행하므로 입력 크기에 비례하여 새로운 데이터 구조나 배열을 생성하지 않습니다. 이 알고리즘은 정렬 프로세스 중에 인덱스와 임시 값을 추적하기 위해 몇 가지 추가 변수만 필요합니다. 입력 배열의 크기에 관계없이 이러한 추가 변수는 고정된 공간을 차지합니다. O(1)의 공간 복잡성 때문에 삽입 정렬은 메모리 사용량이 문제가 되거나 제한된 리소스로 작업할 때 매력적인 선택이 될 수 있습니다. 메모리 요구량을 크게 늘리지 않고도 효율적으로 정렬할 수 있습니다.

 

삽입 정렬의 장점

  • 간단한 구현 : 삽입 정렬은 더 복잡한 정렬 알고리즘에 비해 이해하고 구현하기 쉽습니다. 작은 데이터 집합에 효율적이므로  작은 배열이나 부분적으로 정렬된 데이터 집합에 적합합니다.
  • 제자리 정렬: 삽입 정렬은 입력 배열 외에 추가 메모리가 필요하지 않습니다.

 

삽입 정렬의 단점

  • 대규모 데이터 세트의 비효율성 : 특히 역순 배열의 경우 요소 수가 증가함에 따라 효율성이 떨어집니다.
  • 이차적 시간 복잡성 : 최악의 경우, 삽입 정렬은 이차적 시간 복잡성을 가지므로 대규모 정렬 작업에는 적합하지 않습니다.

 

삽입 정렬의 예시

  • 카드 게임 정렬 : 삽입 정렬은 플레이어가 정렬된 순서를 유지하면서 점차적으로 새로운 카드를 패에 추가하는 카드 게임에서 패를 정렬하는 데 자주 사용됩니다.
  • 온라인 양식 입력 유효성 검사 : 웹 개발에서 양식 입력의 유효성을 검사할 때 삽입 정렬을 활용하여 사용자 입력이 올바른 순서로 정렬되고 표시되는지 확인할 수 있습니다.
  • 음악 재생 목록 재정렬 : 일부 미디어 플레이어는 삽입 정렬을 사용하여 사용자가 원하는 위치에 삽입하여 재생 목록의 노래를 재정렬할 수 있도록 합니다.

다른 정렬 알고리즘과의 비교

  • 삽입 정렬과 선택 정렬 : 두 알고리즘 모두 평균 케이스 시간 복잡도가 O(n^2)입니다. 입력 배열이 부분적으로 정렬되거나 거의 정렬된 경우 삽입 정렬이 선택 정렬보다 더 나은 성능을 발휘합니다. 선택 정렬은 스왑 횟수가 고정되어 있는 반면, 삽입 정렬은 입력에 따라 스왑 횟수가 줄어들거나 늘어납니다.
  • 삽입 정렬과 버블 정렬 비교 : 두 알고리즘의 평균 케이스 시간 복잡도는 O(n^2)입니다. 입력 배열이 부분적으로 정렬되거나 거의 정렬된 경우 삽입 정렬이 버블 정렬보다 더 나은 성능을 발휘합니다. 버블 정렬은 인접한 요소를 비교하고 교환하는 반면, 삽입 정렬은 요소를 비교하고 이동합니다.

 

삽입 정렬 성능의 최적화

  • 이진 검색 사용: 정렬된 부분의 올바른 위치를 선형적으로 검색하는 대신 이진 검색을 구현하여 비교 횟수를 줄일 수 있습니다.
  • 조기 종료: 배열이 이미 정렬된 경우 반복 중에 스왑이 수행되지 않았는지 확인하여 정렬 프로세스를 중지합니다.

 

결론적으로, 삽입 정렬은 배열을 정렬하는 간단하고 효율적인 알고리즘입니다. 특히 작은 데이터셋이나 부분적으로 정렬된 배열에 유용합니다. 그러나 데이터셋이 크면 성능이 저하되므로 이러한 경우에는 적합하지 않습니다. 작동 원리, 시간 및 공간 복잡성, 삽입 정렬의 장단점을 이해하면 특정 요구 사항에 맞는 정렬 알고리즘을 선택할 때 정보에 입각한 결정을 내리는 데 도움이 됩니다.

반응형