삽입 정렬(Insertion Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

삽입 정렬(Insertion Sort)

• 정렬되어 있지 않은 부분의 왼쪽 끝에서 삽입할 원소를 찾아서 정렬되어 있는 부분의 적절한 위치에 삽입
• 정렬 안 된 부분의 숫자 하나가 정렬된 부분에 삽입됨으로써, 정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어든다.
• 이를 반복하면 결국 정렬 안 된 부분에는 아무 원소도 남지 않고 정렬된 부분에 모든 원소가 존재
• 정렬 방법
  • 정렬되어 있지 않은 부분의 왼쪽에서 삽입할 원소 k 선택
  • 빈자리 확보를 위해 k를 꺼내서 임시 장소에 보관
  • 정렬되어 있는 부분에서 k보다 큰 원소들을 오른쪽으로 이동하여 k가 들어갈 빈자리 확보
  • 확보된 빈자리에 k삽입
  • 모든 원소들이 정렬될 때 까지 반복
• 안정된 정렬 방법
• 많은 이동 횟수(레코드가 클 경우 불리하다)
• 이미 정렬이 어느정도 되어 있으면 효율적
• 시간 복잡도
  • 최상의 경우(이미 정렬되어 있는 경우)
    • 비교 : n-1번
    • 이동 : 2(n-1)번
  • 최악의 경우(역순으로 정렬되어 있는 경우 모든 단계에서 앞에 놓은 자료 전부 이동)
    • 비교 : n(n-1) / 2
    • 이동 : n(n-1) / 2 + 2(n-1)

삽입 정렬 예제 코드

• InsertionSort.java

public class InsertionSort {
    public static void main(String[] args) {
        int [] arr = {5,2,8,3,1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    static void insertSort(int[] arr) {
        for(int i = 1; i<arr.length; i++) {
            // 선택한 값
            int temp = arr[i];
            // 선택한 값의 이전 원소의 인덱스 번호 저장
            int index = i - 1;
            // 현재 값이 이전 원소보다 작으면 큰 값은 뒤로 이동
            while (index >= 0 && temp < arr[index]) {
                // 이전 원소를 한 칸씩 뒤로 이동
                arr[index+1] = arr[index];
                index--;
            }
            arr[index+1] = temp;
        }
    }
}