이번에는 반복 알고리즘 중에 쉘 정렬 알고리즘을 알아봅시다.
쉘 정렬 알고리즘은 삽입 정렬 알고리즘을 이용하는 정렬 방식입니다. 쉘 정렬은 같은 간격에 있는 원소들을 삽입 정렬 원리로 정렬하는 것을 반복합니다. 이 때 간격의 초기값은 배열의 크기/2이며 간격이 1일 때까지 1/2로 줄이면서 반복합니다.
쉘 정렬(base:컬렉션, n:원소 개수, compare:비교 논리)
반복(step:=size/2; step>0 ; step:=step/2)
반복(i:=0; i<step ; i:=i+1)
삽입정렬2(base+i, size-n, step)
삽입정렬2(base:컬렉션, size:원소 개수, step:간견)
반복(i:=step; i<size ; i:= i+step)
반복(j=i; j>0 ; j:=j-step)
조건(compare (base [j-step], base [j]) < 0)
temp: = base [j-step]
base[j-step] = base [j]
base[j] = temp
아니면
루프 탈출
만약 9, 4, 3, 10, 5, 8, 7, 6, 2, 1 원소가 있을 때 정렬하는 과정은 다음과 같습니다.
step:5
8 4 3 10 5 9 7 6 2 1
8 4 3 2 5 9 7 6 10 1
8 4 3 2 1 9 7 6 10 5
step:2
3 4 8 2 1 9 7 6 10 5
3 4 1 2 8 9 7 6 10 5
1 4 3 2 8 9 7 6 10 5
1 4 3 2 7 9 8 6 10 5
1 2 3 4 7 9 8 6 10 5
1 2 3 4 7 6 8 9 10 5
1 2 3 4 7 6 8 5 10 9
1 2 3 4 7 5 8 6 10 9
step:1
1 2 3 4 5 7 8 6 10 9
1 2 3 4 5 7 6 8 10 9
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 9 10