Comparator 혹은 Comparable을 구현한 클래스의 경우에는 내부적으로 구현된 정렬 알고리즘을 통해 수행되지만, 알고리즘 문제 풀이를 위해 직접 정렬 알고리즘을 구현해야하는 경우가 있다.
앞서, 알고리즘은 시간복잡도가 관건이라고 알아보았는데 정렬 알고리즘에서는 O(N^2)에서부터 시작해서 O(NlogN)까지 개선해나가는 방식으로 소개하고자 한다.
Bubble Sort(거품 정렬) : O(N^2), Stable, Inplace
인덱스상 앞뒤에 위치한 값을 비교하면서 교환하는 정렬 알고리즘
한번 모든 값을 보면 하나의 값이 제 위치를 찾아가는 특성을 보인다.
public void BubbleSort(T[] arr){
int size = arr.length;
for(int i=0;i<size-1;i++){
for(int j=0;j<size-1-i;j++){
if(arr[j]>arr[j+1]){
T tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}
public static int[] bubbleSort(int[] arr){
int size = arr.length;
boolean sorted = true;
do{
sorted = true;
for(int i=0;i<size-1;i++){
if(arr[i]>arr[i+1]){
int tmp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = tmp;
sorted = false;
}
}
}
while(!sorted);
return arr;
}Selection Sort(선택 정렬) : O(N^2), UnStable, Inplace
가장 작은 값을 선택해서 아직 정렬되지 않은 인덱스 중 맨 앞 인덱스에 배치한다.
public static int[] selectionSort(int[] arr){
int size = arr.length;
//현재 정렬하고자 하는 인덱스
for(int i=0;i<size-1;i++){
int min = i;
//해당 인덱스에 와야할 가장 작은값 찾기
for(int j=i+1;j<size;j++){
if(arr[min]>arr[j]){
min = j;
}
}
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
}Insertion Sort(삽입 정렬) : O(N^2), Stable, Inplace
현재 값 앞까지는 모두 정렬이 되었다고 보고, 그 정렬된 배열에 현재 값의 위치를 찾아 끼워넣는다.
public static int[] insertionSort(int[] arr){
int size = arr.length;
for(int i=1;i<size;i++){
int j = i-1;
int key = arr[i];
while(j>=0 && arr[j]>key){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
return arr;
}Radix Sort(기수 정렬) : O(자릿수*N) , Stable
맨 뒷자리부터 하나씩 확인하면서 같은 값을 같는 녀석들을 List에 담고
한 회차가 끝나면 순서대로 꺼내서 배열을 만든 뒤, 맨 앞자리까지 반복한다.
public static int[] RadixSort(int[] arr,int size) {
int maxIdx = 1;
for(int v: arr) {
maxIdx = Math.max(maxIdx, String.valueOf(v).length());
}
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
for(int k=1;k<=maxIdx;k++) {
int id = 0;
for(int i=0;i<10;i++) {
map.put(i,new ArrayList<>());
}
for(int i=0;i<size;i++) {
int idx = (arr[i]/(int)Math.pow(10, k-1))%10;
map.get(idx).add(arr[i]);
}
for(int i=0;i<10;i++) {
ListIterator li = map.get(i).listIterator();
while(li.hasNext()) {
arr[id++] = (int)li.next();
}
}
}
return arr;
}Merge Sort(병합정렬) : O(NlgN), Stable
Divide And Conquer => 재귀로 구현되어 있으며, 나누는데 lgN 합치는데 N
public static int[] mergeSort(int[] arr,int low,int high){
if(low<high){
int mid = (low+high)/2;
mergeSort(arr,low,mid);
mergeSort(arr,mid+1,high);
merge(arr,low,mid,high);
}
return arr;
}
public static int[] merge(int[] arr,int low,int mid,int high){
int i = low;
int j = mid+1;
int k = low;
while(i<=mid && j<=high){
if(arr[i]<arr[j]){
sortedArr[k++] = arr[i++];
}
else{
sortedArr[k++] = arr[j++];
}
}
while(i<=mid){
sortedArr[k++] = arr[i++];
}
while(j<=high){
sortedArr[k++] = arr[j++];
}
for(int l=low;l<=high;l++){
arr[l] = sortedArr[l];
}
return arr;
}
}Quick Sort(퀵 정렬) : O(NlgN) : UnStable, Inplace
public static void quickSort(int[] arr,int low,int high){
if(low<high){
int loc = partition(arr,low,high);
quickSort(arr,low,loc-1);
quickSort(arr,loc+1,high);
}
}
public static int partition(int[] arr,int low,int high){
int pivot = arr[high];
int i = low-1;
for(int j=low;j<high;j++){
if(arr[j]<pivot){
i++;
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
int tmp2 = arr[++i];
arr[i] = arr[high];
arr[high] = tmp2;
return i;
}
Heap Sort(힙 정렬) : O(NlgN) : UnStable, Inplace
Heap에 데이터를 모두 넣은 뒤에 빼면 정렬이 되어있다.
Binary Search(이진 탐색) : O(lgN)
반드시 정렬된 데이터를 기반으로 하며, 여러번의 탐색이 이루어질 때 좋다.
- lower bound : 찾고자하는 값 이상이 되는 첫번째 출현 위치
- upper bound : 찾고자하는 값을 초과하는 첫번째 출현 위치
public int BinarySearch(int[] arr,int target){
int left = 0;
int right = arr.length-1;
while(left<=right){
int mid = (left+right)/2;
int value = arr[mid];
if(value==target){
return mid;
}
if(value>target){
right = mid-1;
}
else{
left = mid+1;
}
}
return -1;
}
public int lower_bound(int[] arr,int target){
int left = 0;
int right = arr.length-1;
int minIdx = arr.length;
while(left<=right){
int mid = (left+right)/2;
if(arr[mid]>=target){
minIdx = Math.min(minIdx,mid);
right = mid-1;
}
else{
left = mid+1;
}
}
return minIdx;
}
public int upper_bound(int[] arr,int target){
int left = 0;
int right = arr.length-1;
int minIdx = arr.length;
while(left<=right){
int mid = (left+right)/2;
if(arr[mid]>target){
minIdx = Math.min(minIdx,mid);
right = mid-1;
}
else{
left = mid+1;
}
}
return minIdx;
}위상 정렬(Topology Sort) : O(V+E)
방향성이 있는 그래프에서 순서대로 모순 없이 진행하는 순서를 정하는 알고리즘
- DFS : 퇴각할때 Stack에 넣고, 역순으로 꺼내면 완성
- BFS(Indegree) : Indegree가 0인 노드를 넣고, 감소시켜가며 Queue에서 꺼낸 순으로 완성
위상 정렬이 완성되지 못하면 싸이클이 존재한다고 볼 수 있다.
최소 신장 트리 (Minimum Spanning Tree)
정점 N개에 대하여 간선 N-1개로 최소한의 가중치의 합으로 모든 정점을 연결하는 간선의 집합
- Kruskal(간선 중심) : 가중치가 적은 간선부터 고르면서, 사이클을 형성하지 않도록 고르다가 N-1개가 되면 종료 (ElogE + ElogN) = ElogE
- Union-Find O(LogN) - Prim(정점 중심) : 임의의 정점을 시작점으로 잡고, MST의 구성요소가 될 정점을 선택(비용이 가장적은)
O(ElogV, V^2)
