5주차 - 정렬2

정렬

고급 정렬 알고리즘

종류

• 평균적으로 \(θ(nlog^n)\)의 시간이 소요됨

• 병합정렬
• 퀵정렬
• 힙정렬

병합 정렬

• 배열을 절반으로 나눔
• 각 배열별로 재귀함수를 이용해 정렬 한 후, 병합함
• 수행시간: \(θ(n log^n)\)

퀵 정렬

• 평균적으로 효율적인 성능을 가짐
• 리스트 내의 하나의 원소를 선택하고, 그 값을 기반으로 값을 양쪽으로 재배치함
  • 주의점: 기준 원소를 잘못 선택할 경우, 수행 시간이 \(θ(n^2)\)으로 증가할 수 있음
• 재배치를 한 이후, 기준 원소의 왼쪽과 오른쪽을 독립적으로 정렬함

종류

1. Hoare 방식 알고리즘

• 배열의 시작에서 시작하는 포인터 i와 배열의 끝에서 시작하는 포인터 j가 있음
• 왼쪽 포인터는 기준값보다 큰 값을 찾을때까지 오른쪽으로 이동하며, 오른쪽 포인터는 기준값보다 작은 포인터를 찾을때까지 왼쪽으로 이동함
• 포인터가 멈추는 경우, 두 값의 위치를 서로 바꾸며, 포인터가 교차할때까지 위 과정을 반복함

2. Lomuto 방식 알고리즘

• Hoare 알고리즘과 다르게, i와 j가 왼쪽에서 오른쪽 방향으로 증가함
• i값은 기준값보다 클 경우 움직이지 않으며, 기준값보다 작으면, i값을 증가 후 i와 j의 값을 교환함

관련 용어

분할(파티션)

• 자료를 기준점 x를 중심으로 2개로 나누는 것

정복

• 2개의 배열을 재귀적으로 정렬하는 것

합병

• 아무것도 하지 않는 것

머지 정렬과의 차이점

• 머지 정렬은 병합과정이 존재하지만, 퀵정렬은 병합 과정이 존재하지 않음

힙 정렬

• 배열을 힙으로 만든 다음, 배열의 루트 노드와 마지막 노드의 교환을 반복하며 값을 제거하는 정렬 알고리즘
• 마지막 자료와 교환한다는 점에서 선택 정렬과 유사함
• 별도의 공간을 요구하지 않음
  • 병합 정렬은 별도의 공간을 필요로 함

특성

• 완전 이진트리 구조를 사용해야함
• 마지막 레벨을 제외한 모든 레벨이 채워져있음
• 모든 노드는 값을 가지고 있으며, 자식 노드의 값보다 크거나 같아야 함(max-Heap)
• 모든 층은 왼쪽부터 정렬함

소요시간

• Heap을 만드는데 소요되는 시간: \(θ(n)\)
• 최악의 경우 \(O(n log n)\)의 시간이 소요됨

원소 제거

• 대상: 가장 큰 원소
• A[n-1]의 원소를 A[0]의 자리로 옮긴 후, A[n-1]을 처리할 대상에서 제외한다
  • 가장 마지막의 원소와 첫 원소를 교환해준다
• 가장 마지막의 값을 가져와하므로, \(O(log n)\)의 시간이 수행시간을 필요로 한다

원소 정렬

• 원소 제거를 수행하는 경우, A[n-1]의 원소가 A[0]자리로 이동되므로, 힙정렬의 특성을 위반한다.
• 이 상태에서 힙 정렬의 특성을 다시 충족시키기 위해서는 원소 정렬을 수행하여야 한다.
• 원소 정렬은 A[0]의 자식 노드 중 가장 값이 큰 노드의 방향으로 계속 값을 비교하며 정렬한다.