Java 정렬과 Comparator

Comparator, Comparable이란?

우선 comparator와 comparable은 둘다 인터페이스이다.

인터페이스는 추상 메소드 뿐만 아니라 일반 메소드, 생성자, 필드 등을 갖일 수 있는 추상 클래스와는 다르게 반드시 추상 메소드와, 상수만을 갖는다.

인터페이스에 대해 좀더 알아보자

인터페이스 선언

접근제어자 interface interface명 {
	public staitic 타입 명 = 값;
   
    public abstract 메소드 명(매게변수 목록);
}

인터페이스는 위와 같이 선언한다. 모든 필드는 항상 public static이며 추상 메소드는 항상 public abstarct로 선언해 주어야한다.
다만 모든 인터페이스가 항상 위와 같은 구조를 가지므로 생략이 가능하다. 생략 시 자바 컴파일러가 자동으로 추가해준다.

인터페이스는 직접 생성할 수 없고 항상 상속을 통해서만 생성 가능하다.

class 클래스명 implements 인터페이스명{ ... }

implements로 인터페이스를 상속받을 때는 반드시 abstract로 선언했던 추상 메소드를 완성시켜준다.

인터페이스의 장점은 클래스 상속과 다르게 여러개를 상속 받을 수 있다는 점이다.

class 클래스명 extend 부모클래스명 implements 인스턴스명, 인스턴스명{...}

인터페이스의 다른 장점들

1. 대규모 프로젝트 개발 시 일관되고 정형화된 개발을 위한 표준화가 가능하다
2. 클래스의 작성과 인터페이스의 구현을 동시에 진행할 수 있으므로, 개발 시간을 단축할 수 있다.
3. 클래스와 클래스 간의 관계를 인터페이스로 연결하면, 클래스마다 독립적인 프로그래밍이 가능하다.

다시 돌아와서 Comparable, Comprator 보기

Comparable 인터페이스에는 compareTo(T o) 메소드 하나가 선언되어 있다. 이 말은 우리가 만약 Comparable을 사용하고자 한다면 compareTo 메소드를 재정의(Override/구현)을 해주어야 한다는 것이다.

Comprator 인터페이스를 사용하기 위해서는 compare(T o1, T o2)를 구현해 주어야한다.

이제 사용법을 알기 전에 두 인터페이스가 어떨 때 사용하는지 알아본다.

부 인터페이스를 사용할 때는 주로 객체를 정럴할 때 사용하지만 정확히 본다면 정렬은 용도에 불과하다. 진짜 목적은 객체를 비교할 수 있게 만든다는 점이다.

본질적으로 객체는 사용자가 명확하게 기준을 정하지 않는 이상 우선순위를 결정하기 어렵다 그렇기 때문에 Comparable, Comprator을 사용한다.

Comparable, Comprator 차이점

Comparable은 자기 자신과 매개 변수 객체를 비교하는 것이고 Comprator는 주어지는 두 매개 변수 객체를 비교하는 것이다. 그렇기 때문에 Comparable 인터페이스의 comparTo(T o) 메소드는 매개 변수가 하나이고 Comprator 인터페이스의 compare(T o1, To2) 메소드는 매개 변수가 두개인 것이다.
즉 비교하는 것은 같지만 비교 대상이 다르다.

다른 차이점은 Comparable은 lang 패키지에 있어 import 할 필요가 없지만 Comprator는 util 패키지에있어 import 해주어야한다.

Comparable 사용하기

Comparable은 클래스 생성할 때 implement로 상속하며 상속 받은 클래스 내에서 반드시 comparTo 함수를 구현해야한다.

아래 코드 예시

class People implements Comparable<People> {
	int age;
    int height;
   
    People(int age, int height) {
    	this.age = age;
        this.height = height;
    }
   
    @Override
    public int compareTo(People p){
    	return this.age - o.age;
    }

}

public class Example {
	public static void main(String[] args) {
    	People p1 = new People(10, 150);
        People p2 = new People(12, 160);
    	
        int compare = p1.compareTo(p2);
       
        if(compare > 0) { ... }
        else if(compare == 0 ) { ... }
        else { ... }
    }
}

