[알고리즘] 삽입정렬

삽입정렬은, 데이터의 전체 영역이 정렬된 부분과, 정렬되지 않은 부분으로 나눠지면서 정렬이 됩니다. 정렬되지 않은 부분중 맨 앞부분의 데이터를 선택한 후, 정렬된 영역에 해당 데이터를 넣었을때 정렬을 유지 할 수 있도록 삽입합니다. 해당 동작을 반복하면 정렬되지 않은 부분이 없어지고, 정렬된 부분이 증가하면서 최종적으로 모든 데이터가 정렬이 됩니다. 정렬의 과정을 정리하면 아래와 같이 나타낼 수 있습니다. 정렬되지 않은 영역의 데이터중 맨 앞에 있는 데이터를 선택하고 Key라고 합니다. 해당 Key를 기준으로 정렬된 영역의 맨 끝 값을 비교 합니다. 맨 끝의 값이 Key보다 크다면, Key보다 뒤에 있어야 하므로 해당 값을 오른쪽으로 한칸 이동 시킵니다. 맨 끝의 값이 Key보다 작다면, Key보다 앞에 있어야 하므로 유지 합니다. 해당 값 바로 앞에 Key를 넣습니다. 정렬된 영역이 늘어나고, 정렬되지 않은 영역이 줄어 들었습니다. 모든 데이터가 정렬된 영역이 될때까지 2~5를 반...

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