프로그래밍을 하다보면 DB 조회 시에 정렬해서 조회해오는 방법도 있고, 애플리케이션 레벨에서 정렬해야 할 때도 있습니다.

오늘은 애플리케이션에서 배열, 리스트, 맵, 셋에 대하여 각각 오름차순, 내림차순 정렬하는 방법에 대해서 알아보도록 하겠습니다.

1. 배열 정렬하기

우선 아래와 같이 int 배열이 있다고 가정해보겠습니다.

int[] arr = new int[] { 5, 1, 89, 255, 7, 88, 200, 123, 66 };

배열의 정렬은 java.util.Arrays 클래스에 있는 sort() 메서드를 이용하여 정렬할 수 있습니다.

이 메서드를 이용하면 모든 primitive 타입에 대한 정렬이 가능합니다. 물론 원시타입이 아닌 Object[] 도 정렬이 가능합니다.

int[] arr = new int[] { 5, 1, 89, 255, 7, 88, 200, 123, 66 };
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));

Arrays.sort(배열) 호출을 하면 인자로 넘겨준 배열을 정렬해줍니다. 

그리고 출력을 해보면 아래와 같이 잘 정렬이 된 것을 확인할 수 있습니다.

[1, 5, 7, 66, 88, 89, 123, 200, 255]

그럼 이 메서드가 내부적으로 사용하는 정렬 알고리즘은 어떤 것일까요?

Java8 문서에는 듀얼 피봇 퀵소트(Dual-Pivot Quick Sort) 알고리즘을 사용한다고 나와있습니다.

듀얼 피봇 퀵소트는 모든 데이터 셋에 대해서 O(n log(n)) 의 퍼포먼스를 보이고 일반적으로 기존의 One-Pivot 퀵소트 정렬보다 빠르다고 합니다.

Java7 문서, Java14 문서에도 동일한 알고리즘을 사용하는 것으로 나와있습니다.

1.1 부분정렬

위 예제는 배열의 전체 요소를 정렬하는 반면 배열의 일부분만 정렬을 할 수도 있습니다.

일부분만 정렬할 때는 Arrays.sort(int[] a, int fromIndex, int toIndex) 메서드를 이용하시면 됩니다.

int[] arr = new int[] { 5, 1, 89, 255, 7, 88, 200, 123, 66 };
Arrays.sort(arr, 0, 4);
System.out.println(Arrays.toString(arr));

출력을 해보면 아래와 같이 0번 인덱스부터 3번 인덱스까지(4는 exclude입니다) 정렬이 된 것을 확인할 수 있습니다.

[1, 5, 89, 255, 7, 88, 200, 123, 66]

1.2 병렬 정렬 (ParallelSort)

Arrays.sort()가 싱글쓰레드로 돌아간다면 Arrays.parallelSort()는 멀티쓰레드로 동작을 합니다. parallelSort는 배열을 sub-array로 나눈 뒤 각각을 별도의 쓰레드에서 처리를 하고 각 쓰레드에서는 Arrays.sort()를 실행하여 정렬을 하게 됩니다.

Arrays.parallelSort 의 결과는 당연히 Arrays.sort의 결과와 동일합니다. 멀티쓰레딩을 이용했느냐의 차이만 존재할 뿐입니다.

참고로 Arrays.parallelSort 도 부분정렬이 가능합니다. Arrays.parallelSort (int [] a, int fromIndex, int toIndex);

2. List 정렬하기

리스트를 정렬할 때는 java.util.Collections.sort(List<T> list) 메서드를 이용하는 방법이 있습니다.

int[] arr = new int[] { 5, 1, 89, 255, 7, 88, 200, 123, 66 };
List<Integer> toSortList = Ints.asList(arr);    // int[]을 Integer[]로 변환 (구글 guava 라이브러리 이용) 
Collections.sort(toSortList);

출력 결과는 Arrays.sort()를 사용한 것과 동일합니다.

기본적으로 오름차순으로 정렬을 합니다. 만약 내림차순으로 정렬하고 싶다면 comparator를 인자로 전달받는 sort​(List list, Comparator c) 메서드를 이용할 수 있습니다.

그리고 너무나도 기본적인 얘기지만 정렬을 하려면 두 요소(element)를 비교할 수 있어야 하기 때문에 리스트 내의 모든 요소들이 Comparable 인터페이스를 구현하고 있어야 합니다.