위 코드처럼 객체의 특정 필드를 기준으로 객체자신과 매개변수로 주어지는 객체를 비교할 수 있다.

Comparator 사용하기

Comparator의 특징을 보기 전에 우선 코드로 먼저 작성해보자

class People implements Comparator<People> {
	int age;
    int height;
   
    People(int age, int height) {
    	this.age = age;
        this.height = height;
    }
   
    @Override
    public int compareTo(People p){
    	return this.age - o.age;
    }

}

public class Example {
	public static void main(String[] args) {
    	People p1 = new People(10, 150);
        People p2 = new People(12, 160);
        People p3 = new People(13, 155);
        People com = new People(0, 0);
    	
        int compare1 = p1.compare(p2, p3);
        int compare2 = p2.compare(p1, p3);
        int compare3 = p3.compare(p1, p2);
       
        if(compare1 > 0) { ... }
        else if(compare == 0 ) { ... }
        else { ... }
    }
}

Comparator의 특징은 위와 같이 두 개의 객체를 비교할때 메서드를 사용한 객체에게는 아무런 영향이 없다는 것이다. 이 말은 즉 두 객체를 비교하기 위해서 어떤 객체를 사용해도 된다는 말이며 이는 일관성이 떨어진다. 그렇다고 비교만을 위한 객체를 만들면 비교할 때만 사용하는 쓸데없는 객체를 만들게 된다.

그렇기 때문에 보통 Comparator를 사용할 때는 익명 객체를 사용한다.

자바의 익명 객체

익명 객체란 말 그대로 이름이 정의되지 않은 객체를 의미한다.
익명 객체는 보통 특정 구현 부분만 따로 사용한다거나, 부분적으로 기능을 일시적으로 바꿔야 할 경우가 생길 때 사용하게 된다.

익명 객체를 생성 하는 방법은 객체를 생성할 때 구현부도 같이 작성하는 것이다.
아래 코드로 Comparator 익명 객체 사용법을 확인

class People {
	int age;
    int height;
   
    People(int age, int height) {
    	this.age = age;
        this.height = height;
    }

}

public class Example {
	public staic Comprator<People> comp = new Comprator<People>() {
    	public int compare(People o1, People o2) {
        	return o1.age - o2.age;
        }
   
    }

	public static void main(String[] args) {
    	People p1 = new People(10, 150);
        People p2 = new People(12, 160);
       
        int compare = comp.compare(p1, p2)
       
        if(compare > 0) { ... }
        else if(compare == 0 ) { ... }
        else { ... }
    }
}

위와 같이 static으로 구현해도 되지만 아래처럼 main 함수안에서 구현할 수도 있다.

	public static void main(String[] args) {
   
    	Comparator<People> comp1 = new Comparator<People>() {
			@Override
			public int compare(People o1, People o2) {
				return o1.classNumber - o2.classNumber;
			}
		}
       
    	People p1 = new People(10, 150);
        People p2 = new People(12, 160);
       
        int compare = comp1.compare(p1, p2)
       
        if(compare > 0) { ... }
        else if(compare == 0 ) { ... }
        else { ... }
    }

Comparable, Comparator와 정렬의 관계

Comparable, Comparator의 차이점과 사용방법을 알았다.

객체를 비교하기 위해 Comparable 또는 Comparator을 쓴다는 것은 곧 사용자가 정의한 기준을 토대로 비교를 하여 양수, 0, 음수 중 하나가 반환된다는 것이다.

Comparable, Comparator와 정렬의 관계를 보기전에 Java 정렬에 대해 살펴보자

Java역시 다른 언어와 마찬가지로 따로 정의하지 않으면 오름차순으로 정렬한다. 흔히 사용하는 Arrays.sort(), Collections.sort() 모두 오름차순을 기준으로 정렬이 된다.

오름차순으로 정렬되는 방법을 예로 살펴보자
배열 {1,3,2}가 있다고 해보자 정렬하기 위해서 두 수를 비교한다. idx 0과 idx 1을 comparator 코드로 봐보면
return o1 - o2 -> return 1 -3; 이다. 즉 음수가 나온다.
음수가 나오면 바꾸지 않는다.
idx 1과 idx 2를 compartor 코드로 보면
return 3 -2이다. 양수가 나온다. 양수가 나오면 두 인덱스의 수를 바꾼다.
이렇게 해서 {1,2,3}으로 정렬된다.

