삽입정렬

[자료구조][JS] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)이란? 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료와 비교해 삽입할 위치를 결정하는 알고리즘 즉, 두 번째 자료는 첫 번째 자료와, 세 번째 자료는 두 번째와 첫 번째 자료와 비교를 해 삽입될 위치를 찾는다. 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 처음 Key값은 두 번째 자료부터 시작한다. 예시 배열에 3, 7, 2, 5, 1, 4가 있다고 가정하고 자료를 오름차순으로 정렬해보자. 1. key: 7(두 번째 자료). 첫 번째 값인 3과 비교한다. 2. key: 2(세 번째 자료). 두 번째 값인 7과 비교해 7을 한 칸 뒤로 이동한다. 첫 번째 값인 3과 비교하고 3을 한 칸 뒤로 이동한다. 2를 첫 번째 자리에 넣는다..