Collections.sort(List<T> list) 는 merge sort 알고리즘을 이용하여 정렬을 합니다. List.sort(Comparator c)에서 제공하는 기본 알고리즘과는 조금 다르다고 합니다만, 더 안좋게 변형된 알고리즘을 사용하는 건 아니겠죠. 그리고 기본적으로 List.sort()에서 사용하는 merge sort는 어느정도 부분 정렬이 되어있는 데이터에 대해서는 n log(n) 보다 훨씬 적은 횟수만 비교하며(거의 정렬이 되어있는 상태라면 거의 n번의 비교만으로도 정렬 가능), 랜덤하게 섞여있는 데이터 셋에 대해서는 전통적인 merge sort의 퍼포먼스를 낸다고 합니다. Java14 Collections.sort() 참고하시면 좋을 것 같습니다.

만약 역순(내림차순)으로 정렬을 하고 싶으면 Collections.sort(List list, Comparator c) 메서드를 이용하면 됩니다.

// 내림 차순 정렬
Collections.sort(list, Comparator.reverseOrder());

자바에서는 내림차순 정렬을 위해 Comparator.reverseOrder() 메서드를 통해 기본 comparator를 제공해주고 있습니다. 

3. Set 정렬하기

Set은 기본적으로 순서를 보장하지 않습니다. 하지만 LinkedHashSet은 순서를 보장하죠. 따라서 Set을 정렬한다는 것은 이 LinkedHashSet 처럼 순서를 보장하는 set 구현체에 대한 얘기입니다.

Set을 정렬할 때도 Collections.sort()를 이용합니다. 하지만 해당 메서드는 List만을 인자로 전달받고 있기 때문에 Set을 정렬하려면 List로 변경하는 작업이 필요합니다.

Set<Integer> set = new LinkedHashSet<>(Ints.asList(arr));
System.out.println(set);    // 정렬하기 전 출력

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

System.out.println(set);    // 정렬 후 출력

위에서 보듯이 list로 변환 후 다시 set으로 변환하여 정렬을 할 수 있습니다.

4. Map 정렬하기

Map은 아시다시피 key와 value 쌍으로 이루어진 자료구조입니다. 따라서 Map을 정렬할 때는 key를 기준으로 정렬하는 방법과 value를 기준으로 정렬하는 방법, 두 가지 방법이 있습니다. 또한, Map도 Set과 마찬가지로 HashMap 같은 경우는 순서와는 무관한 자료구조이기 때문에 정렬을 위해서는 LinkedHashMap을 이용해야 합니다.

우선 key를 기준으로 정렬하는 방법에 대해서 알아보겠습니다. Map을 정렬할 때도 List, Set과 마찬가지로 Collections.sort(List list) 메서드를 이용할 수 있습니다. 따라서 list로 변환을 해주어야 하죠. 그리고 정렬 후에는 순서의 보장을 위해 list를 LinkedHashMap으로 변환해주어야 합니다. 또한 List.sort(Comparator c)를 이용할 수도 있습니다. 예제에서 두 가지 방법에 대해 모두 확인해보도록 하겠습니다.

// 기본 데이터 셋
HashMap<Integer, String> map = new HashMap<>();
map.put(5, "Orange");
map.put(8, "Apple");
map.put(2, "WaterMelon");
map.put(13, "Pear");
map.put(9, "Grape");
map.put(4, "Banana");


// key, value 를 모두 가져오기 위해서 entrySet()을 리스트로 변환
List<Map.Entry<Integer, String>> entries = new ArrayList<>(map.entrySet());

// 1. List.sort 를 이용하는 방법
entries.sort(Comparator.comparing(Map.Entry::getKey));

// 2. Collections.sort 를 이용하는 방법
Collections.sort(entries, Comparator.comparing(Map.Entry::getKey));

// 정렬된 데이터를 LinkedHashMap에 저장
Map<Integer, String> sortedByKey = new LinkedHashMap<>();
for (Map.Entry<Integer, String> entry : entries) {
	sortedByKey.put(entry.getKey(), entry.getValue());
}

// 정렬된 내용 출력
System.out.println(sortedByKey);

정렬할 때 List.sort(Comparator c) 와 Collections.sort(List list)를 이용하는 방법을 모두 소개해드렸습니다.

여기서 사용한 Comparator.comparing() 메서드는 comparator를 반환하는 메서드입니다. Comparator.comparing(Map.Entry::getKey) 는 Map의 key 값을 비교하는 comparator를 만들어주죠.

위 코드에서 출력되는 내용은 아래왁 같습니다.

{2=WaterMelon, 4=Banana, 5=Orange, 8=Apple, 9=Grape, 13=Pear}

key 값 순서대로 정렬이 된 것을 확인할 수 있습니다.

그럼 이번에는 위 코드를 조금 수정하여 value를 기준으로 정렬을 해보도록 하겠습니다.

