Java 정렬

Array 정렬

배열의 정렬은 Java.util.Arrays의 sort 정적 메서드를 사용한다.

기본 자료형 배열 정렬

int, double, float와 같은 기본 자료형 배열은 오름차순으로 정렬된다. 만약 내림차순으로 정렬하고 싶다면 wrapper class로 변환 후 객체 배열을 정렬하는 방법을 사용하자.

import java.io.*;
import java.lang.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {3,5,6,4,1,3};
        Arrays.sort(arr);
        for(int num : arr) System.out.print(num + " ");
    }
}

 

객체 배열 정렬

객체 배열 정렬에는 두 가지 방법이 있다. 첫 번째로 Comparable 인터페이스를 구현한 객체의 compareTo 메서드를 사용해 정렬한다. 두 번째로 Comparator 객체를 인자로 넣고 Comparator 객체의 compare 메서드를 사용해 정렬한다.

 

1. compareTo 메서드 사용 (Comparable 인터페이스 구현 필요)

wrapper 클래스와 String 클래스는 Comparable 인터페이스를 이미 구현하고 있다.

import java.io.*;
import java.lang.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] arr = {"a", "b", "c", "d"};
        Arrays.sort(arr); //오름 차순 정렬, compareTo 메서드 사용
        for(String c : arr) System.out.print(c + " ");
    }
}

2. Comparator 객체 사용

import java.io.*;
import java.lang.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] arr = {"aaaa", "bacd", "abcd", "abcde"};

        //내림 차순 정렬
        Arrays.sort(arr, Collections.reverseOrder());
        for(String c : arr) System.out.print(c + " ");
        
        //문자열의 길이가 긴 순서대로, 길이가 같다면 사전 순의 역으로 정렬
        Arrays.sort(arr, (String a, String b)-> {
            if(a.length() == b.length()) return b.compareTo(a);
            return b.length() - a.length();
        });
        for(String c : arr) System.out.print(c + " ");
    }
}

List 정렬

List Collection의 정렬은 Collections.sort 정적 메서드를 사용거나 List Collection의 sort 메서드를 사용한다. 객체 배열을 정렬했을 때와 마찬가지로 List 원소 객체의 compareTo 메서드를 사용해 정렬하거나 Comparator 객체를 넣어 Comparator 객체의 compare 메서드를 사용해 정렬한다.

//Sorts the specified list into ascending order, according to the natural ordering of its elements.
static <T extends Comparable<? super T>> 		sort(List<T> list)

//Sorts the specified list according to the order induced by the specified comparator.
static <T> void 								sort(List<T> list, Comparator<? super T> c)

Java의 비교 함수

정리하자면 배열, 리스트같은 리스트 기반 자료구조를 프로그래머가 원하는 기준으로 정렬하는 방법은 두 가지이다.

1. 객체의 compareTo 메서드로 정렬 (Comparable 인터페이스 상속 필요)
2. Comparator 객체를 넣어 Comparator 객체의 compare 메서드로 정렬

//Compares this object with the specified object for order.
int compareTo(T o)

//Compares its two arguments for order
int compare (T o1, T o2)

compareTo, compare 같은 비교 함수는 정렬의 기준으로 사용된다. 공식 문서에 따르면 compareTo, compare 메서드는 다음의 조건을 만족해야한다.

 

compareTo : 객체가 지정된 객체(인자)보다 순서적으로 작거나, 같거나, 큰 경우 각각 음수, 제로, 양수 값을 리턴한다. 여기서 지정된 객체보다 작다라는 말은 정렬 시 객체가 지정된 객체보다 앞에 나옴을 뜻한다. 즉 정렬 시 지정된 객체보다 앞에 나와야 한다면 음수가 리턴되어야한다. sgn은 음수, 제로, 양수 값에 따라 각각 -1, 0, 1을 리턴하는 함수이다. 

1. 모든 x,y에 대해 sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) 성립
2. 모든 x,y,z에 대해 x.compareTo(y) > 0 && y.compareTo(z) > 0 이면 x.compareTo(z) > 0성립 
3. 모든 x,y,z에 대해 x.compareTo(y) == 0 이면 sgn(x.compareTo(z)) == sgn(y.compareTo(z)) 성립
4. (필수X, 권고 사항) (x.compareTo(y)==0) == (x.equals(y)) 성립

compare : 첫번째 객체가 두번째 객체보다 순서적으로 작거나, 같거나, 큰 경우 각각 음수, 제로, 양수 값을 리턴한다.

1. 모든 x,y에 대해 sgn(compare(x, y)) == -sgn(compare(y, x)) 성립
2. 모든 x,y,z에 대해((compare(x, y) > 0) && (compare(y, z) > 0)) 이면 compare(x, z) > 0 성립 
3. 모든 x,y,z에 대해 compare(x, y) == 0 이면 sgn(compare(x, z)) == sgn(compare(y, z)) 성립
4. (필수X, 권고 사항) (compare(x, y)==0) == (x.equals(y)) 성립

비교함수가 위 조건을 만족하지 않는다면 자바의 정렬 알고리즘은 두 객체간의 순서를 결정할 수 없어 오류를 던진다.

C++, Strict Weak Ordering 

종만북을 보면 C++ 비교 함수는 strict weak ordering을 만족해야한다고 나온다. 다음의 조건들을 만족하면 strict weak ordering을 만족하는 것으로 본다. F는 비교함수이다. 

1. 비반사성(irreflexivity) : 모든 x에 대해 F(x,x)는 거짓
2. 비대칭성(asymmetry) : 모든 x,y에 대해 F(x,y)가 참이면 F(y,x)는 거짓
3. 전이성(transitivity) : 모든 x,y,z에 대해 F(x,y)가 참이고 F(y,z)가 참이면 F(x,z)는 참
4. 상등 관계의 전이성(transitivity of equivalence) : 모든 x,y에 대해 F(x,y)와 F(y,x)가 거짓이면 x=y, 모든 x,y,z에 x=y, y=z이면 x=z

F를 이항 연산자 <로 보면 위 조건들을 모두 만족한다. 때문에 C++의 비교함수는 보통 < 연산자로 작성한다. C++의 비교함수는 bool(boolean) 리턴하므로 Java의 비교 함수가 만족해야하는 조건과 다르다.

 

참고)

https://tanjim131.github.io/2020-05-22-strict-weak-ordering/

https://docs.oracle.com/javase/8/docs/api/