Insertion

[알고리즘] 삽입 정렬 Insertion Sort (자바/Java)

목차 삽입 정렬 0번째부터 i번째까지 정렬된 배열의 크기를 증가시키며 정렬하는 알고리즘 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열 만들기! 시간 복잡도: $O(n^2)$ 과정 i번째 원소를 정렬할 차례 i-1번째까지의 원소들은 정렬되어 있음 i-1부터 0까지의 원소들과 i번째 원소(key)를 비교하며, i번째 원소보다 작은 원소를 만나면 break, i번째 원소보다 크다면 해당 원소를 오른쪽으로 한 칸씩 shift break한 원소 다음 자리에 i번째 원소를 삽입 1부터 마지막 원소까지 반복 1 0번째 원소는 정렬된 상태 i=1, 10 10..