삽입 정렬(Insertion Sort)

삽입 정렬이란?

삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하면서 앞의 원소가 크다면 해당 원소를 뒤로 옮기고, 크지 않다면 해당 위치의 다음 인덱스에 비교를 시작한 원소를 삽입하여 정렬하는 알고리즘입니다.

 

삽입 정렬의 기본 동작은 다음과 같습니다.

 1. 정렬을 시작할 때, 첫 번째 요소는 이미 정렬된 상태로 간주합니다.

 2. 두 번째 요소부터 시작하여 삽입하고자 하는 요소를 이전에 정렬된 부분 리스트와 비교합니다.

 3. 삽입하고자 하는 원소보다 작은 원소를 만날 때까지 계속해서 비교하며, 작은 원소를 만나면 그 원소의 다음 위치에 비교를

    시작한 원소를 삽입합니다.

 4. 이 과정을 리스트의 끝까지 반복합니다.

 

삽입 정렬의 특징

1. stable 정렬: 동일한 값의 원소들 간에는 순서가 유지되므로 안정 정렬입니다.

2. in-place 정렬: 자료 구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬합니다.

3. 시간복잡도: 평균, 최악의 경우는 O(N^2)의 시간 복잡도를 갖습니다.

하지만, 이미 정렬된 배열이 주어지는 최선의 경우에는 O(N)의 시간 복잡도를 갖습니다.

아래의 구현 코드를 보면 j번째 원소가 비교를 시작한 원소보다 큰 경우에만 반복을 진행하고 있습니다.

따라서 배열이 이미 오름차순으로 정렬되어있다면 내부의 while 반복문은 실행되지 않고, 외부의 for 반복문을 통해 O(N)의

시간복잡도 만으로 정렬을 확인할 수 있게 됩니다.

 

삽입 정렬의 구현(Java)