[알고리즘] Insertion Sort의 고찰

글에 들어가기 전에 comparison sort 중에 시간복잡도가 O(nlogn)으로 알려진 Heap, Merge, Quick sort 중에 평균적으로 quick sort가 빠르기에 아래의 Insertion sort와 비교대상에 넣게 되었음을 인지하고 읽어주세요...

위의 내용에 대해서는 빠른 시일 내에 다른 글을 작성해보도록 하겠습니다.

 

시작하겠습니다..!!

 

평소에 가장 비교 sort 중에 O(n²) 알고리즘은 시간복잡도 상으로 느리기에 잘 쓰지 않는다고 생각하게 됩니다. 하지만 시간복잡도는 n이 점근적으로 무한대에 접근할 때를 이야기하는 것이기에 n의 크기가 작을 때는 시간복잡도 앞에 상수를 잘 고려해야 합니다.

 

이 글에서는 O(n²)알고리즘 중 n이 작을 때 Insertion sort가 왜 쓰이는지와 자꾸 n이 작을 때라고 하는데 그 정확한 값은 어떻게 추정할 수 있는지?에 대해서 알아보겠습니다.

 

Insertion Sort vs Quick Sort

우리가 생각할 때 Insertion Sort는 O(n²)이고, Quick sort는 평균 O(nlogn)이어서 항상 quick sort가 빠르다고 생각하기 쉽습니다. 하지만 작은 n에 대해서는 단순히 시간복잡도만 볼 것이 아니라, 앞에 붙은 상수도 같이 고려해야 합니다. 상수는 locality of reference가 크게 작용하는데 Insertion sort는 순차적으로 배열 안 데이터에 접근하여 좋고, Quick sort도 pivot을 중심으로 데이터가 접근하기에 locality of reference가 좋습니다.

 

따라서, 이를 비교할 수는 없었고, 알고리즘이 얼마나 복잡한지로 상수의 크기를 측정할 수 있었습니다. (알고리즘이 복잡하다는 것은 Function call, 변수 등이 많다는 뜻.) n이 작을 때 Insertion sort은 알고리즘이 간단하고, Quick sort는 알고리즘이 복잡하기에 Ci을 Insertion sort의 상수라 하고, Cq을 Quick sort의 상수라 하면 작은 n에 대해 Ci * n² < Cq * nlogn이 성립합니다.

 

Insertion sort가 언제부터 Quick sort보다 성능이 좋은지?

n이 얼마 이하일 때 Insertion sort가 더 빠른지를 알게 되면 정렬 알고리즘을 사용할 때 배열의 크기에 따라 다른 알고리즘을 사용할 수 있도록 할 수 있습니다. 

 

Insertion sort 수도코드와 라인별 time 분석

전체 Insertion sort 시간

위처럼 insertion sort를 분석해보면 c1부터 c8의 cost가 상수 시간을 좌우함을 알 수 있습니다. 그런데 c1부터 c8의 cost의 크기는 하드웨어에 의존적입니다. 이 말은 사용하는 machine의 스펙, 어셈블리 레벨의 각 알고리즘 구현 (ex) loop unrolling..)등에 따라 달라진다는 뜻입니다. 

 

따라서, Insertion sort가 언제부터 Quick sort보다 성능이 좋은지는 환경에 따라 다르다고 말할 수 있겠습니다. 그래서 이렇게 크기에 따라 다르게 정렬 방법을 다르게 하려면 자신의 컴퓨터 환경에서 실험을 해보고 threshold를 정하는 게 좋겠습니다. 

 

그렇게 실험은 해본 사람은 있길래 아래의 링크를 첨부하였으니 읽어보면 좋을 듯합니다.

 

http://balsoftware.net/index.php/2016/10/02/combo-quicksort-and-insertion-sort/

Combo Quicksort and Insertion Sort – Bal Software

 

여기에 사용한 모든 그림은 Introduction to algorithm 책에서 가져왔습니다.