각 입력 크기 n에 대해 하나의 트리
트리에는 가능한 모든 명령어 트레이스에 따른 비교가 포함
알고리즘의 실행시간 = 이동한 경로의 길이
최악의 경우 실행시간 = 트리의 높이
-> lower bound for decision tree:
-counting sort: 시간복잡도 O(n+k) - 비교정렬 아니다
배열 내의 원소 값들의 객수를 저장하는 counting array 만든다.
2. counting array(c[])의 요소들에 대해서 직전 요소들 값을 더함
3. 입력배열과 동일한 크기의 출력배열(b[])을 만들고 입력배열의 역순으로 채움
-Radix sorting: 시간복잡도 O(dn) - 정렬할 숫자의 자리수(d)
일의자리->십의자리->백의자리 순으로 정렬
장점: 큰입력에 대해 빠르고 코딩 및 유지 관리가 뛰어남
단점: 퀵소트와 달리 참조 지역성이 거의 표시되지 않는다, 따라서 well-tuned퀵소트는 가파른 메모리 계층 구조를 특징으로 하는 최신 프로세스에서 더 나은 성능 발휘
-Selection problem: i번째 작은 원소를 찾는다.
Naive algorithm: 시간복잡도 Θ(nlgn) 간단하지만 오래걸림
Randomized Selection: 시간복잡도 Worst Case:Θ(n^2)/ Average Case:Θ(n)
랜덤하게 피벗정하고 이를 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰값이 있게하고 이를 반복해 i번째 작은 값을 찾는다.
3. Worst-Case Linear-Time Selection: 시간복잡도 Θ(n)
RandomSelection함수를 이용하지만 Worst Case(Θ(n^2))가 나타날 수 없게 피벗을 중간 값으로 설정
1) 5개를 원소로 갖는 그룹으로 나누고 각 그룹의 중간값을 구한다,
2) 그룹들의 중앙값에서 중앙값을 찾는다. 피벗 주변 원소들의 순서를 조율
