[정렬] 삽입 정렬

1. 삽입 정렬이란?

삽입 정렬(Insertion Sort)은 간단하고 직관적인 정렬 알고리즘입니다. 이 알고리즘은 데이터가 거의 정렬된 상태일 때 매우 효율적이며, 작은 데이터셋을 정렬할 때 유용합니다. 삽입 정렬은 리스트를 순차적으로 탐색하면서 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 하나씩 꺼내어 적절한 위치에 삽입하여 정렬된 부분을 확장해 나갑니다. 이러한 방식 덕분에 데이터의 안정성을 유지할 수 있는 안정 정렬(stable sort)입니다.

2. 삽입 정렬 과정

3. 작업 순서

1. 리스트의 첫 번째 요소는 이미 정렬된 것으로 간주합니다.
2. 두 번째 요소부터 시작하여 리스트의 끝까지 순회합니다.
3. 현재 요소를 이전의 정렬된 요소들과 비교하여 알맞은 위치를 찾습니다.
4. 요소를 해당 위치에 삽입하고, 나머지 요소들을 오른쪽으로 이동시킵니다.
5. 리스트의 모든 요소가 정렬될 때까지 이 과정을 반복합니다.

4. 시간 복잡도

• 최선의 경우: (O(n)) - 이미 정렬된 리스트인 경우.
• 평균 및 최악의 경우: (O(n^2)) - 요소들이 역순으로 정렬된 경우.

삽입 정렬은 간단하지만, 큰 데이터셋에 대해서는 비효율적일 수 있습니다. 그러나 데이터가 거의 정렬된 상태라면 효율적으로 작동하며, 공간 복잡도가 (O(1))로 메모리를 적게 사용한다는 장점이 있습니다.

5. 공간 복잡도

삽입 정렬의 공간 복잡도는 (O(1))입니다. 이는 별도의 추가 메모리 공간을 거의 사용하지 않기 때문입니다. 삽입 정렬은 제자리 정렬(in-place sort) 알고리즘으로, 입력 리스트 외에 약간의 추가 저장 공간만 필요합니다. 이 점은 메모리 사용량이 중요한 환경에서 큰 장점으로 작용할 수 있습니다.

6. 코드

아래는 자바(java)로 구현한 삽입 정렬의 예제 코드입니다.

public class InsertionSort {

    // 삽입 정렬 함수
    public static void insertionSort(int[] arr) {
        // 리스트의 두 번째 요소부터 시작
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            // 정렬된 부분의 요소와 비교하여 적절한 위치를 찾음
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    // 메인 함수
    public static void main(String[] args) {
        int[] data = {9, 5, 1, 4, 3};
        insertionSort(data);
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }
}