15. 정렬(Sort) - 삽입정렬(Insert Sort)

1. Insert Sort 개념

리스트의 앞에서부터 이미 정렬된 서브 리스트의 값들과 비교하여 자신의 위치에 값을 삽입한다.

단순한 알고리즘

시간복잡도 O(n^2)

안정 정렬

데이터의 이동이 많음

---

2. Insert Sort 구현 - JAVA

package sort;

public class InsertionSort implements ISort {
    @Override
    public void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];   // 삽입 위치를 찾아줄 데이터
            int j = i - 1;  // 0-j 정렬된 서브 리스트
            while (j >= 0 && arr[j] > key) {
                // key 값보다 정렬된 배열에 가장 오른쪽에 있는 값이 크면
                arr[j + 1] = arr[j];    // 데이터를 한칸씩 오른 쪽으로 이동
                j = j - 1; // 역순으로 값 비교
            }
            arr[j + 1] = key; //key 값이 배열의 값보다 작아지는 순간 반복이 종료되고 key값을 삽입
        }
    }
}

---

3. Insert Sort 구현 - Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


if __name__ == "__main__":
    arr = [9,1,6,3,7,2,8,4,5,0]
    insertion_sort(arr)
    print(arr)