이렇게 compartor나 comparable을 통한 비교할때 규칙을 일반화 할 수 있다.

• 음수일 때는 바꾸지 않는다.
• 양수일 때는 바꾼다.

정렬에는 다양한 알고리즘이 있는데 정렬에서 핵심은 비교해서 바꿀지 말지 결정하는 것이다. 실제로 java에서 사용하는 Arrays.sort() 메서드는 위와 같은 규칙으로 comparator를 사용해서 교환 여부를 판단한다.

클래스 정렬 예를 및에 코드로 살펴보자

import java.util.Arrays;

class MyInteger implements Comparable<MyInteger> {
	int value;
	
	public MyInteger(int value) {
		this.value = value;
	}
	
	@Override
	public int compareTo(MyInteger o) {
		return this.value - o.value;
	}
	
}

public class Test {
	
	public static void main(String[] args) {
		
		MyInteger[] arr = new MyInteger[10];
		
		// 객체 배열 초기화 (랜덤 값으로)
		for(int i = 0; i < 10; i++) {
			arr[i] = new MyInteger((int)(Math.random() * 100));
		}
 
		// 정렬 이전
		System.out.print("정렬 전 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
		
		Arrays.sort(arr);
       
		// 정렬 이후
		System.out.print("정렬 후 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
	}
	
}
 

위 코드에서 만약 MyInteger 클래스에 compareTo 메소드가 정의 되어있지 않다면 해당 코드는 오류가 발생한다.

MyInteger 클래스를 Arrays.sort 안에서 정렬을 하면서 원소를 비교하려 하는데, 해당 클래스가 비교할 수 있는 기준이 정의되어있지 않아서 정렬 자체가 불가능한 것이다.

아래 코드는 comparator 익명 객체를 사용한 sort 방법 예제 코드이다.

import java.util.Arrays;
import java.util.Comparator;

class MyInteger {
	int value;
	
	public MyInteger(int value) {
		this.value = value;
	}
	
}

public class Test {

	static Comparator<MyInteger> comp = new Comparator<MyInteger>() {
		
		@Override
		public int compare(MyInteger o1, MyInteger o2) {
			return o1.value - o2.value;
		}
	}
   
	public static void main(String[] args) {
		
		MyInteger[] arr = new MyInteger[10];
		
		// 객체 배열 초기화 (랜덤 값으로)
		for(int i = 0; i < 10; i++) {
			arr[i] = new MyInteger((int)(Math.random() * 100));
		}
       
        // 정렬 이전
		System.out.print("정렬 전 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
		
		Arrays.sort(arr, comp);		// MyInteger에 대한 Comparator을 구현한 익명객체를 넘겨줌
       
		// 정렬 이후
		System.out.print("정렬 후 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
	}
}

위 코드를 보면 Arrays.sort() 메서드에서 매개변수로 객체 배열 뿐만 아니라 익명 객체로 구현한 comparator 객체 comp도 같이 넘겨준다.

Arrays.sort() 메소드를 살펴보자

간략하게 요약하자면, Comparator 파라미터로 넘어온 c의 비교 기준을 갖고 파라미터로 넘어온 객체배열 a을 정렬하겠다는 의미다.

Arrays.sort()를 쓸 때 Arrays.sort(array); 이런식으로 배열만 넘겨주었지만 사실은 Comparator로 구현된 객체를 파라미터로 같이 넘겨주어 Arrays.sort(array, comp); 로도 쓸 수 있다는 것이다.

내림차순은?

선행 원소가 후행 원소보다 작으면 compare 혹은 compareTo 메소드의 반환값이 음수가 나오고, 정렬 알고리즘에서는 두 원소를 비교할 때 두 원소는 오름차순 상태라는 의미이므로 두 원소가 교환되지 않는다는 것이다.

반대로 선행 원소가 후행원소보다 크면 compare 혹은 compareTo 메소드의 반환값이 양수가 나오고, 정렬 알고리즘에서는 두 원소를 비교할 때 두 원소는 내림차순 상태라는 의미이므로 두 원소가 교환된다.

즉, 정렬 알고리즘에서는 두 원소를 compare 혹은 compareTo 를 써서 양수값이 나오냐, 음수값이 나오냐에 따라 판단을 한다는 것이다.

위 방법이 오름차순이라면 내림차순으로 정렬하고 싶은 경우 두 원소를 비교한 반환값을 반대로 해주면 된다.

쉽게 말해 두 값의 차가 양수가 된다면 이를 음수로 바꿔 반환해주고, 만약 음수가 된다면 그 값을 양수로 바꾸어 반환해주면 된다는 것이다.

아래의 코드로 예를 들어본다

// 오름차순 정렬
// Comparable
public int compareTo(T o) {
	return this.value - o.value;
}
 
// Comparator
public int compare(T o1, T o2) {
	return o1.value - o2.value;
}

// 내림차순 정렬
// Comparable
public int compareTo(T o) {
	return -(this.value - o.value);
}
 
// Comparator
public int compare(T o1, T o2) {
	return -(o1.value - o2.value);
}

// 내림차순 다른 표현
// Comparable
public int compareTo(MyClass o) {
	return o.value - this.value;	// == -(this.value - o.value);
}
 
// Comparator
public int compare(Myclass o1, MyClass o2) {
	return o2.value - o1.value;		// == -(o1.value - o2.value);
}

출처 https://st-lab.tistory.com/243
(너무 정성스럽게 작성해주신 포스터다 정말 감사한 마음으로 읽었다.)

Comparable String

String의 경우 두 String간의 문자열 비교를 위해 compareTo()를 사용한다. 이 메소드가 가능했던 이유가 바로 String 클래스에 Comparable을 implements하여 compareTo() 메소드를 구현하고 있기 때문에 그렇다.

두 문자열을 Comparae하게 되면 반환 값이 어떻게 되는지 살펴본다.

public class CompareToTest{
    public static void main(String[] args){

        String str = "abcd";

        // 1) 비교대상에 문자열이 포함되어있을 경우
        System.out.println("1" + str.compareTo("abcd") );  // 0 (같은 경우는 숫자나 문자나 0을 리턴)
        System.out.println("2" + str.compareTo("ab") );  //  2
        System.out.println("3" + str.compareTo("a") );  //  3
        System.out.println("4" + "".compareTo(str) );  //  -4
        
        System.out.println("5" + str.compareTo("c") );  //  -2

        // 2) 비교대상과 전혀 다른 문자열인 경우
        System.out.println("6" + str.compareTo("zefd") );  //  -25
        System.out.println("7" + str.compareTo("zEFd") );  //  -25
        System.out.println("8" + str.compareTo("ABCD") );  //  32
    }

}

두 번째 예제인 "ab"와 세 번째 예제인 "a", 4 번째 예제인 ""를 각각 "abcd" 비교할 경우 길이(length) 차이를 반환해준다. 같은 경우는 0을 반환한다.

compareTo 메소드는 String을 비교할때 첫 글자가 같다면 위 예제처럼 길이(length) 차이를 반환해준다.

하지만 첫 글자가 다른 경우라면 아스키코드 값을 빼서 반환해준다.
5~8번 예제가 그 예시이다. c는 아스키코드 값이 a랑 2차이기 때문에 -2가 반환된다.

출처 https://mine-it-record.tistory.com/133
(String compareTo 메소드 출처)

2차원 배열 정렬 방법

2차원 배열은 1차원 배열처럼 Arrays.sort()를 사용해서 정렬 시도하면 오류가 발생한다.

자바에서 2차원 배열을 정렬하는 방법을 찾아보다가 이 포스터를 작성하게 되었다. 위에 Comparable과 Comparator은 2차원 배열 정렬 방식을 이해하기 위해 공부하게 되었다.

1. comparator 익명 객체를 사용해서 정렬

Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[0]-o2[0]; // 첫번째 숫자 기준 오름차순 {1,30}{2,10}{3,50}{4,20}{5,40}
        //return o2[0]-o1[0]; // 첫번째 숫자 기준 내림차순 {5,40}{4,20}{3,50}{2,10}{1,30}
        //return o1[1]-o2[1]; // 두번째 숫자 기준 오름차순 {2,10}{4,20}{1,30}{5,40}{3,50}
        //return o2[1]-o1[1]; // 두번째 숫자 기준 내림차순 {3,50}{5,40}{1,30}{4,20}{2,10}
    }
});

// 다중 조건 
int[][] arr2 = new int[][]{{5,40},{3,50},{1,30},{4,20},{2,10},{6,40},{6,50},{6,10},{6,20},{6,30}};

Arrays.sort(arr2, new Comparator<int[]>() { 
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[0]!=o2[0] ? o1[0]-o2[0] : o1[1]-o2[1]; // 첫번째 기준 오름차순 > 두번째 기준 오름차순  : {1,30}{2,10}{3,50}{4,20}{5,40}{6,10}{6,20}{6,30}{6,40}{6,50}
        //return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[1]-o1[1]; // 첫번째 기준 오름차순 > 두번째 기준 내림차순  : {1,30}{2,10}{3,50}{4,20}{5,40}{6,50}{6,40}{6,30}{6,20}{6,10}
    }
});

