자바에서 정렬하기 4가지 방법

 

백준에서 강의실 배정 문제를 풀다가

sort가 되는 원리를 잘 이해 못하고 있다보니

정렬이 잘되었는지 확인하기 위해 헛된 시간을 쏟고 있다는 것을 깨달았다.

깨달았으면? 공부를 해야지!

 

---

 

1. Arrays.sort()

배열을 이용할 때는 Arrays.sort()를 이용한다.

Arrays.sort()는 정렬 방식이 DualPivotQuickSort이다. 2가지 포인터를 이용해 비교하는 퀵소트로 정렬한다. 이런 이유로 시간 복잡도는 평균 O(n log n)이지만 최악의 경우에는 O(n^2)까지 나올 수 있다. 그래서 정렬할 일이 생기면 기본 Collections.sort() 먼저 생각하기 나름이다.

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

class Main {
    public static void main(String[] args){
        int[] numbers = {5,4,3,2,1};
        
        Arrays.sort(numbers);
        
        for(int i=0;i<numbers.length;i++){
            System.out.print(numbers[i]+" ");
        }
    }
}

 

출력 : 1 2 3 4 5

 

 

2. Collections.sort()

List 컬렉션을 사용할 때 주로 Collections.sort()를 이용한다.

특히 PriorityQueue를 이용하지 않을 때 사용한다. (이용한다면 Comparable)

 

Arrays.sort()는 정렬 방식이 TimeSort이다. 삽입정렬과 합병정렬을 결합한 정렬이다.

시간 복잡도는 평균도 O(n log n)이고, 최악의 경우에도 O(n log n) 이다.

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

class Main {
    public static void main(String[] args){
        List<Integer> numbers = new ArrayList<>();

        numbers.add(5);
        numbers.add(4);
        numbers.add(3);
        numbers.add(2);
        numbers.add(1);
        
        Collections.sort(numbers);
        
        for(int i=0;i<numbers.size();i++){
            System.out.print(numbers.get(i)+" ");
        }
    }
}

 

출력 : 1 2 3 4 5

 

 

List에 객체를 넣어 비교하는 경우라면 콕! 하나의 변수를 집어 비교해줄 수도  있다. 나는 람다식을 주로 이용한다.

객체 o1과 o2를 비교하는 방식이다.

 

Collections.sort 람다식 동작 방식

• o1.start > o2.start == 1 이면, 오름차순 정렬이다. o1.start가 더 크니까 뒤로 이동한다.
• o1.start < o2.start == -1 이면, 내림차순 정렬이다. o1.start가 더 작으니까 앞으로 이동한다.

Collections.sort(list, (o1, o2) -> o1.start>=o2.start?1:-1);

 

 

3. Comparable

나같은 경우는 Comparable을 PriorityQueue에 입력 값(특히 객체)을 넣어줄 때 사용하곤 한다. 입력값을 넣음과 동시에 정렬을 해주는 것이다. 일반적인 Integer면 그냥 넣어주기만 해도 정렬이 되는데, 2개 이상의 값을 비교할 때 즉, 객체를 비교할 때 사용한다.

 

PriorityQueue는 넣거나 뺄 때 기존 정렬 상태를 유지하기 때문에 O(log N)이다.

PriorityQueue는 힙이라고도 불린다는 사실!

 

compareTo 동작 방식

• 나(this) > 비교대상 == 1 , 오름차순 정렬이다. 내가 더 크니까 뒤로 이동한다.
• 나(this) < 비교대상 == -1 , 내림차순 정렬이다. 내가 더 작으니까 앞으로 이동한다.

 

예제) 강의 객체의 시작 시간만 비교해서 시작 시간이 빠른 순 정렬

강의 시작 시간이 내가(this)가 더 클 때 1이 반환되도록 했다.

때문에 나의 강의시간이 더 크다면 오름차순 정렬이 될 것이다. 즉, 내가 비교군 뒤로 이동할 것이다.

 

