3. 정렬

정렬관련 내용을 따로 여기에다가 정리할 예정이나 일단은 알고리즘 관련 내용으로 정리한다.(문제 풀이 위주)

조건

- 정렬 조건이 필요함.

- 시간 복잡도는 약 O(NlogN)

- In-place/ stable여부

 

특성

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

.- 각 원소마다 가장 비슷한 순서의 다른 원소는 자신의 양 옆이다.

- 정렬로 문제가 쉽게 풀리는 경우가 많다.

 

1.1 조건

static class Elem implements Comparalbe<Elem>{
	public int num, idx;
    
    @Override
    public int compareTo(Elem other){
    	return num - other.num;
    }
    // Return 음수 : 내가 먼저(오름차순)
    // Return 양수 : 비교대상 먼저 (other ) (내림차순)
    // Return 0 같다.
    
    // 내것 기준 
    // 내것이 크면 먼저하고 싶다면? (큰순서대로라는 뜻 내림차순)
    // 양수
    // 내 것이 작으면 먼저하고 싶다면(작은 순서대로 오름차순)
    // o.num - num;
    //즉, return 값이 양수이면 먼저오도록한다.라고 이해
}

1.2 시간 복잡도

Java의 Arrays.sort(arr) 

primitive : Dual-pivot Quick Sort

Object : Tim sort

최선 O(N) // 최악 O(NlogN) 평균 O(NlogN)

 

1.3 In-place /stable 여부

정렬 알고리즘이 In-place(제자리)한가?

=> 정렬과정에서 N에 비해 충분히 무시할만한 개수의 메모리만큼 '추가적'으로 사용하는가

정렬 알고리즘이 Stable(안정)한가?

=> 동등한 위상의 원소들의 순서 관계가 보존되는가?

=> a(1) b a(2) c  일때 a(1) a(2) b c 인지 a(2) a(1) b c인지.

primitive에서 사용하는 dual-pivot quick sort는 in-place

object에서 사용하는 tim sort는 stable sort

 

 

국영수 Q10825 백준

삼항 연산자 중첩을 통해서 구현하였는데

private static class Student implements Comparable<Student> {
        String name;
        int korean;
        int math;
        int english;

        Student(String name, int korean, int math, int english) {
            this.name = name;
            this.korean = korean;
            this.math = math;
            this.english = english;
        }

        // 내림 오름 내림 오름 국어 수학 영어 이름
        @Override
        public int compareTo(Student o) {
            return o.korean - korean != 0 ? o.korean - korean
                    : math - o.math != 0 ? math - o.math
                            : o.english - english != 0 ? o.english - english : name.compareTo(o.name);
        }
    }

class 안에서 정의하는 것보다 밖에서 list.sort(new Comparaotr)로 하는 것이 더 빨라보이고

삼항연산자보다 if/else문이 빨라보이며 여튼 시간이 꽤 걸리네.

 

 

Internal sorting vs external sorting

stable sorting vs unsatble sorting