5. Introduction of Sort

우리의 Sort의 목적은 정렬가능한 임의의 데이터 타입을 특정한 순서에 따라 정렬시키는 것이다.

 

sort() 함수는 내부적으로 요소의 비교를 위해 compareTo() 함수를 호출할 수 있다.

java에서 이것은 Comparable interface에 정의되어 있다.

 

public interface implements Comparable<Item>{
    public int compareTo(Item that){
    }
}

 

아래는 이것을 구현한 것이다.

 

//comparable interface를 구현한 Date자료구조, total order를 만족하기때문에 정렬가능하다.

public class Data implements Comparable<Date>{
	private final int month, day, year;
    
    public Date(int m, int d, int y){
    	month = m;
        day = d;
        year = y;
    }
    //Argument보다 작으면 -1, 크면 1, 같으면 0 return
    public int compareTo(Date that){
    	if (this.year < that.year) return -1;
        if (this.year > that.year) return +1;
        if (this.month < that.month) return -1;
        if (this.month > that.month) return +1;
        if (this.day < that.day) return -1;
        if (this.day > that.day) return +1;
        return 0;
    }
}

 

우리는 Comparable interface를 구현한 자료구조의 배열를 sort의 argument로 받음으로서, comparable의 method인 compareTo()함수를 sort내부에서 사용하도록 할 수 있고, 따라서, 자료구조의 종류에 따라 sort함수를 변경함 없이 comparable한 모든 자료구조의 정렬을 처리할 수 있다.

 

public static void sort(Comparable[] a){
	...
    ...	a[j].compareTo(a[j-1]) ...
    ...
}

 

하지만 집합내 모든 요소가 정렬 불가능 할 수 있다. 

정렬가능하기 위해서는 집합내 모든 요소에 대해  total order를 만족시켜야 한다.

우리가 아는 일반적인 숫자 집합은 이것이 모두 성립함이 증명되어있다.

1. Antisymmetry :  if v<= w and w <=v, then v=w 

2. Transitivity : if v<=w and w<=x, then v<=x

3. Totality : either v<=w or w<=v or both

 

예를 들어, 가위바위보 집합을 생각해보자. 집합은 {가위, 바위, 보} 이다.

첫번째, Antisymmetry를 성립하는지 알아보자.

첫번째 명제의 대우는, v != w, then v>w or v<w 이다.

v, w가 서로 다를 때 이기고 지는것이 명확하고, 모든케이스에 대해 만족하므로 이것은 참이다.

두번째, Transitivity가 성립하는지 알아보자.

v = 가위, w = 주먹, x = 보 라고 생각해보자

v <= w, w<= x는 참이다. 그런데, v<=x는 보가 가위를 이기지 못하므로 거짓이다.

따라서, Transitivity가 위배되어 가위바위보 집합은 정렬 불가능하다.

 

정렬이후에 잘 정렬되었는지 여부 확인은 isSorted()를 구현함으로서 확인 할 수 있다.

이것은 다음과 같이 구현가능하다.

 

private static boolean isSorted(Comparable[] a){
	... // iterate
    ... if(less(a[i], a[i-1]) return false;
    ...
}

 

그렇다면 이 테스트를 통과하면, 정말 정렬이된것인가? 

만약, sort()가 단순히 데이터 비교와 데이터 자리바꿈(교환)만으로 이루어졌다면 그렇다고 할 수 있다.

하지만, sort의 구현의 일부가 집합의 요소의 값을 일시적으로 변경시키거나 추가/제거 한다면,

비교전의 집합과 비교후의 집합이 동일하다는 보장이 없으므로, 정렬되었다고 확신할 수 없다.