[Algorithm] Sorting Algorithm

자자자 아주아주 간략하게 Sorting 정리해보자. 아무래도 알고리즘 쪽은 이번에 배운 것의 일부이기 때문에 살짝만 정리하고 넘어가려고 한다. 사실 앞에 두 개의 포스팅이 거의 전부이고 이번 포스팅에 할 Sorting과 다음 포스팅에서 할 Graph 관련된 알고리즘은 정말 방법과 효율만 언급하고 가려한다. 

Sorting에는 여러가지가 있는데, 우선 비효율적인 Sorting들만 봐보자.

1) Bubble Sort

https://www.youtube.com/watch?v=lyZQPjUT5B4

2) Selection Sort

https://www.youtube.com/watch?v=Ns4TPTC8whw

3) Insertion Sort

https://www.youtube.com/watch?v=ROalU379l3U

이 동영상을 보자. 아 아주 천재다. 어떻게 이런 걸 만들생각을 했지? 위의 알고리즘을 보면, 전부다 좀 답답하다는 생각이 든다. 그 말인 즉, 느리다는 것이다. 이 포스팅의 가장 아래쪽에 실제로 구현한 여러 개의 Sorting의 Performance 비교를 해놓은 것이 있는데, 그것을 참고해보면 위의 세 개는 큰 사이즈에 대해서는 절대 쓰면 안 된다는 것을 알게 된다. 위의 algorithm은 모두 O(n^2)의 좋지 않은 효율을 보인다.

그러면 더욱 더 좋은 소팅은 어떤 것이 있을까? Merge sort와 Quick sort가 있다.

4) Quick Sort

https://www.youtube.com/watch?v=ywWBy6J5gz8

5) Merge Sort

https://www.youtube.com/watch?v=XaqR3G_NVoo

Quick Sort와 Merge Sort는 모두 O(nlogn)의 효율을 보여준다. n이 logn으로 바뀐 차이인데, 이것은 사실 엄청나다. log는 보통 여기서 base 2인 log인데, n=1024일 때, n은 당연히 2014인데, logn은 10밖에 안된다. 어마무시한 차이이다. 따라서 Insertion Sort로는 n=1024일 때, 1024*1024 만큼의 연산이 있는데 반면, Quick Sort는 10240개 밖에 안 된다는 말이다. 대부분 Python, Java 혹은 여러 package에서 사용하고 있는 sorting algorithm은 Quick Sort이다. 

아래의 그림은 위에서 설명한 sorting algorithm을 비교한 것이다. (n = 100000)