쉘 정렬(Shell sort)
u 삽입 정렬을 간단하게 변형 u 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴 u h-정렬 화일 : 모든 h번째 원소를 정렬한 화일 u 증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1 u 특징 Ø 순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교회수는 N 3/2 을 넘지 않음 Ø 안정적인 제자리 정렬 ShellSort(a[], n) for (h ← 1; h 0; h ← h/3) do { // h 값을 감소시키며 진행 for (i ← h + 1; i ≤ n; i ← i+1) do { v ← a[i]; j ← i; while (j >h and a[j-h] >v) do { a[j] ← a[j-h]; j ← j-h; } // while A[j] ← ..
2007. 4. 3.
