-
주어진 객체(레코드, 아이템)들의 리스트를 정해진 기준으로 순서대로 나열(재배치)하는 것
- 숫자는 크기순으로 정렬 : 오름차순(ascending order) vs 내림차순(descending order)
- 문자열은 사전 순서(lexical order)로 정렬 : 대소문자 이슈
- 다수의 필드(속성)를 갖는 레코드의 경우, 특정 필드(들)를 정렬 기준으로 함
정렬은 컴퓨팅 인프라에서 가장 중요한 컴포넌트 중 하나이다.
대표적 정렬 알고리즘
단순하지만 비효율적인 방법 : 삽입정렬, 버블정렬, 선택정렬
복잡하지만 효율적인 방법 : 병합정렬, 퀵정렬, 힙정렬
특수한 상황에서만 사용하는 방법 : 기수정렬, 계수정렬, 버킷정렬정렬 알고리즘의 논제
- 실행시간은 빨라야 한다
- 안정적(stable) 정렬: 값이 같은 경우 원래 순서로 정렬한다
- 제자리(in-place) 정렬: 정렬 공간 안(주어진 메모리 공간)에서만 정렬하는 것이다.
삽입정렬
삽입정렬 예) 테이블에 놓인 카드를 하나씩 집어, 한쪽 손에 정렬된 상태를 유지하도록 끼워 넣는 방식으로 정렬
특징
- 정렬된 a[0,..,i-1]에 a[i]를 끼워 넣어 정렬된 a[0,...,i]를 만드는 과정을 반복
- 제자리 정렬 : 배열 내부에서 자리 바꾸는 방식, 추가공간은 상수 개(배열 크기와 상관없음)
- 안정적 정렬 : a[j] > x 조건을 사용하면 같은 값을 갖는 경우 원래 순서를 유지
시간 복잡도
- 최선: 선형시간 O(n)
- 최악: 이차시간 O(n^2)
- 평균: 이차시간 O(n^2)
분할정복(divide-and-conquer)법
설계 전략
- 분할
- 문제를 (하나 이상의) 더 작은 문제로 분할
- 정복
- 작은 문제들을 각각 재귀(recursion)적으로 정복
- 통합
- 작은 무제에 대한 해답을 통합하여 원래 문제의 해답을 구함
하향식(top-down) 접근 방식
- 문제의 맨 상위 사레의 해답을 더 작은 사례에 대한 해답을 재귀적으로 구함
- 대표적인 분할정복 정렬 알고리즘 : 병합정렬, 퀵정렬
재귀 알고리즘
- 재귀는 문제에 대한 해답을 같은 속성의 더 작은 문제들에 대한 해답으로부터 구하는 방법
- 스택 오버플로우 방지하기 위하여 반드시 탈출(종료) 조건(=base case)이 있어야 함
- 함수의 정의에서 자기 자신을 호출(self-call)
재귀 알고리즘1
- 마지막 원소를 제외한 앞쪽 부분 배열의 합을 구했다면, 배열의 합은 앞부분 합과 마지막 원소의 합
- 앞쪽 부분 배열의 합은 같은 방식으로 구함
- 만일 원소가 한 개이면 합은 원소 자신
array_sum2(last)
if (last == 0) return a[last]
return array_sum2(last - 1) + a[last]시간 복잡도
T(n) = O(n)
재귀 알고리즘2
- 배열의 앞쪽 절반의 합과 뒤쪽 절반의 합을 구하여 더함
- 앞쪽 절반과 뒤쪽 절반의 합은 같은 방식으로 구함
- 만일 원소가 한 개이면 합은 원소 자신
array_sum3(low, high)
if (low == high) return a[low]
mid = (low + high) / 2
return array_sum3(low, mid) + array_sum3(mid + 1, high)시간 복잡도
T(n) = T(n/2) + T(n/2) = 1 = 2T(n/2) + 1
마스터 정리(Master Theorem)
작은 문제의 크기가 일정 비율로 줄어들 때, 시간복잡도의 차수(order)를 쉽게 구하는 정리
주어진 크기의 문제를 푸는 데 걸리는 시간
= 작은 문제(들)를 푸는 데 걸리는 시간 + 분할 및 통합 시간
n/b : 작은 문제의 크기
a : 작은 문제의 개수
c * n^k : 분할과 통합에 걸리는 시간분할정복법을 피해야 하는 경우
크기 n인 사례가 거의 n에 가까운 크기의 2개 이상의 사례로 분할되는 경우
예) 하노이의 탑
병합정렬
병합(two-way merge) 알고리즘
2개의 정렬된 배열을 하나의 정렬된 배열로 합치는 알고리즘
-> 2개의 분리된 정렬된 배열을 병합하는 알고리즘
병합정렬(merge sorting)
이분한 부분 배열을 각각 먼저 정렬한 후, 이들을 병합(merge)하여 정렬하는 방법
분할 정복적 설계
분할 : 배열을 2개의 부분 배열로 분할
정복 : 부분 배열을 정복(정렬), 배열이 충분히 작지 않으면 재귀호출!
통합 : 정렬된 부분 배열을 병합(merge)하여 하나의 정렬된 배열로 만듬특징
안정적 정렬이다.
-> 비교하는 두 레코드의 키가 같은 경우, 왼쪽 부분 배열의 레코드를 병합한 배열로 이동
제자리 정렬이 아니다.
-> 문제의 크기에 비례하는 보조 배열이 필요하다.
시간복잡도 분석
실행시간 = 분할시간 + 분할된 문제의 정복시간 + 통합시간
- 분할 : 상수시간이 소요
- 정복 : 2 * (원래 문제 크기의 절반인 부분 배열을 병합정렬 하는 데 걸리는 시간)
- 통합 : 병합(merge)에 최악의 경우 O(n)
최악의 경우 : 2W(n/2) + O(n)
마스터 정리: W(n) = O(nlgn)
평균: O(nlgn)
퀵정렬
퀵정렬(quicksort)알고리즘
20세기 10대 알고리즘 중 하나이다
분할(partition)알고리즘
분할 원소(partition element 혹은 pivot item)보다 작은 아이템은 왼쪽 배열로, 큰 아이템은 오른쪽 배열로 분할하는 알고리즘
시간 복잡도 분석
T(n) = O(n)으로 선형시간 알고리즘이다
퀵정렬 알고리즘
입력 : 배열 a[low,...,high]
출력 : 정렬된 배열 a[low,...,high]퀵정렬은 제자리(in-place) 정렬
퀵정렬은 안정적 정렬이 아님(not stable)
(B1, C1, C2, A1) --> (A1, B1, C2, C1)시간 복잡도 분석
최악:
W(n) = W(n-1) + O(n) -> W(n) = O(n^2)
평균:
피봇원소가 a[k]인 경우 : 분할 후 두 부분 배열 a[0 ~ (k-1)]과 a[(k+1) ~ n -1]을 재귀적으로 퀵정렬 해야 함
성능 개선
피봇 원소가 퀵정렬의 시간을 결정
중복키(duplicate keys)가 많은 경우(선능 개선)
정렬 문제의 계산 복잡도
주어진 문제를 푸는 모든 알고리즘의 효율성의 하한(lower bound)을 구하는 것이다.
비교에 기반한 정렬의 하한
키를 비교만 하여 개의 서로 다른 키를 정렬하는 알고리즘은, 평균의 경우 키의 비교횟 수가 최소한
| nlgn - 1.45n | = O(nlgn)
즉, 키의 비교만으로 정렬하는 알고리즘은 O(nlgn)보다 더 빠른 알고리즘은 불가능