[JAVA] List 정렬하기 (ArrayList, LinkedList 등)

 

 

 

List를 정렬하는 방법

Collections.sort()

List.sort() - Java 8 이후

 

 

 

 

 

정렬 기준 설정

Comparable - compareTo 구현

Comparator - compare 구현

 

 

 

 

 

 

 

 

List를 정렬하는 방법

 

1. Collections.sort()

public static void sort(List<T> list)
public static void sort(List<T> list, Comparator<? super T> c)

 

// 오름차순으로 정렬
Collections.sort(list);

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

// 대소문자 구분없이 오름차순
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);

// 대소문자 구분없이 내림차순
Collections.sort(list, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));

 

 

 

 

 

 

 

 

2. List.sort()

default void sort(Comparator<? super E> c)

 

// 오름차순으로 정렬
list.sort(Collections.naturalOrder());


// 내림차순으로 정렬
list.sort(Collections.reverseOrder());


// 대소문자 구분없이 오름차순 정렬
list.sort(String.CASE_INSENSITIVE_ORDER);


// 대소문자 구분없이 내림차순 정렬
list.sort(Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

정렬 기준 설정

 

1. Comparable 구현

Collections.sort() 메소드는 객체를 정렬할 때 해당 객체의 Comparable을 구현한 compareTo() 메소드를 참조하여 정렬 순서를 결정합니다.

 

따라서 정렬할 객체가 Comparable interface를 구현하고 compareTo() 메소드 안에 정렬 기준이 정의된다면 Collections.sort() 메소드를 사용하여 객체를 정렬할 수 있습니다.

 

 

compareTo 구현방법

현재 인스턴스< 비교대상인 인스턴스 $\to$ 리턴값이 음수
현재 인스턴스 > 비교대상인 인스턴스 $\to$ 리턴값이 양수 
현재 인스턴스 == 비교대상인 인스턴스 $\to$ 리턴값이 0

 

 

참고

 

 

 

 

사용

//list는Comparable를 구현한 객체타입을 저장한 List

//오름차순으로 정렬
Collections.sort(list);

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

 

 

 

예시

ArrayList<Fruit> list = new ArrayList<>();

//오름차순으로 정렬
Collections.sort(list);

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


class Fruit implements Comparable<Fruit> {
    private String name;
    private int price;
    public Fruit(String name, int price) {
        this.name = name;
        this.price = price;
    }
    @Override
    public int compareTo(Fruit fruit) {
        if (fruit.price < price) {
            return 1;
        } else if (fruit.price > price) {
            return -1;
        }
        return 0;
    }
}

 

 

 

 

 

 

 

2. Comparator 구현

사용자가 직접 Comparator interface를 구현(implements)하여 Comparator를 만들 수 있다.

이 Comparator는 Collections.sort() 또는 List.sort() 메소드의 파라미터로 전달되어 정렬의 기준이 된다.

Comparator을 구현하기 위해서는 compare 메소드를 재정의 해야하는데 방법은 다음과 같다.

 

compare 구현방법

 

오름차순으로 정렬

compare()메소드의
'첫번째 파라미터 > 두번째 파라미터' 이면 양수
'첫번째 파라미터 < 두번째 파라미터' 이면 음수
같으면 0 을 리턴

 

내림차순이라면면 양수와 음수를 반대로 리턴하면 된다

 

 

 

 

사용

import java.util.*;

public class Test {
    public static void main(String[] args) {
        // ArrayList 준비
        ArrayList<Fruit> list = new ArrayList<>();
        list.add(new Fruit("Apple", 2000));
        list.add(new Fruit("Orange", 3000));
        list.add(new Fruit("Banana", 1000));
        System.out.println("원본 : " + list);


        // price순 오름차순으로 정렬
        Collections.sort(list, new FruitPriceComparator());
        System.out.println("price 순 오름차순 : " + list);


        // price순 내림차순으로 정렬
        Collections.sort(list, new FruitPriceComparator().reversed());
        System.out.println("price 순 내림차순 : " + list);


        // name순 오름차순으로 정렬
        Collections.sort(list, new FruitNameComparator());
        System.out.println("price 순 오름차순 : " + list);

        // name순 내림차순으로 정렬
        Collections.sort(list, new FruitNameComparator().reversed());
        System.out.println("price 순 내림차순 : " + list);


        list.sort(new FruitPriceComparator());
        System.out.println("price 순 오름차순 : " + list);

        list.sort(new FruitPriceComparator().reversed());
        System.out.println("price 순 내림차순 : " + list);

        list.sort(new FruitNameComparator());
        System.out.println("price 순 오름차순 : " + list);

        list.sort(new FruitNameComparator().reversed());
        System.out.println("price 순 내림차순 : " + list);
    }
}

class FruitPriceComparator implements Comparator<Fruit> {
    @Override
    public int compare(Fruit f1, Fruit f2) {
        if (f1.price > f2.price) {
            return 1;
        } else if (f1.price < f2.price) {
            return -1;
        }
        return 0;
    }
}

class FruitNameComparator implements Comparator<Fruit> {
    @Override
    public int compare(Fruit f1, Fruit f2) {
        return f1.name.compareTo(f2.name);
    }
}

class Fruit {
    String name;
    int price;
    public Fruit(String name, int price) {
        this.name = name;
        this.price = price;
    }
    @Override
    public String toString() {
        return "[ " + this.name + ": " + this.price + " ]";
    }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

참고 - Collections.sort와 Arrays.sort 차이점

 

Arrays.sort()는 Dual-Pivot Quicksort를 사용하고

Collections.sort()는 merge sort와 insert sort를 합친 timsort를 사용합니다.

 

Quick sort는 배열에서 좋은 성능을 보이지만 stable하지 않아서 stable이 필요한 Object에는 Collections.sort()가 많이 쓰입니다.

 

 

 

 

 

 

Timsort

stable(안정적, 요소가 삽입된 순서 유지)하고

adaptive(배열 사이즈가 작으면 알고리즘을 다르게 적용)한

hybrid(병합 정렬과 삽입 정렬에서 파생) 알고리즘입니다.

 

• 거의 다 정렬되어 있는 sequence에 대해서는 $O(N)$의 성능을 보입니다.
• 부분적으로 정렬되어 있는 sequence에 대해서는 $O(N\;logN)$ 이상의 성능을 보입니다.
• 정렬되어있지 않는 sequence에 대해서도 $O(N\;logN)$의 성능을 보장합니다.

 

 

 

 

복잡도Big O Notation

최선 시간 복잡도	O(n)
평균 시간 복잡도	$O(n \; logn)$
최악 시간 복잡도	$O(n\; logn)$
공간 복잡도	$O(\frac{n}{2})$

 

 

 

 

 

 

 

Reference

[Java] ArrayList 정렬하기 (오름차순, 내림차순, 사용자 정의)

자바 [JAVA] - Comparable 과 Comparator의 이해

[Java] 정렬, Collections.sort와 Arrays.sort 차이점

Naver D2 Timsort 분석기 | SUMFIのBlog

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

https://d2.naver.com/helloworld/0315536

https://brandpark.github.io/java/2021/01/06/arrays_sort2.html

[ JAVA ] Arrays.sort()의 내부 동작(2) - 자바니또의 Tech선물