하지만 내가(this) 비교군보다 더 작다면 -1이 반환되도록 했다.

때문에 나의 강의시간이 더 작다면 내림차순 정렬이 될 것이다. 즉, 내가 비교군 앞으로 이동할 것이다.

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

class Main {
    public static void main(String[] args){
        PriorityQueue<Lecture> timeTable = new PriorityQueue<>();

	timeTable.add(new Lecture(1, 3));
	timeTable.add(new Lecture(3, 5));
	timeTable.add(new Lecture(2, 5));
	timeTable.add(new Lecture(2, 4));
        
        
        while(!timeTable.isEmpty()){
            Lecture lec = timeTable.poll();
            System.out.println(lec.start+" "+lec.end);
        }
    }

    public static class Lecture implements Comparable<Lecture>{
        int start;
        int end;

        public Lecture(int start, int end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Lecture o){
            return this.start>o.start?1:-1;
        }
    }
}

 

출력 

1 3

2 4

2 5

3 5

 

 

근데 위 코드에서 = 만 넣어줘도 출력값의 큰 차이가 있다.

public static class Lecture implements Comparable<Lecture>{
	int start;
	int end;

	public Lecture(int start, int end){
		this.start = start;
		this.end = end;
	}

	@Override
	public int compareTo(Lecture o){
		return this.start>=o.start?1:-1;
	}
}

 

출력 

1 3

2 5

2 4

3 5

 

 

대체 왜 다른거지?? 너무 궁금했다. 그래서 분석해보기로 했다.

다음과 같은 입력값이 주어졌을 때 비교 순서가 아래와 같았다.

timeTable.add(new Lecture(1, 3)); //1
timeTable.add(new Lecture(3, 5)); //2
timeTable.add(new Lecture(2, 5)); //3
timeTable.add(new Lecture(2, 4)); //4

//(2,1) -> (3,1) -> (4,2) -> (4,3) -> (2,4) -> (3,2)
//(2,1) -> (3,1) -> (4,2) -> (4,1) -> (4,3) -> (2,3) -> (2,4) (= 붙음)

 

= 이 안붙었을 때는 다음과 같은 양상을 보인다.

나 = 2, 비교군  = 1이 비교되어 나의 시작 시간이 더 큰 상태이다. (3, 5) > (1, 3) == 오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (3, 5) -> (2, 5) -> (2, 4)

 

나 = 3, 비교군 = 1이 비교되어 나의 시작 시간이 더 큰 상태이다. (2, 5) > (1, 3) == 오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (3, 5) -> (2, 5) -> (2, 4)

 

나 = 4, 비교군 = 2가 비교되어 비교군의 시작 시간이 더 큰 상태이다. (2, 4) < (3, 5) == 내림차순 (내가 앞으로)

---- 여기까지는 (1, 3) -> (2, 4) -> (3, 5) -> (2, 5)

 

나 = 4, 비교군 = 3이 비교되어 시작시간이 서로 같은 상태이다. (2, 4) == (2, 5) == 내림차순 (내가 앞으로)

---- 여기까지는 (1, 3) -> (2, 4) -> (3, 5) -> (2, 5)

 

나 = 2, 비교군 = 4가 비교되어 나의 시작 시간이 더 큰 상태이다. (3, 5) > (2, 4) == 오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (2, 4) -> (3, 5) -> (2, 5)

 

나 = 3, 비교군 = 2가 비교되어 비교군의 시작 시간이 더 큰 상태이다. (2, 5) < (3, 5) == 내림차순 (내가 앞으로)

---- 여기까지는 (1, 3) -> (2, 4) -> (2, 5) -> (3, 5)

 

---

 

= 이 붙었을 때는 다음과 같은 양상을 보입니다.

나 = 2, 비교군  = 1이 비교되어 나의 시작 시간이 더 큰 상태이다. (3, 5) > (1, 3) == 오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (3, 5) -> (2, 5) -> (2, 4)

 

