[Java] 정렬 알고리즘 (3) - 삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)

---

1. 앞의 원소들이 이미 정렬이 되어 있다고 가정한다.

2. 특정 원소에서 앞의 원소들을 살펴보며 적당한 위치를 찾는 것

3. 시간 복잡도 : O(𝑁²)

4. 선택 정렬, 버블정렬보다 효율적인 알고리즘

→ 필요 시에 바꾸기 연산을 수행하기 때문. 특히 이미 정렬이 되어 있을 경우에는최고의 효율을 보여준다.

import java.util.Arrays;

public class InsertSort {
    int[] array = new int[]{10, 2, 5, 8, 12, 73};

    public void sort() {
        int j, temp;

        for (int i = 0; i < array.length - 1; i++) {
            j = i;
            while (j >= 0 && array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                j--;
            }
        }

        System.out.println(Arrays.toString(array));
    }
}