[정렬] 3. ArrayList 정렬(Sort)

1. 버블정렬 알고리즘과 2. 배열의 정렬에 이어서 3. ArrayList 정렬에 대해서도 정리해보겠습니다.

ArrayList의 정렬

javadoc에는 다음과 같이 나와있습니다. ArrayList 객체의 멤버 함수로 구현이 되어있습니다.

sort

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

Description copied from interface: List
Sorts this list according to the order induced by the specified Comparator.All elements in this list must be mutually comparable using the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the list).
If the specified comparator is null then all elements in this list must implement the Comparable interface and the elements' natural ordering should be used.This list must be modifiable, but need not be resizable.

Specified by:
sort in interface List <E>

Parameters:
c - the Comparator used to compare list elements. A null value indicates that the elements' natural ordering should be used

1. List.sort()

Java docs의 설명대로 ArrayList java 8 버전 이후로는 List 객체는 sort() 함수를 사용할 수 있다고 합니다. 따라서 아래와 같이 객체에서 바로 호출해서 사용이 가능하고, parameter로 Comparator를 넣어주는데, 오름차순인 경우에는 naturalOrder(), 내림차순이면, reverseOrder()를 사용합니다.

import java.util.*;

public class ArrayListTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        //public boolean add(E e)
        ArrayList<Integer> scores = new ArrayList<>();
        scores.add(100);
        scores.add(600);
        scores.add(200);
        scores.add(500);
        scores.add(400);
        scores.add(300);


        //public void sort(Comparator<? super E> c)
        scores.sort(Comparator.naturalOrder();
        System.out.println("1. scores: "+scores.toString()+" 오름차순 정렬");
        scores.sort(Comparator.reverseOrder());
        System.out.println("2. scores: "+scores.toString()+" 내림차순 정렬");
    }
}

Output:

1. scores: [100, 200, 300, 400, 500, 600] 오름차순 정렬
2. scores: [600, 500, 400, 300, 200, 100] 내림차순 정렬

 

2. Collections.sort()

Java 8 이전에는 Collections.sort()를 사용했습니다. Collections.sort() 메서드는 static method이므로 사용방법에 약간 차이가 있습니다.

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

import java.util.*;

public class ArrayListTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        //public boolean add(E e)
        ArrayList<Integer> scores = new ArrayList<>();
        scores.add(100);
        scores.add(600);
        scores.add(200);
        scores.add(500);
        scores.add(400);
        scores.add(300);

        //public void sort(Comparator<? super E> c)
        Collections.sort(scores);
        System.out.println("1. scores: "+scores.toString()+" 오름차순 정렬");
        Collections.sort(scores,Collections.reverseOrder());
        System.out.println("2. scores: "+scores.toString()+" 내림차순 정렬");


    }
}

Output:

1. scores: [100, 200, 300, 400, 500, 600] 오름차순 정렬
2. scores: [600, 500, 400, 300, 200, 100] 내림차순 정렬

 

3. 사용자 정의 정렬

List.sort()가 받는 Comparator를 Comprable.compareTo와 Comparator.compare 메서드를 재정의하여 사용자 정의 정렬이 가능합니다.

(1) Comparator.compare()

Comparator를 익명 클래스로 구현해서 사용자 정의 함수를 작성했습니다. 아래 코드는 ArrayList의 각 원소의 1의 자리 숫자 기준으로 정렬을 하도록 사용자 정의 함수를 작성하였습니다. Integer는 이미 compare, compareTo 메서드가 구현되어있기 때문에, Comparator를 구현해서 새로운 사용자 정의 정렬을 했습니다. 

import java.util.*;

public class ArrayListTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        //public boolean add(E e)
        ArrayList<Integer> scores = new ArrayList<>();
        scores.add(123);
        scores.add(612);
        scores.add(241);
        scores.add(526);
        scores.add(425);
        scores.add(344);

        Comparator<Integer> comparator = new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {

                return o1%10 - o2%10;  // 10으로 나눈 나머지(1의 자리수)로 비교
            }
        };
        //public void sort(Comparator<? super E> c)
        scores.sort(Comparator.naturalOrder());
        System.out.println("1. scores: "+scores.toString()+" 오름차순 정렬");
        scores.sort(Comparator.reverseOrder());
        System.out.println("2. scores: "+scores.toString()+" 내림차순 정렬");
        scores.sort(comparator);
        System.out.println("3. scores: "+scores.toString()+" 사용자 정의 정렬");

Output: 

1. scores: [123, 241, 344, 425, 526, 612] 오름차순 정렬
2. scores: [612, 526, 425, 344, 241, 123] 내림차순 정렬
3. scores: [241, 612, 123, 344, 425, 526] 사용자 정의 정렬

(2) Comparable.compareTo()

정렬 기준이 없는 객체의 경우에는 Comparable을 구현한 compareTo()를 이용해 정렬합니다.
아래의 예에서는 NumberAndSum 클래스의 sum을 기준으로 정렬하도록 만들었습니다.

public class NumberAndSum implements Comparable<NumberAndSum>{
    int[] numList;
    int sum=0;

    public int getSum() {
        return sum;
    }

    public NumberAndSum(int[] numList) {
        this.numList = numList;
        for(int n:numList) this.sum+=n;
    }

    @Override
    public int compareTo(NumberAndSum o) {
        return this.sum - o.sum;
    }
}

import java.util.*;

public class ArrayListTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        ArrayList<NumberAndSum> numberAndSums = new ArrayList<>();

        numberAndSums.add(new NumberAndSum(new int[]{1, 2, 3})); //6
        numberAndSums.add(new NumberAndSum(new int[]{6, 1, 2})); //9
        numberAndSums.add(new NumberAndSum(new int[]{2, 4, 1})); //7
        numberAndSums.add(new NumberAndSum(new int[]{5, 2, 6})); //13
        numberAndSums.add(new NumberAndSum(new int[]{3, 4, 4})); //11

        Collections.sort(numberAndSums);
        System.out.print("numberAndSums :");
        for(NumberAndSum n:numberAndSums) System.out.print(" "+n.getSum());
        System.out.println(" 사용자 정의 정렬");
    }
}

Output:

numberAndSums : 6 7 9 11 13 사용자 정의 정렬

 

정리 하기

위에서 살펴본 것처럼 ArrayList를 정렬할 때, ArrayList의 각 원소가 기본 타입 등 이미 알려진 타입의 객체로서 Comparable.compareTo()가 이미 구현되어있다면, ArrayList.sort()를 이용해 정렬할 수 있습니다.

하지만, 정렬 기준이 명확하지 않은 사용자 정의 객체는 Comparable.compareTo()를 객체에 구현해서 그 기준으로 ArrayList를 정렬할 수 있습니다.

그리고, compareTo()가 구현되어 정렬 기준이 있다면, Comparator.compare()를 별도로 구현하여 사용자가 원하는 정렬 기준에 따라 정렬하는 것도 가능합니다.