상세 컨텐츠

본문 제목

[Algorithm] Arrays.sort()

Develop/Algorithm

by 웽디 2015. 8. 25. 11:52

본문

평소엔 단순 정렬 알고리즘만 고민해왔다.
어느정도의 복잡도를 가지고 있는지..
어떤 알고리즘이 빠르지? 
요런 것들만 고민해왔는데

아시는 개발자 분이 Arrays.sort() 에 대해 깊게 생각해보고,
카드를 예제로 하여 한번 테스트 해봐달라고 하셔서 해보았다.


오홍! 

Primitive Type일 경우에는 QuickSort를 사용하지만,
Objective Type일 경우에는 MergeSort를 사용한다고 하는데............................

 

한번 테스트를 해봐야 할 것 같다.


테스트를 해본 결과[소스코드]


MergeSort로 정렬을 했을 시에는 객체의 순서가 보장되지만, 
QuickSort로 정렬했을 시에는 객체의 순서가 보장되지 않은 채로 정렬이 된다는 사실을 알 수 있었다.


결과 이미지

(Testcase로 설명 추가함)


#안정적으로 정렬되는 경우 - MergeSort이용



#불안정적으로 정렬되는 경우 - quickSort이용



결론

Primitive Type일 경우에는 동일한 값을 하나의 값으로 인식하기 때문에 순서를 고려할 필요가 없지만,

Object Type일 경우에는 동일한 값을 가진 객체가 여러개가 있을 수도 있기 때문에 순서를 고려해야 함.


그렇기 때문에 정렬 API를 만들 때, 

이러한 이유 때문에 Object Type일 때는 MergeSort를 사용하여 순서가 보장되도록 만든 게 아닐까 싶다.


해당 주제로 고민해보라고 하신 개발자님도 
단순하게 API를 사용만 하지말고, 설계한 이유에 대해서도 생각해보라는 
의도신 것 같다.






'Develop > Algorithm' 카테고리의 다른 글

[Algorithm] Arrays.sort()  (0) 2015.08.25

댓글 영역