10-3. 정렬

정렬1 - Comparable, Comparator

---

• 데이터 정렬

 package collection.compare;
 
 import java.util.Arrays;
 
 public class SortMain1 {
 
 	public static void main(String[] args) {
    
 		Integer[] array = {3, 2, 1};
 		System.out.println(Arrays.toString(array));
        
 		System.out.println("기본 정렬 후");
		Arrays.sort(array);
 		System.out.println(Arrays.toString(array));
        
    }
 }

실행 결과

[3, 2, 1]
기본 정렬 후
[1, 2, 3]

• Arrays.sort()를 사용하면 배열에 들어있는 데이터를 순서대로 정렬할 수 있음

정렬 알고리즘

---

• 정렬은 아래와 같은 방식으로 이루어짐
  
• 맨 앞 두 데이터를 비교한 후, 왼쪽이 더 크면 둘을 교환함
  
• 처음부터 끝까지 비교하면 마지막 항목은 가장 큰 값이 됨
  
• 처음으로 돌아와서 다시 비교 시작
• 최종적으로 1, 2, 3으로 정렬됨

• 지금 설명한 정렬은 가장 단순한 정렬의 예시임

  • 실제로는 정렬 성능을 높이기 위한 다양한 정렬 알고리즘이 존재함

• 자바는 초기에는 퀵소트를 사용했다가 지금은 데이터가 작을 때(32개 이하)는 듀얼 피벗 퀵소트(Dual-Pivot QuickSort)를 사용하고, 데이터가 많을 때는 팀소트를 사용함

  • 이런 알고리즘은 평균 O(nlogn)의 성능을 제공함

쿽소트(Quick Sort)

• 임의의 피봇을 기준으로 해당 피봇 값보다 작은 데이터는 피봇의 왼쪽에, 큰 데이터는 피봇의 오른쪽에 배치함
• 그리고 왼쪽 부분과 오른쪽 부분을 다시 퀵 정렬 방법으로 정렬하는 알고리즘
• 전체 데이터를 2개의 부분으로 분할한 뒤, 각각의 부분을 다시 퀵정렬하는 전형적인 분할-정복 알고리즘

quick_sort(int[] list, int left, int right) {
    if (left < right) {
        int pivot = partition(list, left, right);
        quick_sort(list, left, pivot-1);
        quick_sort(list, pivot+1, right);
    }
}

1. 배열의 임의의 원소를 pivot, 가장 첫 번째 원소를 low, 가장 마지막 원소를 high라고 지정

2. low 값이 pivot보다 작을 동안 low의 인덱스를 증가시킴

• 반복문이 계속될 때까지 조건에 부합하는 원소들은 pivot의 오른족 부분 리스트가 됨

3. high 값이 pivot보다 클 동안 high 인덱스를 감소시킴

• 반복문이 계속될 때까지 조건에 부합하는 원소들은 pivot의 오른쪽 부분 리스트가 됨

4. 2와 3의 반복문을 탈출하여 도달한 위치는 각각 low 값이 pivot보다 크고, high 값이 pivot보다 작은 경우이므로 이때 멈춘 두 원소 자리를 교환함

5. low와 high의 위치가 엇갈리지 않을 때까지 2~3 과정을 반복함

6. low와 high의 위치가 엇갈리는 때 high와 pivot의 자리를 교환함

• 최종적으로 pivot의 위치를 기준으로 왼쪽에는 pivot보다 작은 원소들이, 오른쪽에는 pivot보다 큰 원소들이 위치하게 됨

듀얼 피봇 퀵소트(Dual Pivot Quick Sort)

• 피봇 1개를 기준으로 삼아 정렬하는 퀵 정렬에서, 피봇 2개를 기준으로 정렬하는 알고리즘

• 임의의 피봇 2개를 기준으로 pivot1보다 작은 부분, pivot1 ~ pivot2 사이의 부분, pivot2보다 큰 부분으로 나눈 뒤 각 부분을 다시 듀얼 피봇 퀵정렬 방법으로 정렬함

  • pivot2는 항상 pivot1보다 크도록 설정해야 함

팀 소트(Tim Sort)

• Tim Peter에 의해 고안된 Merge Sort, Insertion Sort이 혼용된 하이브리드 정렬 알고리즘

  • 합병 정렬을 기반으로 구현하되, 일정 크기 이하의 부분 리스트에 대해서는 이진 삽입을 수행하는 것

