삽입정렬

Insertion Sort

삽입 정렬은 가장 간단한 정렬 방식이며 이미 순화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬합니다.

 

정렬 과정

• 배열의 첫 번째 요소는 이미 정렬된 부분으로 간주합니다.
• 두 번째 요소부터 시작하여 배열의 끝까지 순회합니다.
• 각 요소마다 현재 요소를 key에 저장하고, 이전 위치의 요소들과 비교하며 적절한 위치를 찾게 됩니다.
• key보다 큰 요소들을 오른쪽으로 한 칸씩 이동시키면서 삽입할 위치를 찾게 됩니다.
• key를 적절한 위치에 삽이하여 정렬된 부분을 확장 시킵니다.

 

삽입 정렬 코드

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
 // key보다 큰 원소들을 오른쪽으로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
   // key의 적절한 위치에 삽입
            arr[j + 1] = key;
        }
    }
}

 

시간 복잡도

이미 정렬된 배열을 정렬하게 될 때의 시간 복잡도는 O(n)입니다.

평균 및 최악의 경우 시간 복잡도는 O(n^2)입니다.