자바에서 정렬에 대해
유명한 정렬 알고리즘
시간복잡도 N^2 알고리즘
Bubble Sort (버블 정렬)
- 버블 정렬은 배열의 인접한 요소를 비교하고, 필요한 경우 위치를 바꾸는 방식으로 정렬을 수행합니다.
- 이 과정은 배열의 모든 요소가 올바르게 정렬될 때까지 반복됩니다.
Selection Sort (선택 정렬)
- 선택 정렬은 배열을 반복적으로 탐색하여 가장 작은(또는 가장 큰) 요소를 찾아, 정렬되지 않은 부분의 첫 번째 위치와 교환하는 방식으로 작동합니다.
- 이 과정은 배열의 모든 요소가 정렬될 때까지 반복됩니다.
- 선택 정렬은 버블 정렬보다 일반적으로 더 효율적이지만,
- 큰 데이터 세트에 대해서는 여전히 비효율적입니다.
Insertion Sort (삽입 정렬)
- 삽입 정렬은 배열의 각 요소를 이미 정렬된 부분에 적절한 위치에 삽입하는 방식으로 정렬을 수행합니다.
- 새로운 요소를 정렬된 배열 부분에 삽입하기 위해, 이미 정렬된 부분의 적절한 위치가 나타날 때까지 요소들을 오른쪽으로 이동시킵니다.
- 삽입 정렬은 일반적으로 작은 데이터 세트에 효율적이며, 거의 정렬된 데이터에 대해 빠르게 작동합니다.
시간복잡도 NlogN 알고리즘
Quick Sort (퀵 정렬)
- 퀵 정렬은 분할 정복 알고리즘의 한 예로, 배열을 두 부분으로 나누고 각 부분을 재귀적으로 정렬합니다.
- 기준점(pivot)을 선택하고, 이 기준점보다 작은 요소들은 기준점의 왼쪽으로, 큰 요소들은 오른쪽으로 이동시킵니다.
- 이 과정을 반복하여 전체 배열을 정렬합니다.
- 퀵 정렬은 평균적으로 매우 빠른 성능을 보이지만, 최악의 경우 시간 복잡도는 O(n^2)이 될 수 있습니다.
Merge Sort (병합 정렬)
- 병합 정렬도 분할 정복 방법을 사용합니다.
- 배열을 더 이상 나눌 수 없을 때까지 두 부분으로 분할한 후, 분할된 각 부분을 재귀적으로 정렬하고,
- 다시 병합하면서 전체 배열을 정렬합니다.
- 병합 과정에서 두 부분 배열의 요소들을 순서대로 비교하며 새 배열에 삽입합니다.
- 병합 정렬은 모든 경우에 의 시간 복잡도를 가지며, 대규모 데이터에도 효율적입니다.
Heap Sort (힙 정렬)
- 힙 정렬은 완전 이진 트리 구조인 힙을 사용하여 배열을 정렬합니다.
- 먼저 모든 요소를 힙에 삽입하여 최대 힙(또는 최소 힙)을 구성합니다.
- 그런 다음 힙의 루트(가장 큰 또는 가장 작은 값)를 배열의 마지막 요소와 교환하고, 힙의 크기를 줄입니다.
- 이 과정을 반복하여 전체 배열을 정렬합니다.
- 힙 정렬은 평균 및 최악의 경우 모두 의 시간 복잡도를 가집니다.
자바의 Sort 메소드
자바에는 Arrays.sort가 존재합니다. 이 메소드를 사용하면 편하게 배열을 정렬할 수 있습니다.
int[] numbers = {6,5,4,2,3,1};
Arrays.sort(numbers); // 오름차순 정렬
String[] names = {"Park", "Lee", "Song"};
Arrays.sort(names); // 사전순 정렬- boolean[], byte[], short[], int[], long[], float[], double[], char[] 모두 값이 작은 순서대로 오름차순 정렬 입니다.
신기한건 int[]을 정렬한 sort와 String[]을 정렬한 sort가 다른 정렬 알고리즘을 사용한다는 것 입니다.
- int[]
- String[]
int 배열은 DualPivotQuickSort를 사용했고 String 배열은 ComparableTimSort를 사용했습니다!!
| DualPivotQuickSort | TimSort |
| boolean[], byte[], short[], int[], long[], float[], double[], char[] primitive type 배열의 정렬 |
Integer[], Double[] 과 같은 Wrapper Class, String[], 직접 정의한 CustomClass[] 와 같은 Object type 배열의 정렬 |
찾아보니 위의 표처럼 primitive type은 QuickSort를 Object type은 TimSort를 사용합니다.
Dual-Pivot Quick Sort와 Tim Sort의 차이점
둘의 차이점은 stable 하냐 안하냐 입니다.
Dual-Pivot Quick Sort은 stable 하지 않습니다. 즉, 들어 온대로 정렬이 되지 않습니다.
예를 들어 5 1 5 2 3 이라면 1 2 3 5 5 로 정렬이 되지만 첫번째 5가 나중에 들어온 5 일 수 있습니다.
반대로 Tim Sort는 stable이 보장 됩니다.
| Dual-Pivot Quick Sort | Tim Sort | |
| 평균 시간 복잡도 | O(NlogN) | O(NlogN) |
| 최악 시간 복잡도 | O(N^2) | O(NlogN) |
| stable 보장 유무 | X | O |
그러므로 문제에 따라 다르지만 왠만하면 Object를 사용해 배열을 만들고 정렬하는 식이 더 빠르게 정렬을 할 수 있습니다.
하나 더 궁금한점 그럼 Collections.sort는 어떤 것을 쓸까??
들어가서 찾아보니 TimSort를 사용하는 것을 알 수 있습니다. ArrayList<Integer> 이렇게 Object로 선언을 하니 당연한 결과 입니다. 이렇게 보면 배열을 만들어 정렬을 하는 것보니 ArrayList를 만들어 정렬하는게 더 편할 것 같습니다.
Comparable을 사용하여 정렬
public static class Student implements Comparable<Student> {
String name; int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public int compareTo(Student s) {
if(this.age == s.age) return name.compareTo(s.name);
return s.age - this.age;
}
}이렇게 implements를 사용하여 Comparable을 받아와 compareTo를 오버라이딩하여 정렬을 할 수 있습니다.
위의 예시는 학생들을 나이가 같을 경우 이름 가나다 순, 나이는 내림차순으로 정렬한 것 입니다.
Collections.sort(students, (s1, s2) -> {
if(s1.age == s2.age) return s1.compareTo(s2);
return s2.age - s1.age;
});이렇게 student 클래스를 그냥 받아와 람다식으로 정렬을 할 수도 있습니다!!