위 comparator 부분을 잘 이해했다면 이 코드를 한 번 파악하고 이해할 수 있다.

2. Lambda 사용

int[][] arr = new int[][]{{5,40},{3,50},{1,30},{4,20},{2,10}};
// 2. Lambda 사용 - Java 8이상
Arrays.sort(arr, (o1, o2) -> {
    return o1[0]-o2[0]; // 첫번째 숫자 기준 오름차순 {1,30}{2,10}{3,50}{4,20}{5,40}
});

배열 예제 출처 https://ifuwanna.tistory.com/328

이 코드가 위 Comparator를 사용한 방법과 매우 비슷한 구조를 같다는 것을 볼 수 있다.
comparator 익명 객체를 생성하는 대신 Lambda를 사용했다는 것을 추측할 수 있다.

이 코드를 살펴보기전에 Java의 Lamda식에 대해 좀더 알아본다.

Java 람다식(Lambda Expression)

람다식은 자바 8에 추가된 가장 큰 특징의 하나로 자바에서 함수형 프로그래밍 형태를 받아들인 결과이다.

그렇다면 함수형 프로그래밍은 무엇인가?

함수형 프로그래밍은 1990년대부터 가장 대중적인 프로그래밍의 형태로 인기를 끌고 있는 객체지향 프로그래밍과 함께 최근 주목받고 있는 프로그래밍 방식이다. 사실 함수형 프로그래밍은 1950년대부터 있었으므로 객체지향보다 역사가 오래되었다.

