Sort1
2021, Mar 21
Selection Sort
void SelectionSort ( A[], n ) // A[1 ... n]을 정렬
for last <- n downto 2 // ① for loop의 n-1 반복
Find Max A[k] in A[1... last]// ② max 값을 찾기 위한 비교반복 수(n-1, n-2 ... 2, 1)
A[k], A[last] Swap // ③ Swap- 시간복잡도(수행시간)
- ① + ② + ③ = n(n-1)/2
- T(n) = (n-1) + (n-2) + … 2 + 1 = O(n^2)
Bubble Sort
void BubbleSort ( A[], n ) // A[1...n]을 정렬
for last <- n downto 2 // ① for loop을 n-1 반복
for i-1 to last-1 // ② for loop은 각각 n-1, n-2, ... 2, 1 반복
if A[i] > A[i+1] then
Swap ( A[i], A[i+1]) // ③ Swap은 상수 시간- 시간복잡도(수행시간)
- ① + ② + ③ = n(n-1)/2
- T(n) = (n-1) + (n-2) + … 2 + 1 = O(n^2)
Insertion Sort
- Step1) 뒤에서부터 순회하며 들어갈 위치 찾기
- 들어갈 위치는 뒤에서 부터 찾는 것이 좋다, 뒤에서 부터 찾으면 비교와 shift를 한번에 처리할 수 있다.
- Step2) 위치로 이동
- Step3) Shift를 통해 배열 밀기 → 뒤에서부터 비교 + Swap
void InsertionSort ( A[], n )
for i <- 2 upto n // ① for loop은 n-1번 반복
Insert A[i] into suitable location in A[1...i] // ② 삽입은 최악의 경우 i-1을 반복- 시간복잡도(수행시간, Worst로 계산)
- ① + ② = n(n-1)/2
- T(n) = (n-1) + (n-2) + … 2 + 1 = O(n^2)
Merge Sort
- 분할 정복법
- 분할 - 해결하고자 하는 문제를 작은 크기의 동일한 문제로 분할
- 정복 - 각각의 작은 문제를 순환적으로 해결
- 합병 - 작은 문제의 해를 합하여 원래 문제의 해를 구함
- Merge sort는
- Step1) 데이터가 저장된 배열을 절반으로 나누고(분할)
- Step2) 각각을 순환적으로 정렬(정복)
- Step3) 정렬된 두개의 배열을 합쳐서 전체를 정렬(합병)
void MergeSort ( A[], p, r ) // Recursive의 경우 Argument를 명시화 한다. A[p...r]을 정렬
if p < r then
q <- (p + r) / 2 // ① p, q의 중간 지점 계산
MergeSort(A, p, q) // ② 배열의 전반부 Sort
MergeSort(A, q+1, r) // ③ 배열의 후반부 Sort
Merge(A, p, q, r) // ④ 정렬된 두개의 배열 합병
void Merge ( A[], p, q, r )
//Step1) 정렬되어 있는 두 배열 A[p...q] 와 A[q+1...r]을 합하여
//Step2) 정렬된 A[p...r]을 만든다- Implementation
void Merge ( int data[], int p, int q, int r ) {
int i = p, j = q+1, k = p;
int tmp[data.length];
while(i<=q && r <=j) {
if(data[i] <= data[j]) tmp[k++] = data[i++];
else tmp[k++] = data[j++];
}
while(i<=q) tmp[k++] = data[i++];
while(j<=r) tmp[k++] = data[j++];
for(int i = p; i <= r; i++) data[i] = tmp[i];
}- 시간복잡도(수행시간)
T(n) : Data가 n개일 때- a) 0 : n =1
b) T([n / 2]) + T([n / 2]) + n : Otherwise
여기서 n은 merge에 소요되는 시간 : Data n개를 한번씩 비교해야 하므로… - O(nlog(n))
- a) 0 : n =1
Quick Sort
- 분할 정복법
- 분할 - 배열을 다음과 같은 조건이 만족 되도록 두 부분으로 나눈다
- elements in lower parts <= elements in upper parts
- 정복 - 각각의 작은 문제를 순환적으로 해결
- 합병 - Nothing to do
- 분할 - 배열을 다음과 같은 조건이 만족 되도록 두 부분으로 나눈다
void QuickSort ( A[], p, r ) // A[p...r]을 정렬한다. Recursive는 Arguments를 명시화 한다.
if (p < r) then
q = Partition(A, p, r) // ① 분할
QuickSort(A, p, q-1) // ② lower 정렬
QuickSort(A, q+1, r) // ③ upper 정렬
int Partition ( A[], p, r )
// Step1) 배열 A[p...r]의 원소들을 A[r] 기준으로 양쪽 재배치하고
// Step2) A[r]이 위치한 위치를 return한다.- Partitioning detail
int Partition ( A, p, r ) // O(n) Pivot 값을 모든 데이터와 비교해야 하므로
x <- A[r]
i <- p-1
for j <- p to r-1
if A[j] <= x then
i <- i+1
Swap A[i], A[j]
Swap A[i+1], A[j]
return i+1- 시간복잡도(수행시간)
- Worst case : 분할을 하였을 때 항상 한쪽은 0개, 다른 한쪽은 n-1개로 분할되는 경우
T(n) = T(0) + T(n-1) + Θ(n)
= T(n-1) + Θ(n)
= T(n-2) + T(n-1) + Θ(n-1) + Θ(n)
= … … …
= Θ(1) + Θ(2) + Θ(3) + … … + Θ(n-1) + Θ(n) = Θ(n^2) - Best Case ? : 항상 절반으로 분할 되는 경우
T(n) = 2T(n/2) + Θ(n) = Θ(nLog(n))
- Worst case : 분할을 하였을 때 항상 한쪽은 0개, 다른 한쪽은 n-1개로 분할되는 경우