11. Sort Algorithms

Sort algorithms

n개의 set이 주어졌을 때, increasing order로 key 기반 정렬을 수행하는 알고리즘이다. Time complexity와 Space complexity를 고려해야 한다. 또한 다음의 2가지 개념도 고려된다.

 

• Stability
  같은 key에 대해서, key의 순서가 유지되는 정렬
• In-place
  추가적인 공간을 필요하지 않는 정렬

 

Simple sorts ; comparison based

Selection sort

현재의 unsorted list에서 minimum을 선택해 정렬하는 알고리즘이다. 쉬운 알고리즘이다.

$T(n)$	$S(n)$	In-place	Stable
$O(n^2)$	$O(n)$	x	o

 

*swap을 이용하면 in-place로 구현할 수 있다. 대신 stable하지는 않게 된다. 이경우 $T(n)=O(n^2)_{comparison}+O(n)_{swap}$

 

Bubble sort

비교적 간단한 알고리즘이다. Iteration을 돌면서, compare하고 swap한다.

Bubble sort

$T(n)$	$S(n)$	In-place	Stable
$O(n^2)_c+O(n^2)_s$	O(1)	o	o

 

Comparison 같은 경우에는 $_nC_2$번 발생한다. Swap은 Best case에 0번, Worst case에 comparison 수 만큼, Average case에 그거에 절반정도 발생한다.

 

Insertion sort

Sorted list를 유지한 채, unsorted list의 첫 element를 sorted list에 추가하는 정렬방식이다. Quick sort가 best로 알려져있지만, 상황에 따라서 자주 사용되는 알고리즘이다. 

 

Online(new element에도 바로 사용가능) 알고리즘으로 사용되기도 한다.

 

Insertion sort

$T(n)$	$S(n)$	In-place	Stable
$O(n^2)_c+O(n^2)_s$	O(1)	o	o

Time complexity 분석

Time complexity for Average case

Time complexity table

 

Selelction vs Bubble vs Insertion

Alg	Time complexity			Space complexity	In-place	Stable
	Best	Worst	Average	Worst
Selection	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	o	x
Bubble	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	o	o
Insertion	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	o	o

 

Efficient sorts ; comparison based

Quick sort

Divide-and-conquer 기반의 정렬 알고리즘이다. Pivot을 선택하고 list를 pivot을 중심으로 split한다. Split을 하는 이유는, split을 함으로써 pivot의 위치가 확실해지기 때문이다. 이런 이유로 pivot이 largest나 smallest가 선택되면, worst case가 된다.

 

이 의미는 sorted list에 굉장히 약한 성능을 보여준다는 것을 뜻하기도 한다. 그래서 보통 randomization을 사용해서 pivot을 선정한다.

 

Split은 pivot보다 작으면 왼쪽으로, 크면 오른쪽으로 분리하는 과정이다.

Quick sort pseudo code

시간 복잡도를 구하는 과정은 다음과 같다.

Time complexity of Quick sort

$T(n)$	$S(n)$	In-place	Stable
$O(nlogn)$	O(1)	o	x

 

Merge sort

마찬가지로 Divide-and-conquer를 사용하는 알고리즘이다. Split하는 Quick sort와 다르게 Merge sort는 우선 element를 최소단위로 쪼개고 merge하면서 정렬을 수행하는 알고리즘이다.

Divide

Conquer(Merge)

 

시간 복잡도를 구하는 과정은 다음과 같다.

Time complexity of Merge sort

Quick Sort vs Merge sort vs Insertion Sort

Alg	Time complexity			Space complexity
	Best	Worst	Average	Worst
Quick sort	$O(nlogn)$	$O(n^2)$	$O(nlogn)$	$O(1)$
Merge sort	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$ / $O(1)$
Insertion sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$

*Data가 크다면 Merge를 이용하는게 더 좋을 수 있다.

*Quick sort가 Merge sort보다 practical하게 2배 더 빠르다.

 

Lower bound on sorting

정렬 문제의 현재 optimal time complexity의 범위는 $O(n)$에서 $O(nlogn)$이다. 그런 의미에서 봤을 때, Merge sort는 optimal한 알고리즘이다.

 

Distribution sorts ; non-comparison based

Radix sort

최소 자릿수부터 최대 자릿수까지 정렬을 수행해 최종적으로 정렬을 하는 방법입니다.

Radix sort

시간 복잡도는 $O(dn)$입니다. 다만 부동 소수점에 대해서는 적합하지 않다는 단점이 있다.