삽입 부모 노드와 삽입할 데이터를 비교해서 삽입할 데이터가 더 크면 오른쪽에 추가하고, 더 작으면 왼쪽에 추가한다. 단, 비교할 대상이 없을때까지 내려가야 한다.
탐색 삽입과 마찬가지로 찾고자하는 데이터가 부모 노드보다 작으면 왼쪽, 크다면 오른쪽으로 탐색한다. 단, 탐색 도중 데이터를 찾았거나 마지막까지 탐색했다면 탐색을 중지한다.
삭제 임의의 노드(데이터)를 삭제하는 경우 삭제 후에도 이진 탐색 트리가 유지되도록 빈자리를 채워야 한다. 삭제에는 아래 3가지 경우가 있어 각각 다른 방식으로 삭제를 해야한다. 1) 단말 노드를 삭제할 경우 2) 하나의 자식 노드를 가진 노드를 삭제할 경우 3) 두 개의 자식 노드를 가진 노드를 삭제할 경우
1) 단말 노드를 삭제할 경우
2) 하나의 자식 노드를 가진 노드를 삭제할 경우
10을 삭제할 경우 자식 노드 13을 10의 위치로 복사하고 13의 노드를 삭제한다.
3) 두 개의 자식 노드를 가진 노드를 삭제할 경우
13을 이동시킨 이유는 이진 탐색 트리는 부모 노드의 왼쪽은 부모 노드보다 작은값, 오른쪽은 큰 값이 되어야 하므로 13을 이동시켰음. 18을 이동시켜도 상관없음
package BinarySearchTree;
public class BTreeNode {
int data;
BTreeNode leftNode;
BTreeNode rightNode;
}
[BST.java]
package BinarySearchTree;
public class BST extends BinaryTree {
private BTreeNode rootNode = null;
public void insert(int data) {
// 첫 데이터가 추가됐을 때
if (rootNode == null) {
rootNode = new BTreeNode();
setData(rootNode, data);
return;
}
BTreeNode curNode = rootNode;
BTreeNode parentNode = null;
// 현재 노드에 데이터가 없을때까지 반복
while(curNode != null) {
// 키는 유일해야 하므로 중복값이 있을 경우 빠져나옴
if (getData(curNode) == data) {
return;
}
// 자식노드가 없을 때 데이터 추가를 위해 부모노드의 값을 유지하고 있어야 함
parentNode = curNode;
// 현재 노드의 값이 삽입할 데이터의 값보다 크면 현재 노드의 왼쪽 서브트리에 데이터가 있다는 것이 되므로 왼쪽을 반환
if (getData(curNode) > data) {
curNode = getLeftSubTree(curNode);
}
else {
curNode = getRightSubTree(curNode);
}
}
BTreeNode newNode = new BTreeNode();
setData(newNode, data);
// 부모 노드의 값이 삽입할 데이터보다 크면 부모 노드의 왼쪽에 데이터를 삽입해야 하므로 왼쪽에 데이터를 등록함
if (getData(parentNode) > data) {
createLeftSubTree(parentNode, newNode);
}
else {
createRightSubTree(parentNode, newNode);
}
}
// 단순 검색 (존재 유무만 판단함)
public boolean search(int data) {
BTreeNode curNode = rootNode;
// 현재 가리키고 있는 노드가 null일 때까지 반복해서 확인
while(curNode != null) {
// 현재 노드의 값이 찾으려는 대상과 같으면 true
if (getData(curNode) == data) {
return true;
}
// 현재 노드의 값이 찾으려는 대상의 값보다 크면 왼쪽 서브트리에 찾을 대상이 있다는 것이므로 현재 노드의 왼쪽을 반환
else if (getData(curNode) > data){
curNode = getLeftSubTree(curNode);
}
else {
curNode = getRightSubTree(curNode);
}
}
return false;
}
public boolean remove(int data) {
// 삭제할 노드가 있는지 검색
BTreeNode deleteNode = rootNode;
BTreeNode deleteParentNode = null;
while (deleteNode != null && getData(deleteNode) != data) {
deleteParentNode = deleteNode;
if (getData(deleteNode) > data) {
deleteNode = getLeftSubTree(deleteNode);
}
else {
deleteNode = getRightSubTree(deleteNode);
}
}
// 찾는 데이터가 없다면 false
if (deleteNode == null) {
return false;
}
// 단말노드 삭제 시
if (getLeftSubTree(deleteNode) == null && getRightSubTree(deleteNode) == null) {
if (getLeftSubTree(deleteParentNode) == deleteNode) {
removeLeftSubTree(deleteParentNode);
}
else {
removeRightSubTree(deleteParentNode);
}
}
// 자식노드가 하나인 노드 삭제 시
else if (getLeftSubTree(deleteNode) == null || getRightSubTree(deleteNode) == null) {
// 삭제할 데이터가 부모노드의 왼쪽에 있는지 오른쪽에 있는지 확인
if (getLeftSubTree(deleteParentNode) == deleteNode) {
// 부모노드의 왼쪽값이 null이 아니면 왼쪽에 데이터가 있다는 것이므로
// 부모노드의 왼쪽과 삭제할 데이터의 왼쪽을 연결해 이어줌
if (getLeftSubTree(deleteNode) != null) {
deleteParentNode.leftNode = deleteNode.leftNode;
}
// 부모노드의 오른쪽값이 null이 아니면 오른쪽에 데이터가 있다는 것이므로
// 부모노드의 왼쪽과 삭제할 데이터의 오른쪽을 연결해 이어줌
else {
deleteParentNode.leftNode = deleteNode.rightNode;
}
}
else {
if (getRightSubTree(deleteNode) != null) {
deleteParentNode.rightNode = deleteNode.rightNode;
}
else {
deleteParentNode.rightNode = deleteNode.leftNode;
}
}
}
// 자식노드가 둘인 노드 삭제 시
else {
// 이진 탐색 트리의 특성 상 부모의 오른쪽 서브트리에서 가장 작은 값으로 부모노드를 변경해주어야 함
BTreeNode replaceNode = getRightSubTree(deleteNode);
BTreeNode replaceParentNode = deleteNode;
while(getLeftSubTree(replaceNode) != null) {
replaceParentNode = replaceNode;
replaceNode = getLeftSubTree(replaceNode);
}
// 위 로직을 거치면 deleteNode는 삭제할 노드 대신 들어갈 노드를 가리키고,
// deleteParentNode는 대신 들어갈 노드의 부모를 가리키게 됨.
setData(deleteNode, getData(replaceNode));
// 대신 들어갈 노드의 부모 노드의 왼쪽이 대신 들어갈 노드라면
// 대신 들어갈 노드의 오른쪽 서브트리를 부모 노드의 왼쪽으로 연결한다.
if (getLeftSubTree(replaceParentNode) == replaceNode) {
replaceParentNode.leftNode = replaceNode.rightNode;
}
// 대신 들어갈 노드의 부모 노드의 오른쪽이 대신 들어갈 노드라면
// 부모 노드의 오른쪽을 대신 들어갈 노드의 오른쪽 노드와 연결한다.
else {
replaceParentNode.rightNode = replaceNode.rightNode;
}
}
return true;
}
private void removeLeftSubTree(BTreeNode node) {
BTreeNode removeNode = node.leftNode;
node.leftNode = null;
removeNode = null;
}
private void removeRightSubTree(BTreeNode node) {
BTreeNode removeNode = node.rightNode;
node.rightNode = null;
removeNode = null;
}
// 중위 순회
void InorderTraverse(BTreeNode node) {
if (node == null){
return;
}
InorderTraverse(node.leftNode);
System.out.print(node.data + " ");
InorderTraverse(node.rightNode);
}
public void showAll() {
InorderTraverse(rootNode);
System.out.println();
}
}
[BSTMain.java]
package BinarySearchTree;
public class BSTMain {
public static void main(String[] args) {
BST bst = new BST();
bst.insert(5); bst.insert(8);
bst.insert(1); bst.insert(6);
bst.insert(4); bst.insert(9);
bst.insert(3); bst.insert(2);
bst.insert(7);
bst.showAll();
bst.remove(3); bst.showAll();
bst.remove(8); bst.showAll();
bst.remove(1); bst.showAll();
bst.remove(6); bst.showAll();
}
}
테스트
두 개의 자식 노드가 있는 노드를 삭제할 때 헷갈린 부분이 있었다.
처음에는 대체할 부모의 노드의 왼쪽은 당연히 대체할 노드일 것이라고 생각해서 위 코드가 이해가 되지 않았다. 그러나 아래 그림을 삭제에 대입해서 생각해보니 당연한 얘기였다.
12를 삭제 시 위 코드의 if문에 들어가게 되고, 8을 삭제 시 else 문을 들어가게 된다. 데이터는 12, 8, 4, 6, 9, 10, 17, 13, 21 을 넣고 테스트해보면 된다.
균일하게 n개의 데이터가 분포되어 정렬된 배열이 있을 경우 이진 탐색보다 성능이 좋음 ex) 10, 12, 13, 15, 18, 22, 25, 26, 27, 30, ... => 성능 ↑ 10, 102, 192, 375, 462, 1777, ... => 성능 ↓
이진 탐색은 탐색 대상의 값과 상관없이 무조건 절반씩 잘라서 비교하지만, 보간 탐색은 탐색 대상이 앞쪽에 있을 경우 앞쪽부터 탐색을 진행
선형 보간법을 이용해 탐색 위치를 결정함
보간 탐색 방법
탐색을 시작할 위치를 공식을 통해 알아낸다.
해당 위치에 탐색 대상이 있을 경우 해당 위치 값을 반환한다.
해당 위치의 값이 탐색 대상보다 작으면 탐색 대상의 왼쪽을 다시 탐색하고, 크다면 오른쪽을 탐색한다.
탐색 대상을 찾거나 탐색범위가 0이 될 때까지 1~3 과정을 반복한다.
탐색 위치 지정 공식 직선의 방정식 : \(y = mx + c\) 를 이용 (y : 배열의 값, x : 배열 값의 인덱스, m : 기울기) low, high, a를 방정식에 넣어서 계산 \(arr[high] = m * high + c\) \(arr[low] = m * low + c\) \(arr[a] = m * a + c\)
두 점의 좌표를 알면 기울기를 구할 수 있음 \((low, arr[low]), (high, arr[high])\) 일 때, 기울기 : \(\frac{arr[high]-arr[low]}{high-low}\)
\(arr[a] = m * a + c\) 수식에서 c를 제외하고 왼쪽으로 옮기면 아래와 같이 수식이 된다. \(c = arr[a] - m * a\) 찾고자 하는 인덱스는 음수가 나올 수 없으므로 이를 \(arr[low] = m * low + c\)에 대입한다. \(arr[low] = m * low + arr[a] - m * a\) \(m * a = m * low + arr[a] - arr[low]\) \(a = low + \frac{(arr[a] - arr[low])}{m}\) m(기울기)은 위에서 구했으므로 대입하면 최종적으로 아래와 같이 수식이 나온다. $$a = low + \frac{(arr[a] - arr[low])}{(arr[high]-arr[low])} * (high - low)$$
arr[a] : 탐색 대상 a : 찾고자하는 인덱스
구현
기본 구현 [InterpolationBasic.java]
package Search.Interpolation;
public class InterpolationBasic {
public static int search(int[] arr, int start, int end, int target) throws Exception {
// 찾고자하는 값의 인덱스
int targetIndex = 0;
// 재귀 탈출 조건
// 재귀가 계속해서 호출될수록 아래 targetIndex - 1 또는 targetIndex + 1에 의해
// 값이 배열의 범위에서 벗어날 수 있음
if (arr[start] > target || arr[end] < target) {
throw new Exception("데이터를 찾을 수 없습니다.");
}
// 데이터의 모든 값이 중복된 경우 (10, 10, 10, 10, 10 등)
// targetIndex를 구할 때 DivideByZero 예외가 발생하게 되므로 처음과 끝을 확인
else if (arr[start] == arr[end]) {
if (arr[start] == target) {
return start;
}
else {
throw new Exception("데이터를 찾을 수 없습니다.");
}
}
// double로 계산 후 다시 int로 변환한 이유는 아래와 같다.
// 10 ~ 30까지의 범위에서 12값을 찾을 때, 아래 수식은
// ((12 - 10) / (30 - 10) * (20 - 0)) + 0 => (1/10 * 20) + 0 이 된다.
// 그러나, 1/10은 int에서는 0으로 변환되므로 최종값은 0이 되기 때문에 double형으로 먼저 계산 후 int형으로 바꿔주는 방식으로 구현해야 한다.
targetIndex = (int)((double)(target-arr[start]) / (arr[end] - arr[start]) * (end - start)) + start;
System.out.println("targetIndex : " + targetIndex);
if (arr[targetIndex] == target) {
return targetIndex;
}
else if (target < arr[targetIndex]) {
return search(arr, start, targetIndex - 1, target);
}
else {
return search(arr, targetIndex + 1, end, target);
}
}
}
테스트 [InterpolationBasicMain.java]
package Search.Interpolation;
import java.util.Arrays;
public class InterpolationBasicMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) throws Exception {
int[] arr = new int[MAX_COUNT];
for(int i=0; i<MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int)(Math.random() * MAX_COUNT);
}
Arrays.sort(arr);
System.out.println("배열 값 출력");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
int search = InterpolationBasic.search(arr, 0, arr.length - 1, 5);
System.out.println("탐색완료 : " + search);
}
}
결과
이진 탐색과 보간 탐색 비교
데이터 100개를 임의생성한 후 특정 값을 찾는데 몇 번의 탐색 인덱스값을 설정했는지 확인
package Search;
import Search.BinarySearch.BinarySearchBasic;
import Search.Interpolation.InterpolationBasic;
import java.util.Arrays;
public class SearchCompareTest {
private static final int MAX_COUNT = 100;
public static void main(String[] args) throws Exception {
int[] arr = new int[MAX_COUNT];
for(int i=0; i<MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int)(Math.random() * MAX_COUNT);
}
Arrays.sort(arr);
int searchBinary = BinarySearchBasic.search(arr, 0, arr.length - 1, 10);
System.out.println("searchBinary : " + searchBinary);
System.out.println();
int searchInter = InterpolationBasic.search(arr, 0, arr.length - 1, 10);
System.out.println("searchInter : " + searchInter);
}
}
결과
이진 탐색의 경우 무조건 절반씩 잘라서 탐색하기 때문에 7번의 탐색만에 찾았지만, 보간 탐색의 경우 탐색 대상이 앞쪽에 있는지, 뒷쪽에 있는지 확인한 후 탐색 인덱스를 결정하기 때문에 성능이 더 좋다. (데이터 산포가 적을 경우에만)
적용할 수 있는 범위가 제한적임 - 정수, 알파벳, 특수문자 등의 아스키로 표현할 수 있는 것들 - 소수는 불가능
기수 (Radix)를 이용한 정렬 - 2진수의 경우 : 0, 1 / 10진수의 경우 : 0 ~ 9 / 알파벳 소문자의 경우 : a ~ z (0 ~ 25)
기수만큼의 추가 저장 공간이 필요함 - 저장 공간을 버킷 (Bucket) 이라고 부름
Queue를 이용한 정렬 알고리즘
LSD (Least Significant Digit) 정렬 방법과 MSD (Most Significant Digit) 정렬 방법이 있음 - LSD : 덜 중요한 첫번째 자리수부터 정렬 (즉, 가장 작은 자리수) ex) 1234 일 경우 4부터 정렬 - MSD : 가장 중요한 마지막 자리수부터 정렬 (즉, 가장 큰 자리수) ex) 1234 일 경우 1부터 정렬 MSD의 경우 구현의 난이도가 높으며 중간에 데이터를 확인해야 하는 단점이 있음
안정 정렬 (Stable Sort) - 동일한 데이터의 순서가 정렬 후에도 변함이 없음 ex) 5(A), 5(B), 3, 2, 1 => 1, 2, 3, 5(A), 5(B)
비 제자리 정렬 (out of place) - 정렬 시 추가적인 저장공간(버킷)이 필요하므로 제자리 정렬이 아님
기수정렬 방법
기수만큼 큐(Queue)를 이용해 저장공간 (Bucket)을 생성한다.
데이터의 1의 자리를 기준으로 버킷에 넣는다.
버킷에 저장된 데이터를 순서대로 꺼내 기존 데이터에 덮어쓴다.
데이터의 10의 자리를 기준으로 버킷에 넣는다.
마지막 자리수까지 정렬의 기준이 될 자리수를 늘리며 정렬한다.
윤성우의 열혈 자료구조
성능
비교연산이 아닌 데이터 삽입과 추출의 빈도수로 성능을 평가함
길이가 가장 긴 자리수를 k, 데이터 개수를 n 이라고 했을 때, k 자리수 까지의 반복과 데이터 n개를 반복해서 정렬하므로 k * n 이 된다.
최악의 경우 : O(kn)
최선의 경우 : O(kn)
구현
LSD로 구현 [RadixBasic.java]
package Sort.Radix;
import java.util.LinkedList;
import java.util.Queue;
public class RadixBasic {
// 10진수 기준으로 구현
private static int BUCKET_NUM = 10;
public static void sort(int[] arr) {
// 10진수 버킷 생성
Queue<Integer>[] bucket = new LinkedList[BUCKET_NUM];
for(int i=0; i<BUCKET_NUM; i++) {
bucket[i] = new LinkedList<>();
}
int maxLen = maxDigitCount(arr);
// 각 자리수의 숫자 저장
int digitNumber = 0;
// 배열에 다시 저장할 때 필요한 변수
int arrIndex = 0;
// 자리수만큼 반복
for(int i=0; i<maxLen; i++) {
// 데이터의 개수만큼 반복
for(int j=0; j<arr.length; j++) {
digitNumber = getDigit(arr[j], i);
bucket[digitNumber].add(arr[j]);
}
// 버킷에 들어간 데이터를 순서대로 꺼내 배열에 덮어씌움
for(int j=0; j<BUCKET_NUM; j++) {
while (!bucket[j].isEmpty()) {
arr[arrIndex++] = bucket[j].remove();
}
}
arrIndex = 0;
}
}
// 숫자의 자리수 반환
// getDigit(123, 0) => 3
// getDigit(123, 1) => 2
// getDigit(123, 2) => 1
private static int getDigit(int num, int index) {
return (int)Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
}
// 숫자의 자리수 구하기
// digitCount(10) => 2
// digitCount(1) => 1
// digitCount(1000) => 4
private static int digitCount(int num) {
if (num == 0) {
return 1;
}
// log10을 하면 자리수가 나옴
// log10(10) => 1
// log10(100) -> log10(10^2) => 2
return (int)Math.floor(Math.log10(Math.abs(num))) + 1;
}
// 데이터들 중 가장 큰 자리수 반환
private static int maxDigitCount(int[] arr) {
int max = 0;
for(int i=0; i<arr.length; i++) {
max = Math.max(max, digitCount(arr[i]));
}
return max;
}
}
테스트 [RadixBasicMain.java]
package Sort.Radix;
public class RadixBasicMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) {
int[] arr = new int[MAX_COUNT];
for(int i=0; i<MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int)(Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("정렬 후 데이터 (오름차순)");
int[] radixSortTestArray = arr.clone();
RadixBasic.sort(radixSortTestArray);
for(int i : radixSortTestArray) {
System.out.print(i + " ");
}
System.out.println();
}
}
제자리 정렬 (in-place sort) - 데이터 크기만큼의 저장공간을 제외하고 추가적인 공간이 필요하지 않음
퀵정렬 방법
데이터들 중 하나를 골라 피벗으로 설정
데이터 리스트의 앞과 뒤에서 탐색하며 피벗보다 작은 값들은 앞에 오고 피벗보다 큰 값들은 뒤로 가도록 분할
분할된 리스트에 1, 2 과정을 반복
1, 2 과정을 반복할 때마다 최소 하나 이상 정렬이 됨 - 피벗값 기준으로 왼쪽은 작은값, 오른쪽은 큰 값이기 때문
성능
시간복잡도 최악의 경우 : O(n^2) 최선의 경우 : O(nlog2(n)) 평균의 경우 : O(nlog2(n))
피벗 데이터가 자신의 위치를 찾아가기 위해서는 데이터 개수 (n) 만큼의 비교연산이 필요
피벗값이 항상 리스트의 가운데에 있다고 가정할 때, 데이터들은 절반씩 나누어짐
초기상태
1 덩어리
분할 0번
17을 둘로 나누면
2 덩어리
분할 1번
8을 둘로 나누면
4 덩어리
분할 2번
위와 같은 과정을 거치게 되면 최종적으로 분할횟수 = log2(데이터 개수) 가 된다.
리스트가 이미 정렬되어 있고 피벗값이 항상 데이터들 중 가장 작은 값일 때, 데이터들은 n, n-1, n-2, ... 로 나누어짐 - 피벗값이 리스트 내 데이터들 중 항상 작으므로 피벗과 이미 정렬된 데이터를 제외하고 모두 비교해야 하므로 분할횟수 = 데이터 개수가 된다.
그러나, 퀵정렬의 경우 최악의 경우를 빅-오로 사용하지 않음 - 중간에 가까운 피벗을 선택함으로써 최선의 경우에 가까운 성능을 평균적으로 보이기 때문
구현
기본 구현 [QuickBasic.java]
package Sort.Quick;
public class QuickBasic {
public static void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int start, int end) {
// end가 start보다 크다는 것은 더 나눌 데이터가 남아있다는 것이 됨
if (start <= end) {
// 피벗 대상이 될 인덱스 반환
int pivotIndex = partition(arr, start, end);
// 피벗 기준으로 왼쪽 데이터 분할
quickSort(arr, start, pivotIndex - 1);
// 피벗 기준으로 오른쪽 데이터 분할
quickSort(arr, pivotIndex + 1, end);
}
}
private static int partition(int[] arr, int start, int end) {
// 배열의 처음, 중간, 끝의 데이터를 정렬해 크기가 중간인 데이터를 배열의 첫번째로 옮기는 과정
medianOfThree(arr, start, end);
// 피벗값을 제외하고 탐색해야 하므로 + 1
int leftIndex = start + 1;
int rightIndex = end;
int pivotData = arr[start];
// 탐색 인덱스들이 서로 지나치지 않았다면 반복
// 지나쳤다면 해당 피벗을 이용한 탐색이 끝났으므로 반복문 종료
while(leftIndex <= rightIndex) {
// 피벗 데이터보다 큰 값이 나올때까지 탐색
// leftIndex를 비교하는 부분이 앞으로 와야 함. 피벗값과 데이터가 같을 때 인덱스를 벗어날 수 있음. (ex. 4 4 1 2 2)
while(leftIndex <= end && arr[leftIndex] <= pivotData) {
leftIndex++;
}
// 피벗 데이터보다 작은 값이 나올때까지 탐색
// 피벗 데이터는 탐색에서 제외해야 함
// rightIndex를 비교하는 부분이 앞으로 와야 함. 피벗값과 데이터가 같을 때 인덱스를 벗어날 수 있음.
while(rightIndex >= start + 1 && arr[rightIndex] >= pivotData) {
rightIndex--;
}
// 서로의 인덱스가 지나치지 않았을 때 교환
if (leftIndex <= rightIndex) {
swap(arr, leftIndex, rightIndex);
}
}
// 피벗값과 rightIndex가 가리키는 값과 교환
// rightIndex는 피벗값보다 작은 값을 탐색하는데, 서로 인덱스가 지나쳐 탐색이 끝나게 되면
// 피벗보다 큰 값과 작은값이 결정되는 경계를 rightIndex가 가리키고 있기 때문에 교환해야 함
swap(arr, start, rightIndex);
return rightIndex;
}
// 처음, 중간, 끝의 데이터를 비교해 중간의 값을 피벗으로 정하고 연산을 쉽게 하기 위해
// 해당 피벗값을 가장 왼쪽 값과 교환
private static void medianOfThree(int[] arr, int start, int end) {
int[] index = {start, (start + end) / 2, end};
if (arr[index[0]] > arr[index[1]]) {
swap(index, 0, 1);
}
if (arr[index[1]] > arr[index[2]]) {
swap(index, 1, 2);
}
if (arr[index[0]] > arr[index[1]]) {
swap(index, 0, 1);
}
swap(arr, start, index[1]);
}
private static void swap(int[] arr, int idx1, int idx2) {
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
테스트 [QuickBasicMain.java]
package Sort.Quick;
public class QuickBasicMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) {
int[] arr = new int[MAX_COUNT];
for(int i=0; i<MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int)(Math.random() * MAX_COUNT);
}
// int[] arr = {4, 4, 1, 2, 2};
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("정렬 후 데이터 (오름차순)");
int[] quickSortTestArray = arr.clone();
QuickBasic.sort(quickSortTestArray);
for(int i : quickSortTestArray) {
System.out.print(i + " ");
}
System.out.println();
}
}
최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 힙 구성 후 삭제를 반복하면 다음 최대값이 루트노드가 되어 결국 내림차순 정렬이 됨
성능
시간복잡도 최악의 경우 : n log2(n) 최선의 경우 : n log2(n) : 데이터 저장 및 삭제의 시간복잡도 log2(n) : 정렬할 데이터가 n개인 경우 n개의 데이터를 저장 및 삭제해야 하므로 n
데이터 저장 및 삭제의 시간복잡도 - 트리의 높이가 하나씩 증가할 때마다 데이터의 수는 증가 전 높이의 데이터 수보다 최대 2배 증가한다.
그러나 데이터를 추가 및 삭제할 때는 부모노드와 같을 비교하기 때문에 데이터의 수는 2배 증가하지만 비교횟수는 1회 증가되는 것으로 이를 일반화하면 대략적으로 비교횟수 = log2(데이터 개수)이 된다.
구현
기본 구현 [HeapBasic.java]
package Sort.Heap;
import java.util.Collections;
import java.util.PriorityQueue;
public class HeapBasic {
public static void sort(int[] arr, boolean isDescending) {
PriorityQueue<Integer> pq = null;
pq = init(isDescending);
add(pq, arr);
for(int i=0; i<arr.length; i++) {
arr[i] = pq.remove();
}
}
private static PriorityQueue init(boolean isDescending) {
PriorityQueue pq = null;
// 내림차순일 경우 최대힙으로 구성
if (isDescending) {
pq = new PriorityQueue<>(Collections.reverseOrder());
}
// 오름차순일 경우 최소힙으로 구성
else {
pq = new PriorityQueue<>();
}
return pq;
}
private static void add(PriorityQueue pq, int[] arr) {
for(int i=0; i<arr.length; i++) {
pq.add(arr[i]);
}
}
private static int delete(PriorityQueue pq) {
return (int)pq.remove();
}
}
테스트 [HeapBasicMain.java]
package Sort.Heap;
public class HeapBasicMain {
private static final int MAX_COUNT = 10;
public static void main(String[] args) {
int[] arr = new int[MAX_COUNT];
for (int i = 0; i < MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int) (Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("정렬 후 데이터 (오름차순)");
int[] ascHeapSortTestArray = arr.clone();
HeapBasic.sort(ascHeapSortTestArray, false);
for(int i : ascHeapSortTestArray) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("정렬 후 데이터 (내림차순)");
int[] descHeapSortTestArray = arr.clone();
HeapBasic.sort(descHeapSortTestArray, true);
for(int i : descHeapSortTestArray) {
System.out.print(i + " ");
}
System.out.println();
}
}
정렬 시 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)가 될 수 없음
합병 정렬 방법
분할 (divide) : 데이터 리스트에서 데이터가 하나씩 정렬될 때까지 리스트를 절반씩 나눈다.
정복 (conquer) : 나눈 데이터들끼리 재귀적으로 정렬을 진행한다.
결합 (combine) : 정렬된 데이터들을 하나로 합친다.
성능
시간복잡도 최악의 경우 : O(n log2(n)) 최선의 경우 : O(n log2(n))
분할 데이터의 개수가 8개라고 했을 때 3번의 분할과정을 통해 8 -> 4 -> 2 -> 1 (2^3 -> 2^2 -> 2^1 -> 2^0) 순으로 줄어들게 된다. 따라서 분할과정은 3 = log2(8)이 되므로 결국 분할횟수 = log2(데이터 개수) 가 된다.
정복 및 결합 데이터 8개를 2개씩 결합하면 총 4개의 덩어리가 나오게 되며 데이터마다 비교하게 되면 최대 2번 비교하게 된다. 따라서 데이터 2개와 4개의 덩어리를 곱하면 최대 8번의 비교 횟수가 나온다. 다시 데이터 4개와 2개의 덩어리를 곱하면 8번이 되므로 각 병합의 단계마다 최대 데이터 개수만큼 비교하게 되어 병합 횟수 = 데이터 개수가 된다.
구현
기본 구현 [MergeBasic.java]
package Sort.Merge;
public class MergeBasic {
public static void sort(int[] arr, int left, int right) {
mergeSort(arr, left, right);
}
private static void mergeSort(int[] arr, int left, int right) {
int mid = 0;
if (left < right) {
mid = (left + right) / 2; // 데이터 리스트의 중앙 인덱스를 구함
mergeSort(arr, left, mid); // 중앙을 기준으로 왼쪽 데이터들을 분할한다.
mergeSort(arr, mid + 1, right); // 중앙을 기준으로 오른쪽 데이터들을 분할한다.
merge(arr, left, mid, right); // 정복 및 결합 과정을 진행한다.
}
}
private static void merge(int[] arr, int left, int mid, int right) {
// 분할된 왼쪽 리스트들의 시작점 변수
int leftIndex = left;
// 분할된 오른쪽 리스트들의 시작점 변수
int rightIndex = mid + 1;
// 정렬된 데이터가 저장될 인덱스
int sortedIndex = left;
// 정렬된 데이터를 임시로 저장할 곳
int[] tmpSortedArray = new int[right + 1];
// 분할된 왼쪽 리스트의 인덱스가 mid까지 온 경우 왼쪽 정렬 완료
// 분할된 오른쪽 리스트의 인덱스가 right까지 온 경우 오른쪽 정렬 완료
// 즉, 왼쪽 또는 오른쪽 둘 중 하나라도 정렬이 완료된 경우 반복문을 빠져나감
while(leftIndex <= mid && rightIndex <= right) {
// 오름차순 조건문
if (arr[leftIndex] <= arr[rightIndex]) {
tmpSortedArray[sortedIndex++] = arr[leftIndex++];
}
else {
tmpSortedArray[sortedIndex++] = arr[rightIndex++];
}
}
// 왼쪽이 다 정렬된 경우 오른쪽 데이터들의 남은 부분들을 다 옮겨야 함
if (leftIndex > mid) {
for(int i=rightIndex; i<=right; i++) {
tmpSortedArray[sortedIndex++] = arr[i];
}
}
else {
for(int i=leftIndex; i<=mid; i++) {
tmpSortedArray[sortedIndex++] = arr[i];
}
}
// 원래 배열에 정렬된 데이터로 덮어씌움
for(int i=left; i<=right; i++) {
arr[i] = tmpSortedArray[i];
}
}
}
테스트 [MergeBasicMain.java]
package Sort.Merge;
public class MergeBasicMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) {
int[] arr = new int[MAX_COUNT];
for(int i=0; i<MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int)(Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("정렬 후 데이터 (오름차순)");
int[] ascSortedArrayTest = arr.clone();
MergeBasic.sort(ascSortedArrayTest, 0, ascSortedArrayTest.length - 1);
for(int i : ascSortedArrayTest) {
System.out.print(i + " ");
}
System.out.println();
}
}
제자리 정렬 (in-place sort) - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
선택 정렬, 버블 정렬보다 비교적 빠르지만 마찬가지로 배열이 클수록 효율이 떨어짐
선택 정렬과 비슷하지만 선택 정렬은 배열의 모든 값을 탐색해 최소값을 구한 후 정렬하는 방식이지만 삽입 정렬은 데이터의 앞쪽을 탐색하며 자신의 위치를 찾아 정렬함
삽입 정렬 방법
배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성시킴
자신의 위치를 찾는 방법은 arr[i - 1] <= X < arr[i] 가 만족하는 위치가 있다면 해당 위치에 X값을 삽입함
삽입될 위치의 뒤 인덱스들을 하나씩 뒤로 미뤄 X가 들어갈 공간을 만들어줌
성능
시간복잡도 최악의 경우 : O(n^2) - 배열의 데이터가 모두 역순일 때 (5, 4, 3, 2, 1) - 5, 4, 3, 2, 1의 예시에서보면 4와 5를 비교, 3과 4, 5비교, 2와 3, 4, 5 순으로 비교하게 되는데 비교횟수를 수식으로 나타내면 1 + 2 + 3 + 4 + ... + (n-1) 이 되므로 1/2n(n-1) 이 되어 n^2이 된다.
최선의 경우 : O(n) - 배열의 데이터가 모두 정렬되어 있을 때 (1, 2, 3, 4, 5) - 삽입 정렬은 앞쪽부터 정렬되기 때문에 정렬하려는 값 X가 바로 앞 데이터보다 클 경우 모든 앞쪽 데이터들을 확인할 필요가 없으므로 다음 데이터로 넘어가서 다시 비교하게 된다. 따라서, 이미 정렬이 된 상태인 경우 n번만 반복한 후 종료된다.
구현
기본 구현 [InsertionBasic.java]
package Sort.Insertion;
public class InsertionBasic {
public static void sort(int[] arr, boolean isDescending) {
// 현재값을 저장하기 위한 변수
int tmp = 0;
// 비교 대상의 인덱스 변수
int compareIndex = 0;
for(int i=1; i<arr.length; i++) {
// 현재값 저장
tmp = arr[i];
// 현재값 바로 앞 인덱스값 저장
compareIndex = i - 1;
// 앞쪽 데이터들이 현재값보다 작을때까지 반복
// 앞쪽 데이터들을 뒤로 당기는 과정
while(compareIndex >= 0 && !isSortTwoElements(arr[compareIndex], tmp, isDescending)) {
arr[compareIndex + 1] = arr[compareIndex];
compareIndex--;
}
// 빈 공간에 데이터 저장
arr[compareIndex + 1] = tmp;
}
}
/**
*
* @param cmp1 비교할 값
* @param cmp2 비교할 값
* @param isDescending 내림차순 및 오름차순 선택
* @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true
* 오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false
*/
private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) {
// 내림차순일 경우
if (isDescending) {
if (cmp1 < cmp2) {
return false;
}
else {
return true;
}
}
// 오름차순일 경우
else {
if (cmp1 < cmp2) {
return true;
}
else {
return false;
}
}
}
}
테스트
package Sort.Insertion;
public class InsertionBasicMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) {
int[] arr = new int[MAX_COUNT];
for (int i = 0; i < MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int) (Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
int[] ascInsertionTestArray = arr.clone();
System.out.println("정렬 후 데이터 (오름차순)");
InsertionBasic.sort(ascInsertionTestArray, false);
for(int i : ascInsertionTestArray) {
System.out.print(i + " ");
}
System.out.println();
int[] descInsertionTestArray = arr.clone();
System.out.println("정렬 후 데이터 (내림차순)");
InsertionBasic.sort(descInsertionTestArray, true);
for(int i : descInsertionTestArray) {
System.out.print(i + " ");
}
System.out.println();
}
}
결과
클래스 정렬을 위한 구현 [InsertionAdvanced.java]
package Sort.Insertion;
import java.util.Comparator;
public class InsertionAdvanced {
public static <T> void sort(T[] arr) {
T tmp = null;
int compareIndex = 0;
for(int i=1; i<arr.length; i++) {
tmp = arr[i];
compareIndex = i - 1;
while(compareIndex >= 0 && ((Comparable<? super T>)arr[compareIndex]).compareTo(tmp) > 0) {
arr[compareIndex + 1] = arr[compareIndex];
compareIndex--;
}
arr[compareIndex + 1] = tmp;
}
}
public static <T> void sort(T[] arr, Comparator<? super T> comp) {
T tmp = null;
int compareIndex = 0;
for(int i=1; i<arr.length; i++) {
tmp = arr[i];
compareIndex = i - 1;
while (compareIndex >= 0 && comp.compare(arr[compareIndex], tmp) > 0) {
arr[compareIndex + 1] = arr[compareIndex];
compareIndex--;
}
arr[compareIndex + 1] = tmp;
}
}
}
테스트
package Sort.Insertion;
import Sort.Selection.SelectionAdvanced;
import java.util.Comparator;
public class InsertionAdvancedMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) {
Integer[] arr = new Integer[MAX_COUNT];
for (int i = 0; i < MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int) (Math.random() * MAX_COUNT);
}
System.out.println("정렬 전 데이터");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
Integer[] ascInsertionTestArray = arr.clone();
System.out.println("정렬 후 데이터 (오름차순)");
InsertionAdvanced.sort(ascInsertionTestArray);
for(int i : ascInsertionTestArray) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
class Student {
String name;
int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "name='" + name + '\'' +
", age=" + age;
}
}
Student[] students = new Student[5];
students[0] = new Student("아이언맨", 11);
students[1] = new Student("헐크", 4);
students[2] = new Student("토르", 15);
students[3] = new Student("블랙위도우", 13);
students[4] = new Student("캡틴", 4);
System.out.println("클래스 정렬 전 데이터");
for (int i=0; i<students.length; i ++) {
System.out.println(students[i]);
}
System.out.println();
System.out.println("클래스 정렬 후 데이터 (나이 내림차순)");
InsertionAdvanced.sort(students, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
if (o1.age < o2.age) {
return 1;
}
else if (o1.age == o2.age) {
return 0;
}
else {
return -1;
}
}
});
for (int i=0; i<students.length; i ++) {
System.out.println(students[i]);
}
}
}
