#sorting
노트 6개
Algorithm › Paradigm
분할 정복문제를 서로 독립적인 작은 하위 문제로 나누어 재귀적으로 풀고, 그 결과를 합쳐 원래 문제를 해결하는 기법과, 실행 시간을 점화식(반복 대입·추정 후 증명·마스터 정리)으로 구하는 법.
Algorithm › Paradigm
스위핑 (Sweep Line)데이터를 정렬해 한 방향으로 한 번만 훑으며 답을 갱신하는 기법. 구간 겹침 판정·병합 같은 구간 문제의 기본 부품, 겹치는 구간 세기와 평면을 직선으로 나누는 기하 문제를 예로 든다.
Algorithm
정렬데이터를 일정한 순서로 나열하는 대표적인 정렬 알고리즘과 그 복잡도.
Algorithm › Sorting
기본 정렬: 버블·선택·삽입·셸·계수·기수 정렬구현이 단순한 O(n²) 비교 정렬 세 가지와 입력 상태에 따른 실제 속도 비교, 간격을 줄여 가며 삽입 정렬하는 셸 정렬, 비교 없이 정렬하는 계수 정렬·기수 정렬(LSD·MSD).
Algorithm › Sorting
병합 삽입 정렬 (Ford-Johnson)비교 횟수를 최소화하도록 설계된 Ford-Johnson 알고리즘. 짝짓기로 큰 원소를 재귀 정렬하고, 작은 원소를 야콥스탈 수 순서로 이진 삽입해 이진 탐색 비용을 낭비하지 않는다.
Algorithm › Sorting
병합 정렬과 퀵 정렬분할 정복으로 평균 O(n log n)에 정렬하는 두 대표 알고리즘과 상향식 병합 정렬, 퀵 셀렉트, 정렬 알고리즘 복잡도·안정성 비교, 언어별 표준 정렬, 메모리보다 큰 데이터의 외부 정렬.