정리 노트

삽입 정렬 정렬을 하다 보면 배열 안의 데이터들을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 삽입 정렬은 정렬되지 않은 데이터들 중 가장 앞의 데이터를 정렬된 부분에서의 자기 위치를 찾아 정렬하는 방법입니다. 정렬 과정 길이가 6인 정수형 배열({3, 1, 4, 4, 6, 5})을 정렬해봅시다. 먼저 3을 정렬하려면 정렬된 부분과의 대소 비교를 통해 자기 위치를 찾아야 합니다. 하지만 지금은 정렬 시작 단계이기 때문에 정렬된 부분이 없습니다. 따라서 실질적인 삽입 정렬의 시작은 두 번째 원소인 '1'에서부터 시작하고 3은 정렬된 부분으로 포함시킵니다. 정렬되지 않은 원소들 중 가장 앞인 '1' 원소의 위치를 찾기 위해 정렬된 부분의 '3'과 비교합니다. 1이 3보다 작으므로 3과 1의 위치..