삽입 부모 노드와 삽입할 데이터를 비교해서 삽입할 데이터가 더 크면 오른쪽에 추가하고, 더 작으면 왼쪽에 추가한다. 단, 비교할 대상이 없을때까지 내려가야 한다.
탐색 삽입과 마찬가지로 찾고자하는 데이터가 부모 노드보다 작으면 왼쪽, 크다면 오른쪽으로 탐색한다. 단, 탐색 도중 데이터를 찾았거나 마지막까지 탐색했다면 탐색을 중지한다.
삭제 임의의 노드(데이터)를 삭제하는 경우 삭제 후에도 이진 탐색 트리가 유지되도록 빈자리를 채워야 한다. 삭제에는 아래 3가지 경우가 있어 각각 다른 방식으로 삭제를 해야한다. 1) 단말 노드를 삭제할 경우 2) 하나의 자식 노드를 가진 노드를 삭제할 경우 3) 두 개의 자식 노드를 가진 노드를 삭제할 경우
1) 단말 노드를 삭제할 경우
2) 하나의 자식 노드를 가진 노드를 삭제할 경우
10을 삭제할 경우 자식 노드 13을 10의 위치로 복사하고 13의 노드를 삭제한다.
3) 두 개의 자식 노드를 가진 노드를 삭제할 경우
13을 이동시킨 이유는 이진 탐색 트리는 부모 노드의 왼쪽은 부모 노드보다 작은값, 오른쪽은 큰 값이 되어야 하므로 13을 이동시켰음. 18을 이동시켜도 상관없음
균일하게 n개의 데이터가 분포되어 정렬된 배열이 있을 경우 이진 탐색보다 성능이 좋음 ex) 10, 12, 13, 15, 18, 22, 25, 26, 27, 30, ... => 성능 ↑ 10, 102, 192, 375, 462, 1777, ... => 성능 ↓
이진 탐색은 탐색 대상의 값과 상관없이 무조건 절반씩 잘라서 비교하지만, 보간 탐색은 탐색 대상이 앞쪽에 있을 경우 앞쪽부터 탐색을 진행
선형 보간법을 이용해 탐색 위치를 결정함
보간 탐색 방법
탐색을 시작할 위치를 공식을 통해 알아낸다.
해당 위치에 탐색 대상이 있을 경우 해당 위치 값을 반환한다.
해당 위치의 값이 탐색 대상보다 작으면 탐색 대상의 왼쪽을 다시 탐색하고, 크다면 오른쪽을 탐색한다.
탐색 대상을 찾거나 탐색범위가 0이 될 때까지 1~3 과정을 반복한다.
탐색 위치 지정 공식 직선의 방정식 : 를 이용 (y : 배열의 값, x : 배열 값의 인덱스, m : 기울기) low, high, a를 방정식에 넣어서 계산
두 점의 좌표를 알면 기울기를 구할 수 있음 일 때, 기울기 :
수식에서 c를 제외하고 왼쪽으로 옮기면 아래와 같이 수식이 된다. 찾고자 하는 인덱스는 음수가 나올 수 없으므로 이를 에 대입한다. m(기울기)은 위에서 구했으므로 대입하면 최종적으로 아래와 같이 수식이 나온다.
arr[a] : 탐색 대상 a : 찾고자하는 인덱스
구현
기본 구현 [InterpolationBasic.java]
package Search.Interpolation;
publicclassInterpolationBasic{
publicstaticintsearch(int[] arr, int start, int end, int target)throws Exception {
// 찾고자하는 값의 인덱스int targetIndex = 0;
// 재귀 탈출 조건// 재귀가 계속해서 호출될수록 아래 targetIndex - 1 또는 targetIndex + 1에 의해// 값이 배열의 범위에서 벗어날 수 있음if (arr[start] > target || arr[end] < target) {
thrownew Exception("데이터를 찾을 수 없습니다.");
}
// 데이터의 모든 값이 중복된 경우 (10, 10, 10, 10, 10 등)// targetIndex를 구할 때 DivideByZero 예외가 발생하게 되므로 처음과 끝을 확인elseif (arr[start] == arr[end]) {
if (arr[start] == target) {
return start;
}
else {
thrownew 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;
}
elseif (target < arr[targetIndex]) {
return search(arr, start, targetIndex - 1, target);
}
else {
return search(arr, targetIndex + 1, end, target);
}
}
}
적용할 수 있는 범위가 제한적임 - 정수, 알파벳, 특수문자 등의 아스키로 표현할 수 있는 것들 - 소수는 불가능
기수 (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;
publicclassRadixBasic{
// 10진수 기준으로 구현privatestaticint BUCKET_NUM = 10;
publicstaticvoidsort(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) => 1privatestaticintgetDigit(int num, int index){
return (int)Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
}
// 숫자의 자리수 구하기// digitCount(10) => 2// digitCount(1) => 1// digitCount(1000) => 4privatestaticintdigitCount(int num){
if (num == 0) {
return1;
}
// log10을 하면 자리수가 나옴// log10(10) => 1// log10(100) -> log10(10^2) => 2return (int)Math.floor(Math.log10(Math.abs(num))) + 1;
}
// 데이터들 중 가장 큰 자리수 반환privatestaticintmaxDigitCount(int[] arr){
int max = 0;
for(int i=0; i<arr.length; i++) {
max = Math.max(max, digitCount(arr[i]));
}
return max;
}
}
제자리 정렬 (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;
publicclassQuickBasic{
publicstaticvoidsort(int[] arr){
quickSort(arr, 0, arr.length - 1);
}
privatestaticvoidquickSort(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);
}
}
privatestaticintpartition(int[] arr, int start, int end){
// 배열의 처음, 중간, 끝의 데이터를 정렬해 크기가 중간인 데이터를 배열의 첫번째로 옮기는 과정
medianOfThree(arr, start, end);
// 피벗값을 제외하고 탐색해야 하므로 + 1int 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;
}
// 처음, 중간, 끝의 데이터를 비교해 중간의 값을 피벗으로 정하고 연산을 쉽게 하기 위해// 해당 피벗값을 가장 왼쪽 값과 교환privatestaticvoidmedianOfThree(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]);
}
privatestaticvoidswap(int[] arr, int idx1, int idx2){
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 힙 구성 후 삭제를 반복하면 다음 최대값이 루트노드가 되어 결국 내림차순 정렬이 됨
성능
시간복잡도 최악의 경우 : n log2(n) 최선의 경우 : n log2(n) : 데이터 저장 및 삭제의 시간복잡도 log2(n) : 정렬할 데이터가 n개인 경우 n개의 데이터를 저장 및 삭제해야 하므로 n
데이터 저장 및 삭제의 시간복잡도 - 트리의 높이가 하나씩 증가할 때마다 데이터의 수는 증가 전 높이의 데이터 수보다 최대 2배 증가한다.
그러나 데이터를 추가 및 삭제할 때는 부모노드와 같을 비교하기 때문에 데이터의 수는 2배 증가하지만 비교횟수는 1회 증가되는 것으로 이를 일반화하면 대략적으로 비교횟수 = log2(데이터 개수)이 된다.
정렬 시 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (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;
publicclassMergeBasic{
publicstaticvoidsort(int[] arr, int left, int right){
mergeSort(arr, left, right);
}
privatestaticvoidmergeSort(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); // 정복 및 결합 과정을 진행한다.
}
}
privatestaticvoidmerge(int[] arr, int left, int mid, int right){
// 분할된 왼쪽 리스트들의 시작점 변수int leftIndex = left;
// 분할된 오른쪽 리스트들의 시작점 변수int rightIndex = mid + 1;
// 정렬된 데이터가 저장될 인덱스int sortedIndex = left;
// 정렬된 데이터를 임시로 저장할 곳int[] tmpSortedArray = newint[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];
}
}
}
제자리 정렬 (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;
publicclassInsertionBasic{
publicstaticvoidsort(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
*/privatestaticbooleanisSortTwoElements(int cmp1, int cmp2, boolean isDescending){
// 내림차순일 경우if (isDescending) {
if (cmp1 < cmp2) {
returnfalse;
}
else {
returntrue;
}
}
// 오름차순일 경우else {
if (cmp1 < cmp2) {
returntrue;
}
else {
returnfalse;
}
}
}
}
테스트
package Sort.Insertion;
publicclassInsertionBasicMain{
privatestaticfinalint MAX_COUNT = 30;
publicstaticvoidmain(String[] args){
int[] arr = newint[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();
}
}
