6장 정렬 알고리즘 - 2

5. 셸 정렬

단순 삽입 정렬의 장점을 살리고 단점을 보완하여 더 빠르게 정렬하는 알고리즘

기존의 문제점

• 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.

개선방법

• 정렬할 배열의 원소를 그룹으로 나눠서 각 그룹별로 정렬을 수행한다.
• 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다.

원리

4- 정렬, 2- 정렬, 1-정렬 즉, 배열 전체에 적용을 시킨다. 이를 h-정렬이라 한다.
배열에서 h만큼 떨어진 원소를 그룹시켜 각 그룹별로 정렬을 수행한다.
h를 4, 2, 1로 감소시키며 정렬을 수행한다.

h값을 효율적으로 선택하는 법

h를 효율적으로 선택해야 각 그룹을 선택할 때 보다 충분히 섞일 수 있다.
그렇기에 h값이 서로 배수가 안되도록 선택해야 한다.
h의 값을 1부터 선택해 3을 곱한값에 1을 더해주는 수열을 사용하는 것도 방법 중 하나이다.
하지만 1, 4, 13, 40... 이렇기에 길이가 9인 배열에서는 그냥 사용하기에 알맞지 않다.
따라서 9로 나눴을 때 몫을 넘지 않도록 정의를 해서 수열을 사용해야 한다.

결론

정렬 횟수는 증가하지만 전체적인 원소의 이동 횟수가 획기적으로 줄어든다.

6. 퀵 정렬

일반적으로 사용되는 빠른 정렬 알고리즘이다. 

원리

피봇이라는 값을 나누는 기준점을 하나 선택 해 피봇을 기준으로 작은값과 큰 값을 나눈다.
이 때, 선택된 피봇은 왼쪽과 오른쪽 아무곳이나 들어가도 상관 없다.
다시 각 그룹에서 피봇을 선택 후 나누며 모든 그룹이 1개가 남을 때 까지 반복수행한다.

스택의 크기
스택의 크기는 정렬 대상인 배열의 원소 수와 같은 값으로 한다.
배열을 스택에 푸쉬하는 순서를 정할 때 2가지 규칙을 고려할 수 있다.

1. 원소 수가 많은 쪽을 우선 푸시
2. 원소 수가 적은 쪽을 우선 푸시

7. 병합 정렬

배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.

원리

배열의 앞부분을 병합정렬로 정렬한다.
배열의 뒷부분을 병합정렬로 정렬한다.
배열의 앞부분과 뒷부분을 병합한다.

결론

병합 정렬 알고리즘은 서로 떨어져 있는 원소를 교환하는 것이 아니라 안정적이다.

8. 힙 정렬

선택 정렬을 응용한 알고리즘이다. 힙은 완전 이진트리의 루트 노드가 최대값인게 특징이다.

원리

i 값을 N-1로 초기화한다.
a[0]과 a[i]를 교환한다.
a[0], a[1] ... a[n-1]을 힙으로 만든다.
i값을 1씩 감소시켜 0이되면 종료한다. 그렇지 않으면 2로 돌아간다.

결론

힙정렬은 선택정렬을 응용한 알고리즘이다. 단순 선택 정렬은 정렬하지 않은 배열에서 최대값을 선택한다. 힙 정렬은 맨 앞언소를 꺼내는 것만으로 최대값을 구할 수 있지만 남은 원소를 힙으로 재구성해야한다.

9. 도수 정렬

원소의 대소관계를 판단하지 않고 빠르게 정렬하는 알고리즘이다.

원리

도수 정렬은 총 4단계로 이뤄져 있다.

1단계 : 도수 분포표 만들기
최소값부터 최대값까지의 배열을 만든다.
그리고 각 값에 맞는 배열에 1을 추가 한다.

2단계 : 누적 도수 분포표 만들기
0점부터 n점까지 총 몇개의 원소가 있는지 누적된 값을 나타내는 누적 도수 분포표를 만든다. 배열의 두번째인 1부터 시작해 바로 앞 배열을 계속 누적합을 한다.

3단계 : 작업용 배열 만들기
처음 있었던 배열과 누적 도수 분포표를 비교해 배열에 적용시킨다.
처음 배열을 arr, 누적 도수 분포표를 f, 작업용 정렬 배열을 ans라고 하자.

n = len(arr)
for i in range(n-1, -1, -1):
    f[arr[i]] -= 1 # 같은 값의 원소를 중복하지 않기 위해 사용
    ans[f[arr[i]]] = arr[i]

4단계 : 배열 복사하기
정렬이 완성된 ans를 arr에 복사하면 정렬이 완료된다.

결론

도수 정렬 알고리즘은 데이터 비교, 교환작업이 필요 없어 매우 빠르다. 단일 for문만을 사용하며 재귀 호출이나 이중 if문이 없어 매우 효율적이다. 하지만, 도수 분포표가 필요하므로 데이터의 최소값과 최대값을 미리 알고있는 경우에만 적용할 수 있다.

참고) Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편