- Comparable과 Comparator 인터페이스의 차이는?
- Comparable 인터페이스는 자연스러운 순서로 정렬할 때 사용하고. Comparator는 원하는 대로 정렬 순서를 지정한다.
- Array와 Collection 클래스는 몇 가지 오버로딩된 정렬 메서드가 있다.
- 배열을 받는 메서드
- 배열과 Comparator 객체를 받는 메서드
- 지정한 순서대로 정렬하고 싶으면 sort 메서드에서 사용할 Comparator 인터페이스를 구현한 후 이를 제공해야 한다.
- Comparator를 인터페이스를 구현한 ReverseNumericalOrder 클래스가 있다고 치자.
- 이 클래스는 compare 메소드를 오버라이드 한 것
- 이것을 Collections.sort(number, new ReverseNumbericalOrder()); 이렇게 전달하면 원하는 순서대로 정렬이 되는 것을 볼 수 있다.
- 버블 정렬 알고리즘
- 순환할 때 마다 하나의 원소만 변경한다.
- 최선의 경우는 이미 정렬되어 잇을 때
- 최악의 경우는 역순으로 정렬되어 있을 떄
- O(n^2)
- 삽입 정렬 알고리즘
- 정렬된 원소들을 새로운 리스트에 담아서 반환 (버블 정렬과 다른 점)
- LinkedList를 사용하며 반환할 리스트가 구성되면 즉시 반환할 수 있다.
- 최악의 경우는 이미 정렬되어 있을 때고, 이때는 O(n^2)
- 최선의 경우는 역순으로 정렬되어 있을 때고, 이때는 O(n)
- 버블vs삽입
- 삽입 정렬 알고리즘은 새로운 리스트를 반환해야 하므로 정렬하려는 리스트의 두배 정도 되는 저장 공간이 필요하다.
- 버블 정렬은 스왑할 때 사용하는 임시 변수용으로 사용할 여분의 메모리 슬롯 하나만 더 있으면 된다.
- 따라서, (나의 의견)
- 어느 정도 정렬된 아주 큰 배열은 버블정렬
- 전혀 정렬되지 않았고 그다지 크지 않은 배열의 경우에는 삽입정렬
- 퀵 정렬 알고리즘
- 재귀적인 알고리즘으로 버블과 삽입 보다 훨씬 더 효율적이고 성능이 ㅇ좋음
- 원소들을 두 개의 리스트로 분리하는 시간 복잡도는 O(n)이고, 각각의 재귀 호출은 각 리스트 숫자의 절반만큼의 횟수만 발생
- 복잡도는 O(n logn)
- 최악의 경우는 pivot (get(0)으로 무작위로 선택한 기준)을 선태갛는 기준에 있는데 리스트가 역순으로 정렬되어 있을 때
- 병합 정렬 알고리즘
- 분할정복 알고리즘
- 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각 하나로 합친다
- 병합 정렬의 성능은 O(n logn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반 만큼만 발생