자바 표준 라이브러리 함수 Arrays.sort()에 대하여

개인 학습/알고리즘

tact 2025. 5. 20. 05:20

최근 두 달 동안 너무 바빴다.

본 전공(경영) 중간고사, 개인 과제, 팀 프로젝트
개인 프로젝트(크롬 익스텐션 개발, 웹 보안 찍먹)
멋사 아이디어톤 준비, 자격증 시험 등

아무튼 알고리즘을 놓고 산 지가 벌써 두 달 조금 안 된 것 같은데,

조금이나마 여유가 생기기도 했고 입과 전까지 목표한 게 있어서 다시 시작했다.

문제는, 자바 자체를 오랜만에 봐서 그런가 조금 낯설었다.

나름 백준 골드5인데 애초에 IDE 자동완성 도움이 컸던지라 프로그래머스부터 켰다.

수고스럽지만 직접 타이핑해서 풀어야지..

프로그래머스에서 몇 문제 풀다 보니, 정렬 알고리즘이 필요했는데 당장 생각나는 게 거품 정렬이었다.

근데 제출하고 나니까 몇몇 테케에서 시간초과가 뜨더라.

거품 정렬이 느린 건 알고 있었다.

분명 더 효율적인 정렬 방법이 있던 거로 아는데 기억이 안 난다.

그러다 문득 그냥 Arrays.sort() 쓰면 되지 않나 싶은 마음에 써보았다.

바로 통과되더라.

Arrays.sort()

갑자기 궁금해졌다.

Arrays.sort()는 내부적으로 어떤 동작 방식을 가지고 있을까?

어떤 정렬 방식을 취하길래 더 빠른 거지?

한창 알고리즘 문제 풀 때 분명 많이 쓴 함수일 텐데, 기억이 안 나는 건지 안 찾아본 건지 모르겠다.

참고로 Arrays.sort()는 *데이터 타입에 따라 다른 정렬 알고리즘을 사용한다.

*오버로딩 되어 있기 때문이다.

int[] 같은 기본형 데이터 타입에 대해 듀얼 피봇 퀵 정렬을 사용한다.

퀵 정렬을 개선한 알고리즘이다.

두 개의 피봇을 사용하여 배열을 세 부분으로 나누어 정렬한다.

시간복잡도는 평균 O(n log n)이고, 최악의 경우 O(n^2)를 가진다.
공간 복잡도는 O(log n)이다.

Integer[] 같은 참조형 데이터 타입에 대해 팀 정렬을 사용한다.

병합 정렬 + 삽입 정렬의 하이브리드 알고리즘이다.

거의 무적이라고 생각하면 된다.

시간복잡도는 O(n log n)을 가진다.
공간복잡도는 O(n)이다.

듀얼 피봇 퀵 정렬의 경우 비안정 정렬이나, 팀 정렬의 경우 안정 정렬이다.

웬만한 실무에서도 정렬 함수를 직접 구현하기보다 Arrays.sort()를 쓰는 게 훨씬 낫다.

최적화된 함수를 쓰자.

어차피 가독성도 이게 훨씬 좋다.