정렬은 비교, 중복, 탐색을 위해서 필요함.
선택 정렬
시간 복잡도
$O(n^2)$
$ (n-1) + (n-2) + ... + 1 + cn = {n(n-1) \over 2} + cn = O(n^2) $
선택정렬이란?
가장 큰 수를 선택한 후
1. 1~n까지 가장 큰 수를 찾는다.
2. 가장 큰 수와 마지막 수의 위치를 교환한다.
3. 정렬된 수를 제외하고 정렬될 때까지 1~2를 반복한다.
c++ 코드
void selection_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
int largest_index;
for (int i = SIZE - 1; i > -1; i--)
{
largest_index = i;
for (int j = i; j > -1; j--)
{
if (arr[largest_index] < arr[j])
largest_index = j;
}
int temp = arr[largest_index];
arr[largest_index] = arr[i];
arr[i] = temp;
}
}
Python 코드
import random
from timeit import default_timer as timer
def selection_sort(x):
for last in range(len(x)-1, 0, -1):
largest = 0
for i in range(1, last+1):
if x[i] > x[largest]:
largest = i
x[largest], x[last] = x[last], x[largest]
def test(x):
for i in range(1, len(x)):
if x[i-1] > x[i]:
return False
return True
data = [1, 3, 5, 6, 8, 2, 4, 10, 7, 9]
start = timer()
selection_sort(data)
print(timer() - start)
print(data)
print(test(data))
버블 정렬
시간 복잡도
Worst : $O(n^2)$
Best : $O(n)$
$ (n-1) + (n-2) + ... + 1 + cn = {n(n-1) \over 2} + cn = O(n^2) $
버블정렬이란?
1. 두 장씩 비교하면서 큰 것을 오른쪽으로
2. 맨 오른쪽이 제일 큼
3. 맨 오른쪽 빼고 정렬될 때까지 1~2 반복
c++ 코드
void bubble_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
bool flag = false; // stop option
for (int i = SIZE - 1; i > -1; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j + 1])
{
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// stop option
if (!flag) break;
}
}python 코드
import random
from timeit import default_timer as timer
def bubble_sort(A):
sorted = True # Termination conditions
for last in range(len(A) - 1, 1, -1):
for i in range(last):
if A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
sorted = False
if sorted:
break
def test(A):
for i in range(1, len(A)):
if A[i - 1] > A[i]:
return False
return True
x = random.sample(range(10000), 100)
start = timer()
bubble_sort(x)
print(timer() - start)
print(x)
print(test(x))
삽입 정렬
시간 복잡도
Worst : $O(n^2)$
Best : $O(n)$
$ 1 + 2 + ... + (n-1) = {n(n-1) \over 2} = O(n^2) $
삽입 정렬이란?
현재 위치 앞의 수들을 보고 현재 수가 들어갈 수 있는 곳을 찾아서 삽입
c++ 코드
void insertion_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
for (int i = 1; i < SIZE; i++)
{
int loc = i - 1; //0
int now = arr[i]; //3
while (loc >= 0 && now < arr[loc])
{
arr[loc + 1] = arr[loc];
loc--;
}
arr[loc + 1] = now;
}
print(3, arr);
}
Python 코드
def insertion_sort(A):
for i in range(1, len(A)):
loc = i - 1
new_item = A[i]
while new_item < A[loc] and loc > -1:
A[loc+1] = A[loc] # A[loc+1], A[loc] = A[loc], A[loc+1]
loc-=1
A[loc+1] = new_item
data = [1, 3, 5, 6, 8, 2, 4, 10, 7, 9]
start = timer()
insertion_sort(data)
print(timer() - start)
print(data)
print(test(data))
병합 정렬
시간 복잡도
$O(nlogn)$
마스터 정리 유형 3으로 시간 복잡도를 계산할 수 있다.
* 마스터 정리 유형 3 근사 버전:
$ T(n) = aT({n \over b}) + f(n) $
$ h(n) = n^{log_ba}$ 라고 할 때, ${f(n) \over h(n)} = \Theta (1)$ 이면 $T(n) = \Theta (h(n)logn) $
따라서,
$ T(n) = 2T({n \over 2}) + c_1n+c_2 , a = 2, b = 2, f(n) = c_1n+c_2 \\ h(n) = n^{log_2 2} $
$ {c_1n+c_2 \over n^{log_2 2}} = \Theta (1) $ 이므로 $T(n) = \Theta (n^{log_2 2} logn) = \Theta (nlogn)$
병합 정렬이란?
아래 코드에서 Divide 부분이 merge_sort_fuc이고
Combine 부분이 merge라고 생각하면 된다.
c++ 코드
void merge(int list[], int left, int mid, int right)
{
int merge_arr[SIZE];
int i, j, k;
i = left;
j = mid + 1;
k = left;
while (i <= mid && j <= right)
{
if (list[i] < list[j])
merge_arr[k++] = list[i++];
else
merge_arr[k++] = list[j++];
}
while (i <= mid)
merge_arr[k++] = list[i++];
while (j <= right)
merge_arr[k++] = list[j++];
for (int i = left; i <= right; i++)
list[i] = merge_arr[i];
}
void merge_sort_func(int list[], int left, int right)
{
int mid;
if (left < right)
{
mid = (left + right) / 2;
merge_sort_func(list, left, mid);
merge_sort_func(list, mid + 1, right);
merge(list, left, mid, right);
}
}
void merge_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
merge_sort_func(arr, 0, SIZE - 1);
print(4, arr);
}
python 코드
import random
from timeit import default_timer as timer
def merge_sort(A, p, r):
if p<r:
q = (p+r)// 2
merge_sort(A, p, q)
merge_sort(A, q+1, r)
merge(A, p, q, r)
def merge(A, p, q, r):
i = p
j = q+1
t = 0
tmp = A[:]
while i<=q and j<=r:
if A[i] <= A[j]:
tmp[t] = A[i]
i+=1
else :
tmp[t] = A[j]
j+=1
t+=1
while i<=q:
tmp[t] = A[i]
t+=1
i+=1
while j<=r:
tmp[t] = A[j]
t+=1
j+=1
i = p
t = 0
while i<=r:
A[i] = tmp[t]
i+=1
t+=1
def test(A):
for i in range(1, len(A)):
if A[i - 1] > A[i]:
return False
return True
x = random.sample(range(10000), 100)
start = timer()
merge_sort(x, 0, len(x)-1)
print(timer() - start)
print(x)
print(test(x))
퀵 정렬
시간 복잡도
$ O(nlogn) $
Worst
worst case는 한 개씩 쪼개지는 경우이다.
퀵 정렬의 경우 n개의 데이터가 있으면 피벗을 제외하고 n-1개의 데이터들과 비교하게 되므로
$ O(n^2) $
$ T(n) = T(n-1) + c_1n+c_2 $
Best
best case는 반씩 쪼개지는 경우이다.
$ T(n) = 2T({n \over 2}) + c_1n + c_2 $
마스터 정리 유형 3으로 시간 복잡도를 계산할 수 있다.
* 마스터 정리 유형 3 근사 버전:
$ T(n) = aT({n \over b}) + f(n) $
$ h(n) = n^{log_ba}$ 라고 할 때, ${f(n) \over h(n)} = \Theta (1)$ 이면 $T(n) = \Theta (h(n)logn) $
따라서,
$ T(n) = 2T({n \over 2}) + c_1n+c_2 , a = 2, b = 2, f(n) = c_1n+c_2 \\ h(n) = n^{log_2 2} $
$ {c_1n+c_2 \over n^{log_2 2}} = \Theta (1) $ 이므로 $T(n) = \Theta (n^{log_2 2} logn) = \Theta (nlogn)$
Average
$ T(n) = T(i-1) + T(n-i) + c_1n + c_2 $
$ T(n) = {1 \over n} \sum_{i=1}^n (T(i-1) + T(n-i)) + c_1n+ c_2 $
$ T(n) = {2 \over n} \sum_{k=0}^{n-1} T(k) + c_1n +c_2 $
$ T(n) = \Theta (nlogn) $
퀵 정렬이란?
pivot을 기준으로 pivot보다 작으면 왼쪽, 크면 오른쪽으로 정렬.
왼쪽, 오른쪽 배열에 대해서도 똑같이 진행
c++ <algorithm>의 sort() 함수의 기반이 되는 알고리즘
c++ 코드
void quick_sort_func(int list[], int left, int right)
{
if (left >= right) return;
int pivot = left;
int i = left + 1, j = right;
while (i <= j)
{
while (i <= right && list[pivot] > list[i]) i++;
while (j >= left && list[pivot] < list[j]) j--;
if (i > j) {
int temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;
}
else {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
quick_sort_func(list, left, j - 1);
quick_sort_func(list, j + 1, right);
}
void quick_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
quick_sort_func(arr, 0, SIZE - 1);
print(5, arr);
}
python 코드
import random
from timeit import default_timer as timer
def partition(A, p, r):
x = A[r]
i = p
for j in range(p, r):
if A[j] <= x:
A[i], A[j] = A[j], A[i]
i+=1
A[i], A[r] = A[r], A[i]
return i
def qsort(A, p, r):
if p<r:
q = partition(A,p,r)
qsort(A, p, q-1)
qsort(A, q+1, r)
def quick_sort(A):
qsort(A, 0, len(A)-1)
def test(A):
for i in range(1, len(A)):
if A[i-1] > A[i]:
return False
return True
x = random.sample(range(10000), 100)
print(x)
start = timer()
quick_sort(x)
print(timer() - start)
print(x)
print(test(x))
힙 정렬
시간 복잡도
$ O(nlogn) $
힙 정렬이란?
최대 힙 / 최소 힙을 사용해서 정렬하는 것.
아래 코드에서는 최대 힙을 사용하였다.
최대 힙은 맨 위가 트리에서 가장 큰 원소이므로 최대 힙이 만들어지면 맨 위의 원소를 제외하고 또다시 최대 힙을 만드는 것을 반복하며 정렬한다.
c++ 코드
/*
* parent = (i-1)/2
* left = i*2 + 1
* right = i*2 + 2
*/
void make_heap(int n, int arr[])
{
for (int i = (n - 2) / 2; i > -1; i--)
{
int now = i;
int left = i * 2 + 1, right = i * 2 + 2;
int child = left;
if (arr[left] < arr[right] && right < n) child = right;
while (arr[child] > arr[now] && child < n)
{
int temp = arr[now];
arr[now] = arr[child];
arr[child] = temp;
now = child;
left = now * 2 + 1, right = now * 2 + 2;
if (arr[left] < arr[right] && right < n) child = right;
}
}
}
void heap_sort(int n)
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
make_heap(n, arr);
for (int i = n - 1; i > -1; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
make_heap(i, arr);
}
cout << "<heap_sort>" << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << ' ';
}
기수 정렬 ( Radix sort )
시간 복잡도
$ O(n) $
n개의 원소를 k자릿수만큼 비교 => $ O(n) $을 $ k $번 반복 = $ O(n) $
기수 정렬이란?
입력이 모두 K 자릿수 이하의 자연수인 경우 자릿수 별로 안정성을 유지하며 정렬한다.
이때, 값이 같은 원소는 정렬 전후 순서가 바뀌지 않는다.
c++ 코드
int A[15] = { 123,2154,222,4,283,1560,1061,2150,3154,33,2234,345,677,8911,1 };
void rsort(int m, int n)
{
queue<int> bucket[10];
for (int i = 0; i < n; i++)
{
int index = A[i] / pow(10, m);
index %= 10;
bucket[index].push(A[i]);
}
int index = 0;
for (int i = 0; i < 10; i++)
{
while (!bucket[i].empty())
{
A[index++] = bucket[i].front();
bucket[i].pop();
}
}
}
void radix_sort()
{
int k = 4;
for (int i = 0; i < 4; i++)
rsort(i, 15);
cout << "<radix_sort>" << endl;
for (int i = 0; i < 15; i++)
cout << A[i] << ' ';
cout << endl;
}python 코드
import random
from timeit import default_timer as timer
def rsort(A, m):
buckets = [[] for _ in range(10)]
for v in A:
index = v // (10 ** m)
index %= 10
buckets[index].append(v)
res = []
for bucket in buckets:
res.extend(bucket)
return res
def radix_sort(A, k):
for i in range(0, k):
A = rsort(A, i)
return A
def test(A):
for i in range(1, len(A)):
if A[i-1] > A[i]:
return False
return True
x = random.sample(range(10000),100)
start = timer()
x = radix_sort(x, 4)
print(timer() - start)
print(x)
print(test(x))
계수 정렬 ( Counting Sort )
시간 복잡도
$ O(n) $
$ \Theta (k) + \Theta (n) + \Theta (k) + \Theta (n) $
$ k \le O(n) $ => $ O(n) $
계수 정렬이란?
- 입력 값이 모두 k 이하인 경우
- $ k \le O(n) $ 인 경우에만 의미가 있음
- 같은 값이 몇 개인지 세어서 위치 결정
해당 수 앞에 몇 개가 존재하는지를 세어서 정렬
c++ 코드
void counting_sort()
{
int n = 10;
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
int count[11] = {};
int sortarr[10] = {};
for (int i = 0; i < n; i++)
count[arr[i]]++;
for (int i = 1; i < 11; i++)
count[i] += count[i - 1];
for (int i = 0; i < n; i++)
{
count[arr[i]]--;
sortarr[count[arr[i]]] = arr[i];
}
cout << "<counting_sort>" << endl;
for (int i = 0; i < n; i++)
cout << sortarr[i] << ' ';
cout << endl;
}
python 코드
import random
from timeit import default_timer as timer
def counting_sort(A, k):
B = [0] * len(A)
C = [0] * (k+1)
for v in A:
C[v] += 1
for i in range(1, k+1):
C[i] += C[i-1]
for i in range(len(A)-1, -1, -1):
v = A[i]
C[v] -= 1
B[C[v]] = v
return B
def test(A):
for i in range(1, len(A)):
if A[i-1] > A[i]:
return False
return True
x = random.choices(range(50), k=100)
start = timer()
print(x)
x = counting_sort(x, 49)
print(timer() - start)
print(x)
print(test(x))
팀 정렬
팀 정렬이란?
- 2002년 Tim Peters 가 개발
- 파이썬 버전 2.3부터 표준 정렬 알고리즘으로 사용
- 데이터가 정렬된 정도에 따라 삽입 정렬과 병합 정렬 사이를 전환하는 적응형 알고리즘
시간복잡도 비교
전체 코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
#define SIZE 10
void print(int option, int list[])
{
switch (option) {
case 1:
cout << "<selection sort>" << "\n";
break;
case 2:
cout << "<bubble sort>" << "\n";
break;
case 3:
cout << "<insertion sort>" << "\n";
break;
case 4:
cout << "<merge sort>" << "\n";
break;
case 5:
cout << "<quick sort>" << "\n";
break;
}
for (int i = 0; i < SIZE; i++)
cout << list[i] << ' ';
cout << "\n";
}
void selection_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
int largest_index;
for (int i = SIZE - 1; i > -1; i--)
{
largest_index = i;
for (int j = i; j > -1; j--)
{
if (arr[largest_index] < arr[j])
largest_index = j;
}
int temp = arr[largest_index];
arr[largest_index] = arr[i];
arr[i] = temp;
}
print(1, arr);
}
void bubble_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
bool flag = false; // stop option
for (int i = SIZE - 1; i > -1; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j + 1])
{
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// stop option
if (!flag) break;
}
print(2, arr);
}
void insertion_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
for (int i = 1; i < SIZE; i++)
{
int loc = i - 1; //0
int now = arr[i]; //3
while (loc >= 0 && now < arr[loc])
{
arr[loc + 1] = arr[loc];
loc--;
}
arr[loc + 1] = now;
}
print(3, arr);
}
////////////////////////////////////////////////////////////////
void merge(int list[], int left, int mid, int right)
{
int merge_arr[SIZE];
int i, j, k;
i = left;
j = mid + 1;
k = left;
while (i <= mid && j <= right)
{
if (list[i] < list[j])
merge_arr[k++] = list[i++];
else
merge_arr[k++] = list[j++];
}
while (i <= mid)
merge_arr[k++] = list[i++];
while (j <= right)
merge_arr[k++] = list[j++];
for (int i = left; i <= right; i++)
list[i] = merge_arr[i];
}
void merge_sort_func(int list[], int left, int right)
{
int mid;
if (left < right)
{
mid = (left + right) / 2;
merge_sort_func(list, left, mid);
merge_sort_func(list, mid + 1, right);
merge(list, left, mid, right);
}
}
void merge_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
merge_sort_func(arr, 0, SIZE - 1);
print(4, arr);
}
//////////////////////////////////////////////////////////////
void quick_sort_func(int list[], int left, int right)
{
if (left >= right) return;
int pivot = left;
int i = left + 1, j = right;
while (i <= j)
{
while (i <= right && list[pivot] > list[i]) i++;
while (j >= left && list[pivot] < list[j]) j--;
if (i > j) {
int temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;
}
else {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
quick_sort_func(list, left, j - 1);
quick_sort_func(list, j + 1, right);
}
void quick_sort()
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
quick_sort_func(arr, 0, SIZE - 1);
print(5, arr);
}
//////////////////////////////////////////////////////////////
/*
* parent = (i-1)/2
* left = i*2 + 1
* right = i*2 + 2
*/
void make_heap(int n, int arr[])
{
for (int i = (n - 2) / 2; i > -1; i--)
{
int now = i;
int left = i * 2 + 1, right = i * 2 + 2;
int child = left;
if (arr[left] < arr[right] && right < n) child = right;
while (arr[child] > arr[now] && child < n)
{
int temp = arr[now];
arr[now] = arr[child];
arr[child] = temp;
now = child;
left = now * 2 + 1, right = now * 2 + 2;
if (arr[left] < arr[right] && right < n) child = right;
}
}
}
void heap_sort(int n)
{
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
make_heap(n, arr);
for (int i = n - 1; i > -1; i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
make_heap(i, arr);
}
cout << "<heap_sort>" << endl;
for (int i = 0; i < n; i++)
cout << arr[i] << ' ';
cout << endl;
}
//////////////////////////////////////////////////////////
int A[15] = { 123,2154,222,4,283,1560,1061,2150,3154,33,2234,345,677,8911,1 };
void rsort(int m, int n)
{
queue<int> bucket[10];
for (int i = 0; i < n; i++)
{
int index = A[i] / pow(10, m);
index %= 10;
bucket[index].push(A[i]);
}
int index = 0;
for (int i = 0; i < 10; i++)
{
while (!bucket[i].empty())
{
A[index++] = bucket[i].front();
bucket[i].pop();
}
}
}
void radix_sort()
{
int k = 4;
for (int i = 0; i < 4; i++)
rsort(i, 15);
cout << "<radix_sort>" << endl;
for (int i = 0; i < 15; i++)
cout << A[i] << ' ';
cout << endl;
}
/////////////////////////////////////////////////////////////
void counting_sort()
{
int n = 10;
int arr[10] = { 1,3,5,6,8,2,4,10,7,9 };
int count[11] = {};
int sortarr[10] = {};
for (int i = 0; i < n; i++)
count[arr[i]]++;
for (int i = 1; i < 11; i++)
count[i] += count[i - 1];
for (int i = 0; i < n; i++)
{
count[arr[i]]--;
sortarr[count[arr[i]]] = arr[i];
}
cout << "<counting_sort>" << endl;
for (int i = 0; i < n; i++)
cout << sortarr[i] << ' ';
cout << endl;
}
int main()
{
selection_sort();
bubble_sort();
insertion_sort();
merge_sort();
quick_sort();
heap_sort(10);
radix_sort();
counting_sort();
return 0;
}
'22-1학기 > 알고리즘' 카테고리의 다른 글
| 5. 검색 트리 (0) | 2022.04.06 |
|---|---|
| 4. 선택 알고리즘 (0) | 2022.04.06 |
| 2. 점화식과 알고리즘 복잡도 분석 (0) | 2022.03.14 |
| 1. 알고리즘 표기법 (0) | 2022.03.14 |