삽입 정렬 알고리즘(Insertion Sort Algorithm)

 삽입 정렬 알고리즘은 선택 정렬 알고리즘과 비슷한 평상시에 많이 볼 수 있는 쉬운 알고리즘입니다.

 삽입 정렬 알고리즘은 데이터를 순차적으로 정렬하면서 현재 값을 정렬되어 있는 값들과 비교해 적합한 위치로 삽입하는 방식의 알고리즘입니다.

다음은 삽입 정렬의 소스코드와 출력 결과입니다.

*나머지 소스코드는 선택 정렬 알고리즘 소스코드와 같습니다.

SelectionSort에서 InsertionSort로 변경한 것입니다.

 삽입 정렬 알고리즘의 성능을 시간복잡도로 표기했을 때 O(N^2)로 표기할 수 있습니다. 선택 정렬 알고리즘의 경우에도 이와 방식이 같으므로 알고리즘의 성능은 서로 큰 차이가 없습니다.

 그런데 삽입 알고리즘은 데이터의 정렬 상태가 최선인 경우와 최악인 경우에 따라 성능이 좋거나 나빠집니다. 데이터의 정렬 상태가 최선일 때는 데이터를 뽑아서 삽입하는 과정이 필요없으므로 선택 정렬 알고리즘과 비교했을 때 월등히 좋은 성능을 보여줍니다. 처리할 데이터의 수와 비교 횟수가 같기 때문입니다. 그러나 선택 정렬 알고리즘은 데이터가 정렬이 되어 있더라도 똑같이 비교를 하기 때문에 상대적으로 성능이 떨어질 수밖에 없습니다.

 최악의 경우인 데이터가 정렬되지 않았을 때는 선택 정렬 알고리즘보다 삽입 정렬 알고리즘의 성능이 더 좋지 않습니다. 삽입 정렬 알고리즘의 데이터 비교 횟수는 N * (N-1) / 2이고, 데이터의 이동 횟수도 동일합니다. 선택 정렬 알고리즘의 비교 횟수는 N * N / 2이고, 이동 횟수는 N이라는 것과 비교하면 성능을 감소시키는 요인이 될 수 있습니다.

 데이터를 정렬할 때 무조건 하나의 알고리즘으로만 정렬하는 것은 옳지 않습니다. 데이터를 정렬할 여러 가지 조건(데이터의 개수, 사용할 수 있는 메모리의 양 등)을 분석해서 가장 합당한 정렬 알고리즘을 선택할 수 있어야 합니다.