[자료구조/알고리즘] 삽입정렬(insertion sort)

삽입정렬

- 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입함

- 시간 복잡도:O(n^2)

- 배열의 두 번째 데이터 부터 연산을 시작함

정렬방법

- 두번째 인덱스 부터 시작( 해당 인덱스를 키값으로 지정)

- 키값 왼쪽에 위치한 배열은 정렬 된 상태(처음엔 정렬되어 있다고 가정 : 배열의 크기가 1이므로)

- 정렬된 배열의 값이 키값보다 크면 위치를 교환한다

- 정렬된 배열의 값이 키값보다 작으면 교환을 중지한다

(정렬된 배열중 자기자신 보다 작은 값 뒤 큰 값 앞에 위치)

- 키값으로 지정되었던 인덱스 까지 정렬되었으므로 다음 인덱스를 다시 키값으로 지정하고 반복

ex) 사진 예시

[1회전]

[2회전]

[3회전]

[4회전]

Java로 구현한 삽입정렬