출처
해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다.
7-1
BubbleSort
첫 요소 부터 마지막 요소까지 기준을 지정하면서 나머지 요소들과 현재 기준인 요소의 크기를 비교 합니다. 오름차순의 경우 기준 요소 값보다 나머지 요소중 더 작은 값이 존재한다면 교환 합니다.
- O(N^2)
Insertion Sort
첫 요소 부터 마지막 요소까지 기준을 정하면서 이미 정렬된 요소들과 현재 기준인 요소들을 비교합니다. 오름차순의 경우 기준인 요소보다 더 크다면 한칸씩 뒤로 미루고 더 작다면 기준인 요소를 더 작은 요소 바로 두에 위치 시킵니다.
- O(N^2)
Selection Sort
나머지 요소들 중 가장 작은 요소를 가장 앞에 위치시키고 다시 가장 작은 요소를 뺀 나머지들 중 가장 작은 요소를 가장 앞에 위치시킵니다. 차례로 가장 작은 값을 찾아 나머지들 중 가장 앞에 위치시킵니다.
- O(N^2)
Quick Sort
임의의 값(보통은 중앙 인덱스)을 골라 pivot으로 지정합니다. pivot보다 적은 값은 pivot의 왼쪽으로 큰 값은 pivot의 오른쪽으로 보냅니다. pivot보다 적은 값들(왼쪽)을 다시 재귀적으로 호출하고 pivot보다 큰 값들(오른쪽)을 다시 재귀적으로 호출합니다. 적은 값들, 큰 값들 모두 재귀함수로부터 돌아오면 작은 값들 + pivot + 큰 값들 합쳐서 반환합니다.
- O(NlogN)
MergeSort
두 집합들을 반으로 나누어 재귀적으로 호출합니다. 합칠땐 두 집합간 최소값들을 비교하며 차례로 합칩니다. 만약 한쪽이 더 이상 비교할 요소가 존재하지 않는 다면 반대쪽의 남은 요소들을 맨 뒤에 추가합니다.
- O(NlogN)
Sorting 구현 코드
https://velog.io/@ds02168/QuickSortInsertionSortRadixSortMergeSortHeapSort
7-2
Java를 사용하면 일일이 모든 정렬 알고리즘을 외우고 필요때 마다 일일이 구현할 필요가 없습니다. 간단히 API를 사용하면 최적의 알고리즘으로 정렬한다는 보장을 믿고 수행할 수 있습니다.
Comparator
자바에서는 Comparator 인터페이스를 이용하여 간편하게 자료구조들을 정렬할 수 있습니다.
Collection.sort(new Comaprator<클래스>(){
@Override
public compare(클래스 o1, 클래스 o2){
return o1.필드 - o2.필드;
}
});위의 포맷대로 오름차순의 경우 첫 번째 매개변수와 두번째 매개변수의 차로 순서를 정하고, 내림차순의 경우 두 번째 매개변수와 첫번째 매개변수의 차로 순서를 정합니다.
list.sort((o1,o2) -> o1.compareTo(o2));Comparator<클래스> 는 함수형 인터페이스이므로 compare매개변수에 대해 람다식이 가능합니다.
Comparable<클래스>
기존의 Comparator 인터페이스만 사용해서 객체들간 정렬을 할 경우 비교할 필드를 미리 알고 compare메서드에 정의해 두어야 합니다. 비교할 객체들의 클래스에 Comparable<클래스> 인터페이스를 구현한다면 간편하게 비교 메서들을 사용할 수 있습니다.
class 클래스 implements Comparable<클래스>{
필드
...
새성자
메서드
...
@Override
public compareTo(클래스 o){
return this.필드 와 o.필드 비교;
}
}list.sort(Comparator.naturalOrder()); //오름차순
list.sort(Comparator.reverseOrder()); //내림차순비교할 객체들의 클래스에 미리 Comparable<클래스>를 구현하여 compareTo메서드를 오버라이딩 한다면 객체간 비교에도 자바가 제공하는 API를 바로 사용할 수 있습니다.
GitHub
