정렬, Arrays.sort()와 Collections.sort() 뭐가 다를까?

 

Java 정렬 : Arrays.sort()와 Collections.sort()는 뭐가 다를까?

 

 

Arrays.sort()      → 배열을 정렬할 때 사용
Collections.sort() → List를 정렬할 때 사용

 

즉, 핵심은 내가 지금 정렬하려는 대상이 배열인지, 리스트인지를 먼저 확인하는 것이다.

---

1. Arrays.sort()는 배열을 정렬할 때 사용한다

Arrays.sort()는 배열을 정렬할 때 사용한다.

예를 들어 이런 배열이 있을 때:

int[] arr = {3, 1, 2};

정렬은 이렇게 한다.

Arrays.sort(arr);

전체 코드는 다음과 같다.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 1, 2};

        Arrays.sort(arr);

        System.out.println(Arrays.toString(arr));
    }
}

결과는 다음과 같다.

[1, 2, 3]

기본적으로 오름차순으로 정렬된다.

---

2. Arrays.sort()를 사용할 수 있는 것들

Arrays.sort()는 이름 그대로 배열에 사용한다.

예를 들면 이런 것들이다.

int[] numbers = {3, 1, 2};
String[] words = {"banana", "apple", "carrot"};
Integer[] nums = {3, 1, 2};
char[] chars = {'c', 'a', 'b'};

이런 배열들은 모두 Arrays.sort()로 정렬할 수 있다.

Arrays.sort(numbers);
Arrays.sort(words);
Arrays.sort(nums);
Arrays.sort(chars);

여기서 중요한 점은 int[] 같은 기본형 배열도 정렬할 수 있다는 것이다.

---

3. Collections.sort()는 List를 정렬할 때 사용한다

반대로 Collections.sort()는 배열이 아니라 List를 정렬할 때 사용한다.

예를 들어 ArrayList가 있다면:

List<Integer> list = new ArrayList<>();

list.add(3);
list.add(1);
list.add(2);

정렬은 이렇게 한다.

Collections.sort(list);

전체 코드로 보면 다음과 같다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();

        list.add(3);
        list.add(1);
        list.add(2);

        Collections.sort(list);

        System.out.println(list);
    }
}

결과는 다음과 같다.

[1, 2, 3]

Collections.sort()도 기본은 오름차순이다.

---

4. 제일 중요한 차이

정리하면 가장 큰 차이는 이것이다.

구분Arrays.sort()Collections.sort()

정렬 대상	배열	List
예시	int[], String[], Integer[]	List<Integer>, List<String>
기본형 배열	가능	불가능
기본 정렬	오름차순	오름차순
원본 변경	원본 배열이 바뀜	원본 리스트가 바뀜

그래서 아래처럼 사용하면 안 된다.

int[] arr = {3, 1, 2};

Collections.sort(arr); // 불가능

Collections.sort()는 List를 정렬하는 메서드이기 때문이다.

반대로 이것도 안 된다.

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));

Arrays.sort(list); // 불가능

Arrays.sort()는 배열을 정렬하는 메서드라서 List에는 사용할 수 없다.

---

5. 둘 다 원본이 바뀐다

이 부분도 기억해야 한다.

Arrays.sort()와 Collections.sort()는 둘 다 원본 자체를 정렬한다.

예를 들어 배열을 정렬하면:

int[] arr = {3, 1, 2};

Arrays.sort(arr);

System.out.println(Arrays.toString(arr));

결과는 다음과 같다.

[1, 2, 3]

arr 자체가 정렬된 상태로 바뀐다.

리스트도 마찬가지다.

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));

Collections.sort(list);

System.out.println(list);

결과:

[1, 2, 3]

list 자체가 정렬된 상태로 바뀐다.

그래서 원본을 보존해야 하는 문제라면 복사본을 만들어야 한다.

int[] copied = arr.clone();
Arrays.sort(copied);

리스트라면 이렇게 복사할 수 있다.

List<Integer> copied = new ArrayList<>(list);
Collections.sort(copied);

지난번 K번째수 문제에서도 비슷한 실수를 했다.
원본 배열을 계속 기준으로 사용해야 하는데, 잘라낸 배열을 다시 array에 대입하면서 기준 배열이 바뀌었다.
정렬 문제에서는 원본을 바꿔도 되는지 먼저 확인하는 습관이 필요할 것 같다.

---

6. 내림차순 정렬은 조금 다르다

오름차순은 간단하다.

Arrays.sort(arr);
Collections.sort(list);

그런데 내림차순은 자료형에 따라 조금 다르다.

---

Integer[] 배열 내림차순

Integer[] 같은 객체 배열은 Collections.reverseOrder()를 사용할 수 있다.

Integer[] arr = {3, 1, 2};

Arrays.sort(arr, Collections.reverseOrder());

System.out.println(Arrays.toString(arr));

결과:

[3, 2, 1]

---

int[] 배열 내림차순

하지만 int[]는 기본형 배열이라 아래 코드는 사용할 수 없다.

