[알고리즘] 삽입 정렬 (Java)

삽입 정렬 정렬 알고리즘의 한 종류인 삽입 정렬입니다. 주어진 리스트 중 앞에서부터 정렬된 부분을 비교하여 적절한 위치에 넣습니다.

앞서 설명한 선택 정렬이나 버블 정렬이 무조건 위치를 교체하였다면 삽입 정렬은 필요시에만 교체합니다. 삽입 정렬의 시간 복잡도는 O(n^2)입니다.

시간 복잡도는 선택 정렬이나 버블 정렬과 동일하지만 정렬이 어느 정도 되어 있을 때는 굉장히 빠른 속도를 자랑합니다. 다음 숫자 리스트를 오름차순 선택 정렬을 하려고 합니다.

Index 0 1 2 3 4 5 6 7 8 Value 9 1 6 2 4 8 3 5 7 먼저 index 1에서 하위 index를 비교하여 제값을 찾아갑니다. 여기선 index 0보다 작으므로 교체합니다.

Index 0 1 2 3 4 5 6 7 8 Value 1 9 6 2 4 8 3 5 7 다음 index 2에서 하위 index를 비교하여 제값을 찾아갑니다. 여기선 index 1보다 작고 index 0보단 크므로 사이로 들어갑니다.

Ind...

원문링크 : [알고리즘] 삽입 정렬 (Java)