Comparator 익명 객체를 사용한 정렬 예제를 생각해보자 사실 우리가 필요한 것은 compare() 메서드이다. 메서드만 있으면 되지만, 자바 언어의 한계 또는 특성으로 인해 익명의 내부 클래스를 만들고 객체화해서 전달하고 있다.

자바 8부터 등장한 람다식은 이런 번거로움을 없애 준다.

람다식은 객체가 필요한 자리에 단순히 코드 블록만을 전달해 준다. 이 람다식이 바로 함수라고 볼 수 있다. 람다식은 런타임에 익명의 내부 클래스로 변경돼서 처리되므로 동작은 동일하다.
지금은 람다식을 여기까지만 알아본다.

즉 위 람다식을 사용한 정렬 예제와 comparator 익명 객체를 사용해서 정렬은 java 컴파일러 입장에서는 완전히 같은 코드지만 사용자 입장에서는 가독성이 높고 편리하게 사용할 수 있는 정렬 방법이다.

람다식 개념 출처 https://readystory.tistory.com/32

---

이렇게 해서 2차원 배열 방법을 알기 위해서 comparable, comparator 인터페이스 까지 알아봤다. 원리?를 알고 사용하려니깐 절대 안까먹고 다른 방법으로 응용도 가능할 것 같다.