[C언어 알고리즘] 2.6 쉘 정렬(Shell Sort) 알고리즘

[C언어 알고리즘] 2.6 쉘 정렬(Shell Sort) 알고리즘

---

이번에는 반복 알고리즘 중에 쉘 정렬 알고리즘을 알아봅시다.

 

쉘 정렬 알고리즘은 삽입 정렬 알고리즘을 이용하는 정렬 방식입니다. 쉘 정렬은 같은 간격에 있는 원소들을 삽입 정렬 원리로 정렬하는 것을 반복합니다. 이 때 간격의 초기값은 배열의 크기/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

 

---

[C언어 알고리즘] 2.6.1 쉘 정렬 알고리즘 성능 분석

[C언어 알고리즘] 2.6.2 쉘 정렬 알고리즘 구현

[C언어 알고리즘] 2.6.3 쉘 정렬 알고리즘 소스 코드