나 = 3, 비교군 = 1이 비교되어 나의 시작 시간이 더 큰 상태이다. (2, 5) > (1, 3) == 오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (3, 5) -> (2, 5) -> (2, 4)

 

나 = 4, 비교군 = 2가 비교되어 비교군의 시작 시간이 더 큰 상태이다. (2, 4) < (3, 5) == 내림차순 (내가 앞으로)

---- 여기까지는 (1, 3) -> (2, 4) -> (3, 5) -> (2, 5)

 

나 = 4, 비교군 = 1이 비교되어 나의 시작 시간이 더 큰 상태이다. (2, 4) > (1, 3) ==  오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (2, 4) -> (3, 5) -> (2, 5)

 

나 = 4, 비교군 = 3가 비교되어 시작시간이 서로 같은 상태이다. (2, 4) == (2, 5) == 오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (3, 5) -> (2, 5) -> (2, 4)

 

나 = 2, 비교군 = 3이 비교되어 나의 시작 시간이 더 큰 상태이다. (3, 5) > (2, 5) == 오름차순 (내가 뒤로)

---- 여기까지는 (1, 3) -> (2, 5) -> (3, 5)  -> (2, 4)

 

나 = 2, 비교군 = 4가 비교되어 나의 시작 시간이 더 큰 상태이다. (3, 5) > (2, 4) == 오름차순 (내가 뒤로)

---- 그리하여 최종결과는 (1, 3) -> (2, 5)  -> (2, 4) -> (3, 5)

 

---

 

분석해보니 별 의미 없는 것 같다 ㅋ나 > 비교군 일 때는 내가 크면 내가 비교군 뒤에 위치해야 하고, 나 < 비교군이 되면 내가 비교군 앞에 위치해야 한다.== 조건이 없으므로 나 == 비교군이면 내가 비교군 앞에 위치해야 한다.

 

나 >= 비교군 일 때는 위와 동일하지만, == 조건이 있으므로 나 == 비교군이면 내가 비교군 뒤로 가야한다.

 

이 과정에선 무조건 시작 시간만 고려하니까 끝나는 시간이 재각각이 나오는 이유를 알아봤자 무의미한 것 같다.

단지 시작 시간이 같을 때 어떻게 처리해줄지의 섬세한 차이이다.

 

 

4. Comparator

나같은 경우는 Comparator을 PriorityQueue를 이용하지 않을 때 쓴다.

특히 Arrays.sort()를 이용해 배열을 정렬할 때 객체를 비교해 정렬하고 싶다면, Comparator을 이용해 정렬해준다.

Comparable과는 달리 java.util에서 import를 해줘야 한다.

 

compare 동작 방식

• 나(this) > 비교대상 == 1 , 오름차순 정렬이다. 내가 더 크니까 뒤로 이동한다.
• 나(this) < 비교대상 == -1 , 내림차순 정렬이다. 내가 더 작으니까 앞으로 이동한다.

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

class Main {
    public static void main(String[] args){
       Lecture[] timeTable = new Lecture[4];

        timeTable[0] = (new Lecture(1, 3)); //1
        timeTable[1] = (new Lecture(3, 5)); //2
        timeTable[2] = (new Lecture(2, 5)); //3
        timeTable[3] = (new Lecture(2, 4)); //4

        Arrays.sort(timeTable, new Comparator<Lecture>() {

			@Override
			public int compare(Lecture o1, Lecture o2) {
				if(o1.start==o2.start) return o1.end>o2.end?1:-1;
				else return o1.start>o2.start?1:-1;
			}
		});
        
        for(int i=0;i<4;i++){
            Lecture lec = timeTable[i];
            System.out.println(lec.start+" "+lec.end);
        }
    }

    public static class Lecture{
        int start;
        int end;

        public Lecture(int start, int end){
            this.start = start;
            this.end = end;
        }

    }
}