nomad-programmer

삽입 정렬은 보는 관점에 따라서 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느낄 수 있다. 하지만 전혀 다른 방법으로 정렬을 이뤄나간다. 삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 '삽입'해 가면서 정렬을 진행하는 알고리즘이다. 정렬된 상태로 삽입하기 위해서는 특정 위치를 비워야 하고, 비우기 위해서는 데이터들을 한 칸씩 뒤로 미는 연산을 수행해야 한다. 정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬 대상이다. 삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다. 삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 ..