List와 Memory 복사를 이용한 Insertion Sort의 차이...

최근 알고리즘에 대해서 다시 공부하고 있습니다.
한번씩 생각해두지 않으면 너무 쉽게 잊혀지는 것 같습니다. 그래서라도 자꾸 보게되는데요...
오늘은 가장 처음에 나오는 정렬에 관한 실험입니다.

java로 구현해보았는데요, 재미있는 부분은 정렬된 변수들을 저장할 때에 그냥 단순히 list에 담아서 반환하면 편하지 않을까 생각했습니다. 왜냐하면 array에 있다면 매번 메모리를 복사해주어야 하는 부담이 있기 때문입니다.

결론부터 말씀드리면 memory-based-insertion-sort 의 완승!!!

랜덤숫자 : list-based-sort : memory-based-sort ( unit: msec)
1000 : 120 : 13
2000 : 1529 : 26
3000 : 6758 : 35

즉, 1000개의 단위 랜덤숫자를 증가할 때에 memory 기반의 insertion-sort는 거의 linear하게 증가하는 반면에 LinkedList를 사용할 때에는 지수적으로 증가하고 있습니다.

제가 아직 Java라는 언어에 익숙치 않아서 그런가 봅니다. 어쨌든 Java의 LinkedList를 사용할 때에는 절대로 1만개를 넘어가는 아니 5000개의 아이템 이상의 경우에는 사용을 자재하는 편이 좋을 것 같다는 생각이 듭니다.

p.s) 혹시 제가 잘못 이해하고 있는 부분이 있다면 언제든 댓글주시면 수정하도록 하겠습니다. 감사합니다. 제가 작성한 소스를 첨부해 봅니다.

invalid-file