쉘 정렬(Shell Sort)
삽입 정렬의 단점을 보완한 정렬 방식. 삽입 정렬의 단점??? 삽입 정렬은 한칸씩 이동하면서 비교하기 때문에 만일 가장 멀리 떨어진 곳에서 비교가 이루어진다면 이동 시 많은 오버헤드가 발생할 수 있다. 그 단점을 보완하기 위해 만들어진 방식!! 그림과 함께 살펴보도록 하자 1. 주어진 배열에 대해 반으로 쪼갠 후, 쪼갠 블록을 각 쌍으로 삽입 정렬을 시행한다. 예를 들면 {3,2}, {8,1}, {0,4} 가 쌍으로 삽입 정렬이 실행되고 결과는 {2,3}, {1,8}, {0,4} 로 나타날 것이다. 2. 삽입 정렬이 완료된 블록에 대해 다시 반으로 쪼갠 후, 쪼갠 블록의 각 index를 다시 삽입 정렬로 정렬한다. {2,1,3,8}, {0,4} => {1,2,3,8}, {0,4} 3. 결과에 대해 다시 ..
2013. 6. 24.