정렬

1) 정렬이란?

- 정렬은 어떤 자료들이 주어졌을 때, 그 자료들에 대해서 오름차순 혹은 내림차순 등의 기준이 주어졌을 때,

  그것에 맞게 자료들을 정렬하는 것을 말합니다. 

  오름차순이라면 크기가 작은 것이 앞에, 내림차순이라면 크기가 큰 것이 앞에 정렬합니다. 

  

 

2) 정렬의 특징

 

(1) 정렬 조건이 필요하다

- 정렬 조건이란 어떤 자료들이 주어졌을 때, 2개 중에서 어떤 것이 앞에 와야 하는지에 관한 것입니다. 

  자료 4개가 주어졌을 때, 오름차순으로 정렬해달라는 조건이 들어 왔다면,

  크기가 작은 것이 앞에 오게 합니다

  예를 들어, 자바에서는 Comparable 인터페이스를 구현해서 이를 나타낼 수 있습니다.

static class Elem implements Comparable<Elem>{

    public int num, idx;
    
    @Override
    public int compareTo(Elem other){
        return num-other.num;
    }

}

- Comparable 인터페이스를 사용할 때는, compareTo 메소드를 정의해줘야 합니다.

  compareTo 메소드는 항상 int형을 돌려주며, 같은 자료구조인 또 다른 값인 other를 받습니다. 

  이 때, num - other.num이 음수를 리턴하면 내가 더 작다는 것을,

  양수를 리턴하면 쟤(other)가 더 작다는 것을,

  0을 리턴하면 같다는 것을 의미합니다. 

 

(2) 시간 복잡도

- 자바에서 기본적으로 제공하는 정렬 함수는 시간 복잡도가 O(nlogn)입니다. 

  만약 N이 10만이라면, logN이 약 16이기 때문에, 대략 160만번의 연산이 필요합니다. 

  좀 더 심화하면, 자바에서 제공하는 Array.sort메소드는 기본 자료형과 참조 자료형에 대해 

  적용되는 정렬 방식이 다릅니다. 

  Arrays.sort 메소드는 기본 자료형에 대해서는 Dual-Pivot Quick Sort를,

  반면, 참조 자료형에 대해서는 Tim Sort를 사용합니다. 

  Dual-Pivot Quick Sort는 평균 O(nlogn), 최악의 경우 O(n^2)의 시간이 걸리고,

  Tim Sort는 평균 O(nlogn), 최악의 경우 O(nlogn)의 시간이 걸립니다. 

 

 

(3) In-place와 Stable 여부

- 정렬 알고리즘이 In-place(제자리)한가의 여부는 정렬하는 과정에서 N에 비해 충분히 무시할만한 

  개수의 메모리만큼을 추가적으로 사용하는가에 관한 것입니다. 

 

- 정렬 알고리즘인 stable(안정)한가의 여부는 동등한 위상의 원소들의 순서 관계가 보존되는가

  에 관한 것입니다. 

 

- Arrays.sort 메소드에 대해서 기본 자료형은 퀵 소트이기 때문에, In-place sort이고,

  참조 자료형은 Tim Sort이기 때문에, Stable Sort입니다.  

 

 

(4) 정렬의 특성

- 같은 정보들은 인접해 있습니다

- 각 원소마다 가장 가까운 원소(or 비슷한 원소)는 자신의 양 옆 중에 있습니다. 

 

참고

패스트캠퍼스 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online