삽입 정렬

삽입 정렬(Insertion Sort)은 배열의 모든 요소를 하나씩 비교하면서, 비어있는 배열에 하나씩 옮기는 방식의 알고리즘 입니다. 일반적으로 선택 정렬과 버블 정렬보다 빠른 알고리즘 중 하나로 분류됩니다.

삽입 정렬은 배열을 두 부분으로 나누어 처리합니다. 하나는 정렬된 부분(sorted)이고, 다른 하나는 정렬되지 않은 부분(unsorted)입니다. 정렬되지 않은 부분에서 하나의 숫자를 선택하여 정렬된 부분의 적절한 위치에 삽입합니다. 이 과정을 반복하면서 정렬을 완성합니다.

시간 복잡도는 최선의 경우 O(n), 평균과 최악의 경우 O(n^2)입니다. 하지만 데이터가 이미 정렬된 경우나 데이터의 양이 적을 경우에는 다른 정렬 알고리즘보다 빠른 속도를 보입니다.

삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다.

삽입정렬 알고리즘의 구체적인 개념

• 첫 번째 원소는 이미 정렬된 것으로 볼 수 있기 때문에 두 번째 원소부터 시작합니다. 두 번째 원소는 첫 번째 원소와 비교하여 첫 번째 원소보다 작으면 위치를 바꿔줍니다. 그리고 세 번째 원소는 첫 번째와 두 번째 원소와 비교하면서 자신보다 적은 수를 만날 때까지 비교하고, 삽입할 위치를 찾아 해당 위치에 삽입합니다. 이런 방법으로 리스트의 마지막 원소까지 비교하면서 적절한 위치를 찾아 삽입하면 정렬이 완료됩니다.

• 위 이미지에서 처음에는 배열의 첫 번째 원소가 정렬된 상태입니다. 그리고 두 번째 원소부터 시작하여 적절한 위치를 찾아 정렬되는 과정을 보여줍니다. 이러한 방식으로 마지막 원소까지 정렬하면 최종적으로 오름차순으로 정렬된 배열을 얻을 수 있습니다.
• 삽입 정렬은 버블 정렬이나 선택 정렬과 같은 O(n^2)의 시간 복잡도를 가지지만, 일반적인 상황에서 다른 더 복잡한 정렬 알고리즘들과 경쟁할 만큼 빠르고, 데이터가 이미 정렬되어 있는 경우 더욱 빠르게 수행됩니다.

Insertion sort with Python