알고리즘 4강 (정렬)

학습개요

1. 지난 시간에 배운 정렬 알고리즘(선택, 버블, 삽입, 셸 정렬)들은 n개의 데이터를 정렬하는 데 최악의 수행시간 O(n2)이 필요한 기본적인 성능의 알고리즘이었다. 이번 강의에서는 지난 시간에 배운 정렬 알고리즘에 비해서 평균적인 성능이 우수한 두 알고리즘, 퀵 정렬과 합병 정렬을 소개하고 그것들의 특성을 살펴본다.

 학습목표

1. 퀵 정렬의 원리, 다양한 경우의 성능 분석 과정 및 특징을 이해할 수 있다.
2. 합병 정렬의 처리 과정과 특징을 이해할 수 있다.
3. 두 정렬 알고리즘(퀵 정렬, 합병 정렬)과 분할정복 방법과의 관계를 이해할 수 있다.

 주요용어

1. 퀵 정렬(quick sort)
   - 피벗을 기준으로 주어진 배열을 크기가 일정하지 않은 2개의 부분배열로 분할하고, 각 부분배열에 대해서 독립적으로 퀵 정렬을 순환적으로 적용하는 방식의 알고리즘
2. 피벗(pivot)
   - 주어진 배열을 두 부분배열로 분할할 때 기준이 되는 특정 데이터
   - 보통 배열의 첫 번째 원소를 피벗으로 지정
3. 분할 함수
   - 피벗이 제자리를 잡고, 이를 기준으로 왼쪽 부분배열과 오른쪽 부분배열로 분할하는 함수
   - 교재에서의 함수명은 Partition()임
4. 합병 정렬(merge sort)
   - 주어진 배열을 동일한 크기의 2개의 부분배열로 분할하고, 각 부분배열을 순환적으로 합병 정렬로 정렬한 후, 정렬된 두 부분배열을 결합하여 하나의 정렬된 배열을 만드는 방식의 알고리즘
5. 합병 함수
   - 정렬된 두 부분배열을 합쳐서 하나의 정렬된 배열을 만드는 함수
   - 교재에서의 함수명은 Merge()임

정리하기

1. 1. 퀵 정렬
   ⦁ 특정 데이터(‘피벗’)를 기준으로 주어진 배열을 2개의 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 정렬 방식
   - 피벗이 제자리를 잡도록 하여 정렬하는 방식
   ⦁ 분할 함수 Partition() → 피벗을 기준으로 주어진 배열을 두 부분배열로 나누는 함수 → Θ(n)
   ⦁ 성능
   - 최악의 경우 → 항상 극심하게 불균형적으로 분할되는 경우 → 배열이 항상 0:n-1 또는 n-1:0으로 분할되는 경우 → 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열로 분할되는 경우 → 피벗이 항상 최솟값/최댓값이 되는 경우 → 입력 데이터가 정렬되어 있고 배열의 첫 번째 원소를 피벗으로 사용하는 경우 → T(n)=T(n-1)+Θ(n), T(1)=Θ(1) → O(n2)
   - 최선의 경우 → 항상 가장 균형적으로 분할되는 경우 → 배열이 항상 n/2:n/2로 분할되는 경우 → 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우 → 피벗이 항상 배열의 중간값이 되는 경우 → T(n)=2T(n/2)+Θ(n), T(1)=Θ(1) → O(nlogn)
   - 평균적인 경우 → 부분배열의 모든 분할 비율에 따른 수행 시간의 평균 → O(nlogn)
   ⦁ 피벗 선택의 임의성만 보장되면 최악의 성능이 아닌 평균적인 성능 O(nlogn)을 보일 가능성이 매우 높은 정렬 알고리즘
   ⦁ 불안정적 정렬, 제자리 정렬
   ⦁ 분할정복 방법이 적용된 알고리즘 → 결합 단계는 필요 없음
2. 2. 합병 정렬
   ⦁ 주어진 배열을 동일한 크기의 2개의 부분배열로 분할하고, 각 부분배열을 순환적으로 합병 정렬을 적용하여 정렬시킨 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 정렬 방식
   ⦁ 합병 함수 Merge() → 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 함수 → Θ(n)
   ⦁ 성능(최악/최선/평균) → T(n)=2T(n/2)+Θ(n), T(1)=Θ(1) → O(nlogn)
   ⦁ 안정적인 정렬
   ⦁ 제자리 정렬 알고리즘이 아님 → 정렬된 두 부분배열을 저장하기 위해 전체적으로 입력 크기 n만큼의 추가적인 저장 공간이 필요
   ⦁ 전형적인 분할정복 방법이 적용된 알고리즘