삽입정렬(insertion sort) - 삽입정렬 알고리즘을 설명하기 전 자료를 정렬된 목록과 정렬되지 않은 목록으로 자료를 나눌 필요가 있습니다.
삽입정렬은 배열의 경우 처음 첫 번째 요소를 정렬된 목록으로 간주한 후 루프를 시작합니다.
정렬되지 않은 목록의 제일 첫 번째 요소부터 정렬된 목록과 비교하여 적절한? 위치에 삽입해 나갑니다.
정렬되지 않은 목록 끝까지 위 작업을 반복하면 모든 요소가 정렬된 부분으로 바뀌게 됩니다.
삽입정렬 알고리즘의 아이디어도 어렵지는 않지만 삽입되는 과정을 차근차근 분석할 필요가 있습니다.
위 영상은 이해는 되지만 위 영상만 보고 코드로 작성하려면 먼가 부족하거나 헷갈릴 수가 있습니다. 삽입정렬에 대한 아이디어는 알려주지만, 알고리즘의 세세한 부분이 정확하지 않다는 것을 참고해주시길 바랍니다. 아마 표현하기 힘들기 때문이라 생각되네요.
그럼 그림을 통해 자세히 알아보겠습니다.
노란색 채움-정렬이 된 요소
붉은 테두리 - 비교대상
푸른 화살표 - 복사(대입 or 삽입)
푸른색 채움 - 복사된 상태
정렬의 시작은 가장 첫 번째 요소를 정렬이 된 상태라고 간주합니다. 두번째 요소 39를 임시 변수에 복사해 두고 정렬된 수와 비교해서 내려갑니다. 여기서는 39와 5를 비교하였고 비교 결과 39는 5보다 크므로 더 이상 비교할 필요가 없습니다.
5,39는 정렬된 요소가됩니다.
정렬되지 않은 요소 첫번째 값 2를 임시변수에 저장합니다. 이 임시변수의 값과 정렬된 값을 비교해 내려갑니다.
39와 2를 비교하여 2는 39보다 더 작습니다. 이경우 39를 오른쪽에 복사합니다. 다시 5와 2를 비교하여 2가 더 작으므로 5를 오른쪽에 복사합니다. 2와 비교할 값이 더 이상 없으면 2(임시변수의 값)를 이전 비교대상 자리에 복사합니다.
위 그림도 같은 방법으로 해석하면 됩니다. 한 가지만 살펴보죠. 정렬되지 않은 23의 경우에서 23과 5를 비교할 때 23이 5보다 크므로 더 이상 비교하지 않고 23(임시변수의 값)을 마지막 정렬된 비교 값의 자리에 복사(삽입)합니다.
더 이상 비교할 값이 없는 경우 또는 비교할 정렬된 값보다 큰 경우 이전 정렬된 비교 값이 있었던 자리에 삽입을 하면 됩니다.
이래저래 주저리 주저리 설명을 했는데 정렬되는 순서를 노트에 차근차근 적어보시면 감이 잡히실 겁니다.
코드는 앞서 살펴본 버블정렬과 선택정렬만큼 간단합니다.
while문을 사용한다면 조건에 대한 부분을 이해하기 쉽지만 전 위와 같이 for문으로 하는 것이 더 익숙하네요. for문은 압축의 묘미가 있죠. 삽입정렬은 앞서 살펴본 버블정렬과 선택정렬에 비해서 속도가 빠릅니다.
http://www.sorting-algorithms.com/
위 사이트에서 비교를 해 보면 쉽게 알 수 있습니다. 다음엔 퀵정렬에 대해서 알아보겠습니다.