삽입정렬에서 교환을 하는 경우도 삽입정렬이라 할 수 있을까요?
글쓴이: dltkddyd / 작성시간: 금, 2014/01/10 - 6:39오후
삽입정렬을 insertion sorting라고 하더군요. 제가 직접 코드를 짜봤는데, 정렬된 부분을 삽입항목이 있을 때 오른쪽으로 옮기는 것이 번거롭고 더 더딘 것 같아서 swap을 사용했습니다. 코드는 아래와 같고요.
template<typename Iterator>
Iterator sort_by_insertion(Iterator first, Iterator last) {
if(first==last) {return last;}
Iterator next=first;
if(next==last) {return last;}
for(Iterator i=first+1;i!=last;i++) {
for(Iterator j=first;j<i;j++) {
if( *i<*j ) {
swap(*j,*i);//이 부분이 과연 삽입정렬에 해당하는지
}
}
}
return last;
}for로 각 요소를 이동하는 대신에 swap을 썼는데, swap을 사용해도 삽입정렬이라 할 수 있을까요? 직접 요소를 이동해서 삽입을 구현해야 한다고 하더라도 swap을 직접 사용하는 것보다 더 속도가 더딜 것이라 생각합니다. 과연 속도가 정말 더딜까요?
Forums:
삽입 정렬은 맞습니다만 속도는 더 느려질 겁니다.
1. 삽입 정렬은 맞습니다. 내부적으로 swap을 썼느냐는 관계 없이 요소 사이에 삽입을 하는 정렬 방식이 삽입 정렬이니까요.
2. 속도는 swap을 쓰는 경우에 더 느려집니다.
[왼쪽|오른쪽]으로 구분해서 왼쪽에서 오른쪽으로 진행한다고 하면 왼쪽은 반드시 정렬되어있는 상태가 됩니다. 당연하죠?
예를 들어 삽입 정렬중인 다음의 배열이 있다고 칩시다.
[1 2 5 6 7 8|4 3]
이 때 일반적인 삽입 정렬법은 다음과 같이, 삽입 위치 이후를 그냥 복사하는 것입니다.
[1 2 5 6 7 8 4|3] -> tmp = 4
[1 2 5 5 6 7 8|3] -> tmp == 4
[1 2 4 5 6 7 8|3] -> use tmp
왜냐면 삽입하는 위치 이후는 항상 정렬되어있음이 보장되어있기 때문이지요.
그런데 이 때 위처럼 swap을 사용하게 되면 다음과 같이 삽입 정렬이 진행됩니다.
[1 2 5 6 7 8 4|3] -> tmp = 4
[1 2 4 6 7 8 5|3] -> swap 4 and 5
[1 2 4 5 7 8 6|3] -> swap 5 ans 6
[1 2 4 5 6 8 7|3] -> swap 6 ans 7
[1 2 4 5 6 7 8|3] -> swap 7 ans 8
여기서 발생하는 문제는, 5 6 7 8이 정렬되어있음이 항상 보장되어있음에도 불구하고
계속 의미 없는 비교 연산을 하면서 원소를 이동시키고 있다는 점입니다.
그래서 이 쪽의 속도가 더 느려지게 됩니다.
저는 이렇게 생각했습니다.