int[] arr = {3, 1, 2};

Arrays.sort(arr, Collections.reverseOrder()); // 불가능

이럴 때는 보통 오름차순 정렬 후 뒤에서부터 사용한다.

int[] arr = {3, 1, 2};

Arrays.sort(arr);

for (int i = arr.length - 1; i >= 0; i--) {
    System.out.print(arr[i] + " ");
}

출력:

3 2 1

배열 자체를 내림차순으로 바꾸고 싶다면 직접 뒤집어도 된다.

int left = 0;
int right = arr.length - 1;

while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;

    left++;
    right--;
}

---

List 내림차순

리스트는 비교적 간단하다.

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));

Collections.sort(list, Collections.reverseOrder());

System.out.println(list);

결과:

[3, 2, 1]

또는 이렇게도 가능하다.

list.sort(Collections.reverseOrder());

---

7. Comparator로 정렬 기준 바꾸기

정렬은 꼭 숫자 오름차순만 있는 게 아니다.
문자열 길이 기준, 2차원 배열의 특정 원소 기준 등 문제에 따라 정렬 기준을 직접 정해야 하는 경우가 많다.

문자열 배열을 길이 기준으로 정렬하면:

String[] words = {"banana", "kiwi", "apple"};

Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));

System.out.println(Arrays.toString(words));

결과:

[kiwi, apple, banana]

리스트도 비슷하다.

List<String> words = new ArrayList<>(Arrays.asList("banana", "kiwi", "apple"));

Collections.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));

System.out.println(words);

결과:

[kiwi, apple, banana]

Java 8 이후에는 list.sort()를 사용할 수도 있다.

words.sort((a, b) -> Integer.compare(a.length(), b.length()));

---

8. 2차원 배열 정렬은 Arrays.sort()를 사용한다

코딩테스트에서 구간 문제를 풀 때 2차원 배열 정렬을 자주 보게 된다.

예를 들어 다음 배열이 있다.

int[][] arr = {
    {3, 4},
    {1, 2},
    {2, 5}
};

첫 번째 값 기준으로 정렬하려면:

Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));

두 번째 값 기준으로 정렬하려면:

Arrays.sort(arr, (a, b) -> Integer.compare(a[1], b[1]));

내림차순은 비교 순서를 바꾼다.

Arrays.sort(arr, (a, b) -> Integer.compare(b[1], a[1]));

이 부분은 구간 정렬 문제에서 자주 나올 것 같아서 익숙해져야겠다.

---

9. a - b 비교는 조심하기

Comparator를 작성할 때 이런 코드를 자주 보게 된다.

Arrays.sort(arr, (a, b) -> a[0] - b[0]);

작은 숫자에서는 문제가 없어 보이지만, 값의 범위가 크면 오버플로우가 날 수 있다.

그래서 안전하게 쓰려면 Integer.compare()를 사용하는 게 좋다.

Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));

내림차순은 이렇게 작성한다.

Arrays.sort(arr, (a, b) -> Integer.compare(b[0], a[0]));

앞으로 Comparator를 쓸 때는 습관적으로 Integer.compare()를 쓰는 게 좋을 것 같다.

---

10. 시간복잡도

정렬을 사용할 때는 시간복잡도도 같이 생각해야 한다.

메서드시간복잡도

Arrays.sort()	O(N log N)
Collections.sort()	O(N log N)

대부분의 코딩테스트 문제에서는 정렬을 사용하면 O(N log N) 정도로 생각하면 될 것 같다.

입력 크기가 크고 완전탐색이 어려운 경우에는, 정렬 후 한 번 순회하면서 답을 구할 수 있는지 고민해보면 좋다.

---

11. 최종 정리

마지막으로 한 번에 정리하면 다음과 같다.

상황사용 방법

int[], String[], Integer[] 정렬	Arrays.sort()
int[][] 정렬	Arrays.sort(arr, Comparator)
List<Integer>, List<String> 정렬	Collections.sort()
Java 8 이후 List 정렬	list.sort()
int[] 내림차순	오름차순 정렬 후 뒤에서부터 사용
Integer[] 내림차순	Arrays.sort(arr, Collections.reverseOrder())
List 내림차순	Collections.sort(list, Collections.reverseOrder())
정렬 기준 변경	Comparator 사용

---

마무리

이번에 Arrays.sort()와 Collections.sort()를 정리하면서 가장 크게 이해한 점은 이거다.

Arrays.sort()는 배열용
Collections.sort()는 리스트용

둘 다 정렬 메서드이지만, 대상이 다르다.
그리고 둘 다 원본 자체를 바꾼다.

앞으로 정렬 문제를 풀 때는 먼저 이렇게 확인해야겠다.

1. 내가 정렬하려는 게 배열인가, 리스트인가?
2. 원본을 바꿔도 되는가?
3. 오름차순인가, 내림차순인가?
4. 직접 정렬 기준을 만들어야 하는가?

이 기준만 잡아도 Arrays.sort()와 Collections.sort()를 헷갈리지 않고 사용할 수 있을 것 같다.