// 1. List.sort 를 이용하는 방법
entries.sort(Comparator.comparing(Map.Entry::getValue));

// 2. Collections.sort 를 이용하는 방법
Collections.sort(entries, Comparator.comparing(Map.Entry::getValue));

Comparator.comparing() 메서드의 인자로 key가 아닌 value 값을 넘겨주기만 하면 됩니다.

수정된 코드 실행 결과는 다음과 같습니다.

{8=Apple, 4=Banana, 9=Grape, 5=Orange, 13=Pear, 2=WaterMelon}

value값으로 넣어주었던 과일명 순으로 정렬이 되어 출력된 것을 확인할 수 있습니다.

5. 커스텀 객체 정렬하기

이번에는 커스텀 객체를 정렬하는 방법에 대해 알아보겠습니다. 사실 커스텀 객체를 정렬하는 방법이라고 따로 있는건 아닙니다. 이미 위에서 설명드린 내용중에 comparator를 이용하는 방법을 이용해야 합니다.

일단 쇼핑몰에 판매중인 상품에 대한 객체 정의를 해보겠습니다.

@Getter
@Setter
@AllArgsConstructor
class Product {
    String name;        // 상품 명
    int price;          // 상품 가격
    float sellerRating; // 판매자 평점
    
    @Override
    public String toString() {
    	return "{" + this.name + ", " + price + ", " + sellerRating + "}";
    }
}

이제 이 객체를 리스트로 만들어 가격, 판매자 평점을 기준으로 각각 오름차순, 내림차순으로 정렬을 해보도록 하겠습니다.

// 기본 데이터 셋
List<Product> data = new ArrayList<>(Arrays.asList(
    new Product("Apple", 100, 4.3f),
    new Product("Apple", 200, 3.3f),
    new Product("Apple", 150, 4.8f)));

// 1. List.sort 를 이용하여 가격 오름차순 정렬
data.sort(Comparator.comparing(Product::getPrice));
System.out.println("\n1. List.sort 를 이용하여 가격 오름차순 정렬");
System.out.println(data);

// 2. List.sort 를 이용하여 가격 내림차순 정렬
data.sort(Comparator.comparing(Product::getPrice, Comparator.reverseOrder()));
System.out.println("\n2. List.sort 를 이용하여 가격 내림차순 정렬");
System.out.println(data);

// 3. Collections.sort 를 이용하여 판매자 편점 오름차순 정렬
Collections.sort(data, Comparator.comparing(Product::getSellerRating));
System.out.println("\n3. Collections.sort 를 이용하여 판매자 편점 오름차순 정렬");
System.out.println(data);

// 4. Collections.sort 를 이용하여 판매자 편점 내림차순 정렬
Collections.sort(data, Comparator.comparing(Product::getSellerRating, Comparator.reverseOrder()));
System.out.println("\n4. Collections.sort 를 이용하여 판매자 편점 내림차순 정렬");
System.out.println(data);

Product 리스트를 특정 필드를 기준으로 오름차순 내림차순으로 정렬하는 코드는 List.sort를 사용해도, Collections.sort를 사용해도 한 줄이면 됩니다. 매우 간단합니다. 내림차순으로 정렬을 하고 있을 때는 Comparator.comparing() 메서드에 Comparator.reverseOrder() 인자를 추가해주면 됩니다. 즉, Comparator.comparing(정렬기준, 정렬순서) 이렇게 사용하시면 되는거죠.

자, 이제 출력 결과를 확인해보면 다음과 같습니다.

1. List.sort 를 이용하여 가격 오름차순 정렬
[{Apple, 100, 4.3}, {Apple, 150, 4.8}, {Apple, 200, 3.3}]

2. List.sort 를 이용하여 가격 내림차순 정렬
[{Apple, 200, 3.3}, {Apple, 150, 4.8}, {Apple, 100, 4.3}]

3. Collections.sort 를 이용하여 판매자 편점 오름차순 정렬
[{Apple, 200, 3.3}, {Apple, 100, 4.3}, {Apple, 150, 4.8}]

4. Collections.sort 를 이용하여 판매자 편점 내림차순 정렬
[{Apple, 150, 4.8}, {Apple, 100, 4.3}, {Apple, 200, 3.3}]

Summary

여기까지 자바에서 정렬하는 방법에 대해서 알아보았습니다.

간략히 요약을 하면 다음과 같습니다.

배열의 정렬 -> Arrays.sort() 이용

List 정렬 -> Collections.sort(), List.sort() 이용

Set, Map 정렬 -> List로 변환 후 Collections.sort(), List.sort() 이용

기본적으로 오름차순 정렬

내림차순 정렬은 Comparator.reverseOrder() 이용