[Algorithm] 정렬

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다.

출처 : https://github.com/rhs0266/FastCampus

 

 

정렬

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

 

 

정렬의 조건

1. 정렬 조건이 필요

static class Elem implements Comparable<Elem> {
    public int num, idx;

    @Override
    public int CompareTo(Elem other) {
        // 오름차순 -> return 음수
        return num - other.num;
        
        // 내림차순 -> return 양수
        // return other.num - num;

        // 같은 경우 -> return 0
    }
}

return 값

• 음수: 내가 작으니까 내가 먼저 -> 오름차순
• 양수: 쟤(other)가 작으니까 쟤가 먼저 -> 내림차순
• 0: 우리는 친구 -> 같은 경우

 

 

2. 시간 복잡도는 약 O(N log N)

N개의 원소를 정렬하는 것은 O(N log N) 만큼의 시간복잡도를 갖는다.

• 예를 들어 N이 10만개일 경우 약 160만, 즉 1초 안에 충분히 연산이 가능한 것이다.

 

 

둘 다 평균 시간 복잡도가 O(N logN)으로 같지만 최악의 경우만 놓고 보면 Tim Sort가 더 안전할 테니까 Object 원소로 정렬을 하면 무조건 안전할까?

Tim Sort는 In-place하지 않기 때문에 시간이 더 걸릴 수 있으므로 그렇지 않다.

 

3. In-place / Stable 여부

• In-place(제자리)인가?
  • N에 비해 충분히 무시할만한 개수의 메모리만큼만 추가적으로 사용하는가?
  • N이 10만개일 때 정렬 과정에서 메모리를 10개 정도만 더 쓸 경우 충분히 무시할 수 있어서 In-place하다.
    • 만약 10만개의 메모리를 더 써야한다면 무시할 수 없기에 In-place하지 않다.
• Stable(안정) 한가?
  • 동등한 위상의 원소들의 순서 관계가 보존되는가?
  • 만약 5, 5가 입력되었고, 그것을 출력할 때 앞의 5와 뒤의 5가 순서 그대로 출력되면 Stable한 경우이다.
  • 즉, 비교가 불가능한 두 대상에 대해서 순서 관계가 입력 순 그대로 나온다면 Stable한 것이다.

 

이 복잡한 것을 깊게 알 필요는 없고 정렬시에 평균 O(N logN)의 시간이 걸린다는 것과 Primitive 원소를 정렬할 때에는 Quick Sort라서 In-place하고, Object 원소를 정렬할 때에는 TimSort라서 Stable하다는 것만 알고 있으면 된다.

 

 

정렬의 특성

1. 정렬 후에 같은 정보들은 인접해 있을 것

2. 각 원소마다 가장 가까운 원소 즉, 가장 비슷한 원소는 자신의 양 옆 중의 하나