[JAVA] sort... 그 무언가..

정렬을 공부하다가 문득 궁금해졌다

 

java의 Arrays.sort() 는 어떤 정렬 알고리즘을 사용하는지..!

 

그렇게 켜본 인텔리제이 ..

역시나 평범하지는 않다 ..!

 

sort를 사용하면 메소드안에서 DualPivotQuicksort의 sort를 호출한다 

 

이걸..타고 들어가보면... 그래... 복잡한 코드다... 그래... 잘만들어진 메소드...가져다 쓰면 되는거지...

 

시간복잡도는 O(nlog(n)) 이고... 뭐 기존의 전통적인 퀵정렬보다... 빠르다고 하는 듯 하다 ..

 

여기서 끝내기 아쉬워서 검색좀 하면서 찾아보는데...

 

그렇다..!! Arrays에만 sort가 있는것이 아니다 ..!! 

 

Collections 에도 sort가 있다! 

 

배열과 리스트 ... 그 땔 수 없는 관계...

 

그렇다면 둘은 같은... 알고리즘을 사용할까?!

 

[Java] Java의 정렬 알고리즘 - Arrays와 Collections

 

아니다 ! 다르다 .!

 

Tim정렬.? 이건 처음들어본다.. 병합과 삽입의 콜라보..(Java 7이상..!)

 

참조지역성의 원리..! 뭐 비슷한 주소근처를 들려서 캐싱해준다는 말인듯... 

 

배열의 경우 연속해서 할당... 리스트는 노드이용 주소를 기억하니..!  다르긴 할것이다...!

 

아.. 유튜브에서 본 링크를 걸고 싶은데.. 아무리 찾아도 예전에 본 영상을 못찾겠다.. 참 쉬운 설명이였는데..

 

그래서 ~ 무튼!

 

퀵정렬의 경우 .. 참조지역성이 좋다 ! 그렇기 때문에 Arrays 는 sort 할때 듀얼피봇퀵정렬을사용하는것..

 

반면

 

리스트의 뭉텅이인 Collections 의경우 참조지역성이 낮고.. 메모리에 여러군데 존재하니.. 쓸때없이.. 캐시에 많이 올리는

 

것보다 다른 정렬 방법을 사용한다 .. 그래서 사용하는게 병합+삽입정렬인듯하다..

 

 

---

 

결론..!

 

• Arrays 는 참조지역성이 좋은.. 퀵정렬을 사용해서 sort
• Collections은 Tim 정렬을 사용해서 sort 

 

추가로 공부해보자... 참조지역성 과 CPU,, 캐싱 ,tim정렬..