• 삽입 정렬의 작은 데이터 세트에 대해 효율적인 면과 병합 정렬의 큰 데이터 세트에 효율적인 면을 합친 것임

• 팀 정렬은 배열을 여러 부분으로 나눔

  • 이렇게 나눠진 부분을 run이라고 하며, 각 run에서는 삽입 정렬로 정렬함
  • 정렬된 run들은 병합 정렬로 합치면서 정렬함

• 이렇게 작은 부분에서는 삽입 정렬을 큰 부분에서는 병합 정렬을 이용해 각 정렬들의 강점을 활용하여 정렬함

비교자 - Comparator

---

• 정렬을 할 때 1, 2, 3 순서가 아니라 3, 2, 1로 정렬하고 싶다면, 비교자를 사용하면 됨
• 이름 그대로 두 값을 비교할 때 비교 기준으로 직접 제공할 수 있음

public interface Comparator<T> {
   int compare(T o1, T o2);
}

• 두 인수를 비교해서 결과 값을 반환하면 됨
  • 첫 번째 인수가 더 작으면 음수, 예(-1)
  • 두 값이 같으면 0
  • 첫 번째 인수가 더 크면 양수, 예(1)

package collection.compare;

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

public class SortMain2 {
 
 	public static void main(String[] args) {
    
 		Integer[] array = {3, 2, 1};
 		System.out.println(Arrays.toString(array));
 		System.out.println("Comparator 비교");
 		Arrays.sort(array, new AscComparator());
 		System.out.println("AscComparator:" + Arrays.toString(array));
        
 		Arrays.sort(array, new DescComparator());
 		System.out.println("DescComparator:" + Arrays.toString(array));
 		Arrays.sort(array, new AscComparator().reversed()); //DescComparator와 같다
        System.out.println("AscComparator.reversed:" + Arrays.toString(array));
        
    }
    
 	static class AscComparator implements Comparator<Integer> {
    
        @Override
 		public int compare(Integer o1, Integer o2) {
 			System.out.println("o1=" + o1 + " o2=" + o2);
 			return (o1 < o2) ? -1 : ((o1 == o2) ? 0 : 1);
        }
        
    }
    
 	static class DescComparator implements Comparator<Integer> {
    
        @Override
 		public int compare(Integer o1, Integer o2) {
 			System.out.println("o1=" + o1 + " o2=" + o2);
 			return (o1 < o2) ? -1 : ((o1 == o2) ? 0 : 1) * -1;
        }
        
    }
    
}

실행 결과

[3, 2, 1]
Comparator 비교
o1=2 o2=3
o1=1 o2=2
AscComparator:[1, 2, 3]

o1=2 o2=1
o1=3 o2=2
DescComparator:[3, 2, 1]

o1=3 o2=2
o1=2 o2=1
AscComparator.reversed:[3, 2, 1]

• Arrays.sort()를 사용할 때 비교자를 넘겨주면 알고리즘에서 어떤 값이 더 큰지 두 값을 비교할 때, 비교자를 사용함

Arrays.sort(array, new AscComparator())
Arrays.sort(array, new DescComparator())

• AscComparator를 사용하면 숫자가 점점 올라가는 오름차순으로 정렬됨

• DescComparator를 사용하면 숫자는 점점 내려가는 내림차순으로 정렬됨

  • 왜냐하면 DescComparator구현의 마지막에 -1을 곱해주었기 때문에 이렇게 하면 양수는 음수로, 음수는 양수로 반환됨
  • 쉽게 이야기해서 계산의 결과가 반대로 됨
  • 따라서 정렬의 결과도 반대가 됨

정렬을 반대로

new AscComparator().reversed()

• 정렬을 반대로 하고 싶으면 reversed() 메서드를 사용하면 됨

  • 이렇게 하면 비교의 결과를 반대로 변경함
  • 앞서 설명한 -1을 곱한 것과 같은 결과가 나옴

• 비교자(Comparator)를 사용하면 정렬의 기준을 자유롭게 변경할 수 있음

강의 출처 : 김영한의 실전 자바 - 중급 2편
정렬 알고리즘 자료 출처 : [Algorithm] 퀵 정렬(Quick Sort)과 듀얼 피봇 퀵 정렬(Dual Pivot Quick Sort)