- Divide-and-Conquer Techniques and Sorting Techniques
- Divide-and-Conquer Method
- Dynamic Programming Method
- Greedy Method
- Backtracking Method
- Local Search Method
- Branch-and-Bound Method
- Etc.
#
The Divide-and-Conquer Approach
-
- Divide an instance of a problem into one or more smaller instances.
- 문제의 인스턴스를 하나 이상의 작은 인스턴스로 나눕니다.
- Divide an instance of a problem into one or more smaller instances.
-
- Conquer (Solve) each of the smaller instances. Unless a smaller instance is sufficiently small, use recursion to do this.
- 각 작은 인스턴스를 정복합니다. 작은 인스턴스가 충분히 작지 않으면 재귀적을 사용하여 이 작업을 수행합니다.
- Conquer (Solve) each of the smaller instances. Unless a smaller instance is sufficiently small, use recursion to do this.
-
- If necessary, combine the solutions to the smaller instances to obtain the solution to the original instance.
- 필요한 경우 작은 인스턴스에 대한 솔루션을 결합하여 원래 인스턴스에 대한 솔루션을 확보합니다.
- If necessary, combine the solutions to the smaller instances to obtain the solution to the original instance.
#
Recursion
- Tower of Hanoi
-
- T(n) = 2T(n-1) +1, n>1, T(1) = 1
- Recursive thinking!
#
1. Sorting
A sorting algorithm is said to be stable if two items with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
Sorting Algorithm의 Stability : 정렬되지 않은 상태에서 같은 key 값을 가진 원소의 순서가 정렬 후에도 유지하느냐
일부 정렬 알고리즘은 삽입 정렬, 병합 정렬, 버블 정렬 등과 같이 본질적으로 안정적입니다. (정렬 후에도 원래의 순서가 유지됨)
Problem:
- Given a list of n items, arrange them in a certain order.
- Ex: non-increasing, non-decreasing, or etc.
- Given a list of n items, arrange them in a certain order.
Some criteria for choosing a sorting algorithm
How many items will you be sorting? 얼마나 많은 원소를 정렬할 것인가?
Will there be duplicate items in the data? 데이터에 중복 항목이 있습니까?
What do you know about the data? 데이터에 대해 알고 계십니까?
Is the data already partially sorted?
데이터는 이미 부분적으로 정렬되어 있는가?
Do you know the distribution of the items?
품목의 분포를 알고 있습니까?
Are the keys of items very long or hard to compare?
항목 키가 매우 길거나 비교하기 어렵습니까?
Is the range of possible keys very small? 가능한 키의 범위가 매우 작습니까?
Do you have to worry about disk accesses? 디스크 액세스에 대해 염려해야 합니까?
Do you need a stable sorting algorithm? 안정적인 정렬 알고리즘이 필요한가?
How much time do you have to write and debug your routine? 루틴을 작성하고 디버깅하는 데 얼마나 많은 시간이 필요합니까?
ref. Skiena, Steven S. The Algorithm Design Manual: The CD-ROM. 2 June 1997. 7 Dec. 2005,
- 원래 링크 깨짐
#
A Formal Definition of Sorting
- A partial order on a set S is a relation R such that for each a, b, and c in S:
- aRa is true (R is reflexive).
- aRb and bRc imply aRc (R is transitive)
- aRb and bRa imply a = b (R is antisymmetric)
- A Linear Order or Total Older on a set S is a partial order R on S such that for every pair of elements a, b, either aRb or bRa.
- The sorting problem
- Given a sequence of n elements a_1, a_2, ..., a_n drawn from a set having a linear order $\preceq $
- find a permutation \Pi = (\pi_1, \pi_2, ..., \pi_n) of (1,2,...,n) that will map the sequence into a nondecreasing sequence a_{\pi_1}, a_{\pi_2},...,a_{\pi_n} such that a_{\pi_1} \preceq a_{\pi_i+1} for $1 \leq i < n $
- Ex: $ \leq$ on \mathbb{Z}, $ $\subseteq $ on sets
- Sorting on data with partial order?
- ref. 이산수학 내용