[알고리듬] 2주차: 정렬

Selection sort

① $n$개 수 중 최소값을 찾는다

② 그 수를 맨 앞으로 이동

③ 그 수 다음부터 $n - 1$개 수에 대해 위 작업 반복

 

-> $i$번째 반복에서 앞의 $1$ ~ $(i - 1)$번째까지는 정렬이 되어 있음

 

시간복잡도: $O(n^2)$

 

 

 

 

Insertion sort

① $n$개의 수 중 $i$번째 수를 꺼냄

② $1$ ~ $i-1$번째 중 올바른 위치에 삽입

② $i=2$부터 $n$에 대해 위 작업을 반복

 

-> $i$번째 반복에서 앞의 $1$ ~ $i - 1$번째까지는 정렬이 되어 있음

 

시간복잡도: $O(n^2)$

 

*Best case: $\Theta(n)$

 

 

 

Bubble sort

이웃한 수끼리 교환으로 정렬

 

 

 

 

Merge sort and Quick sort

Divide and conquer

Merge sort

① $n$개의 수를 절반으로 나눈다 ($\frac{n}{2}$개씩)

② $\frac{n}{2}$개의 수 각각을 정렬한다

③ 정렬된 걸 합친다

 

시간복잡도: $O(n\log{n})$

 

 

Quick sort

최악의 경우 $O(n^2)$, 평균적인 경우 O(n\log{n})

대체로 빠름