최상의 답변
먼저, 병합 정렬과 같이 점근 적으로 더 빠른 대안이 존재할 때 왜 2 차 정렬 알고리즘을 사용하는지 물어봐야합니다. 또는 퀵 정렬. 작은 배열 (요소 20-30 개 미만)의 경우 삽입 정렬과 선택 정렬이 일반적으로 O (n * logn) 대안보다 빠릅니다. 사실, 분할 및 정복 패러다임을 기반으로하는 많은 정렬 알고리즘은 배열이 충분히 작을 때 삽입 정렬 또는 선택 정렬로 전환합니다.
삽입 정렬과 선택 정렬 중 언제 어떤 것을 사용해야합니까?
보통 삽입 정렬은 배열의 “정렬”정도에 따라 선택 정렬보다 비교를 덜 수행합니다. 선택 정렬은 요소를 배치 할 때 배열의 나머지 부분을 스캔해야하지만 삽입 정렬은 필요한만큼의 요소 만 스캔합니다. 즉, 배열이 이미 정렬되었거나 거의 정렬 된 경우 삽입 정렬이 O (n) 시간 내에 수행됩니다.
삽입 정렬보다 선택 정렬의 한 가지 장점은 쓰기 (스왑) 수가 있다는 것입니다. O (n), 삽입 정렬에서는 O (n ^ 2)에 있습니다. 예를 들어 쓰기가 플래시 메모리의 수명을 단축시키기 때문에 플래시 메모리를 기준으로 정렬하는 경우 중요 할 수 있습니다.
답변
선택 정렬에서 각 요소에 대해 정렬 된 섹션에 추가하려면 목록의 정렬되지 않은 부분을 전체 스캔하여 최소 남은 요소를 찾아야합니다. 삽입 정렬에서는 sorted 섹션을 검색하여 다음 요소가 어디로 가는지 알아 내야하지만 삽입 점을 찾으면 검색이 종료됩니다 (약 절반 평균적으로 정렬 된 섹션을 통과합니다.)
따라서 선택 정렬에는 정렬 된 섹션에 추가 할 각 요소에 대해 평균 N / 2 개의 비교가 필요하고 삽입 정렬에는 평균적으로 N / 4 개의 비교가 필요합니다. 그러나 삽입 정렬에는 배열을 정렬 할 때 추가 시간 패널티가 있습니다. 각 N / 4 (평균) 비교에서는 요소를 위로 이동해야하므로 N / 4 이동 및 비교도 있습니다. 선택 정렬은 단일 스왑 만 필요합니다.
전반적으로 삽입 정렬이 일반적으로 경쟁에서 승리합니다. (배열의 경우) 빠른 “블록 이동”기능이있는 경우 특히 그렇습니다.