단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘이다.
단순 삽입 정렬의 문제
[1, 2, 3, 4, 5, 0, 6]두 번째 원소부터 주목하여 2, 3, 4, 5를 순서대로 선택하여 정렬한다. 여기까지는 이미 정렬을 마친 상태이므로 원소의 이동(값의 대입)은 발생하지 않는다.
이 단계까지는 아주 빠르게 완료한다. 그러나 원소 0을 삽입하려면 총 6번에 걸쳐 원소를 이동(대입)해야 한다.
단순 삽입 정렬의 특징
- 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다.
- 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.
셸 정렬 알아보기
셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄이는 방법이다.
뭔 개소린가
배열의 길이가 8일 때
[8, 1, 4, 2, 7, 6, 3, 5](8, 7), (1, 6), (4, 3), (2, 5) 서로 4칸씩 떨어진 원소를 꺼내어 그룹별로 각각 정렬한다. (꼭 4가 아니라 배열 길이를 2로 나눈값을 이용해서 그룹으로 묶으면 된다.)
정렬하면 이렇게 된다. (7, 8), (1, 6), (3, 4), (2, 5) 이처럼 서로 4칸 떨어진 원소를 정렬하는 방법을 4-정렬이라고 한다.
아직 정렬을 마치진 않았지만 정렬을 거의 마친 상태에 가까워진다고 한다.
이어서
정렬을 마친 상태의 배열에서 2칸 떨어진 원소를 모두 꺼내 두 그룹으로 나눈다. (7, 3, 8, 4), 1, 2, 5, 6 정렬을 마치고 나면 이렇게 된다. (2-정렬)
(3, 4, 7, 8), (1, 2, 5 ,6) 이렇게 해서 얻은 배열은 좀 더 정렬된 상태에 가까워진다. 마지막으로 1-정렬을 적용하여 1칸 떨어진 배열, 즉 배열 전체에 적용하면 정렬이 완료된다.
배열을 바로 단순 삽입 정렬하지 않고 4-정렬과 2-정렬을 먼저 수행하여 정렬을 거의 마친 상태로 만든다. 그리고 마지막으로 단순 삽입 정렬을 한 번 수행하여 정렬을 완료하는 것이다.
단순 삽입 정렬과 수행 과정에서 다른 점이 있다면, 주목하는 원소와 비교하는 원소가 서로 이웃하지 않고 h개 만큼 떨어져 있다.
보완된 셸 정렬
[8, 1, 4, 2, 7, 6, 3, 5][8, 7]
[1, 6]
[4, 3]
[2, 5]4개 그룹으로 나누어 정렬한다.
[7, 3, 8, 4]
[1, 2, 6, 5]정렬된 배열을 2개 구룹으로 나누어 다시 정렬한다.
((8, 7), (4, 3)), ((1, 6), (2, 5))가 섞이지 않는다. 그런데 이렇게 두 그룹이 섞이지 않은 상태에서 합치면 다시 처음 단계와 같아진다.
애써 그룹으로 나누어서 정렬하고 충분히 그 기능을 하지 못한다는 것을 보여준다.
해결하려면
h값이 서로 배수가 되지 않도록 해야 한다. 그러면 원소가 충분히 뒤섞이므로 효율 좋은 정렬을 기대할 수 있다. 다음과 같은 수열을 사용하면 된다.
h = ... -> 121 -> 40 -> 13 -> 4 -> 1
이 수열을 거꾸로 살펴보면 1부터 시작해서 3배한 값에 1을 더하고 있다. 하지만 h의 초깃값이 지나치게 크면 효과가 없다. 따라서 배열의 원소 수인 n을 9로 나누었을 때 그 몫을 넘지 않도록 정해야 된다.
n = len(a)
h = 1
while h < n // 9:
h = h * 3 + 1
while h > 0:
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 3똑같다.
- 왼쪽에 있는 값이 더 크면 오른쪽으로 넣기
- tmp가 들어갈 빈 자리 확보 (오른쪽에 넣은 데이터와 겹치는 데이터)
- 빈 자리에 tmp 넣기
셸 정렬의 시간 복잡도는 O(n^1.25)이고 단순 정렬의 시간 복잡도인 O(n^2)보다 매우 빠르다.
셸 정렬 알고리즘은 이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않다.
