[정렬] 삽입 정렬 : Insert Sort

 

📌 삽입 정렬 : Insert Sort

✅ 배열의 요소를 하나씩 순회하며, 현재 요소를 적절한 위치에 삽입

✅ 시간 복잡도 : O(\(n^2\))  ~ O(\(n\))

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        insertSort(arr);
        System.out.println("결과 : " + Arrays.toString(arr));
    }

    public static void insertSort(int[] arr){
        int n = arr.length;

        for(int i = 0; i < n - 1; i++){
            int j = i;
            while(arr[j] > arr[j + 1]){
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                j--; //교환이 일어나면, 크기를 줄여 이전요소로 이동하여 비교를 계속
            }
        }
    }
}

 

 

---

01

- 항상 왼쪽에 있는 숫자는 정렬이 되어있다고 가정, 본인이 왼쪽에 있는 숫자보다 크다면 멈춘다.

- 만약 데이터가 '거의 정렬된' 상태라면 삽입 정렬은 필요한 때에 한해서만 삽입을 진행하기 때문에  빠르다.