반응형
선택정렬
- 정렬되지않은 데이터 중 순차적으로 가장 작은 수를 선택하고 교환해나가는 정렬
- 장점 : 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점 (풀스캔)
- 단점 : 데이터의 개수가 조금만 많아지더라도 아주 많은 연산을 해야하기때문에 오래걸림
- 시간복잡도 : O(N^2)
- 연산법 : N*(N+1) / 2
public class sortAl {
/** * 알고리즘 *
* * 1. i = 0 *
* * 2. i부터 N-1까지 가장 크거나 작은값을 찾는다. *
* * 3. i와 가장 크거나 작은값을 교환한다. 동일한 값일 경우 교환하지 않는다. *
* * 4. ++i * 5. 2부터 다시 반복한다. */
int value[] = {5, 3, 8, 2, 10, 9, 4, 1};
public void sort() {
for (int i = 0; i < value.length; i++) {
int minIndex = i;
int min = value[minIndex];
for (int j = i; j < value.length; j++) {
// TODO : 중요! < 와 <= 는 엄연하게 Stability 관점에서 교환하냐 안하냐가 달라질 수 있다.
if (value[j] < min) {
min = value[j];
minIndex = j;
}
}
swap(value, i, minIndex);
}
printValue();
}
private void swap(int array[], int index1, int index2) {
int tempValue = array[index1];
array[index1] = array[index2];
array[index2] = tempValue;
}
private void printValue() {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
버블정렬
- 서로 이웃한(옆에 있는) 값과 비교해 더 작은 값을 앞으로 보내는 정렬법(반복)
- 특징 : 선택 정렬과 같이 직관적인 알고리즘
- 단점 : 데이터의 개수가 조금만 많아지더라도 아주 많은 연산을 해야하기때문에 오래걸림(가장 비효율적)
- 시간복잡도 : O(N^2)
- 연산법 : N*(N+1) / 2
public class sortAl {
/** * * 알고리즘 *
* * 1. i = 0; *
* * 2. i가 n-1이면 끝낸다. *
* * 3. j = 1; *
* * 4. j가 n-i가 되면 7로 간다. *
* * 5. a[j-1] > a[j] 이면 두 값을 교환한다, *
* * 6. j를 하나 증가시키고 4로 돌아간다. *
* * 7. i를 하나 증가시키고 2로 돌아간다. */
int value[] = {5, 3, 8, 2, 10, 9, 4, 1};
public void sort() {
for (int i = 0; i < value.length - 1; i++) {
for (int j = 1; j < value.length - i; j++) {
if (value[j - 1] > value[j]) {
swap(value, j - 1, j);
}
}
}
printValue();
}
private void swap(int array[], int index1, int index2) {
int tempValue = array[index1];
array[index1] = array[index2];
array[index2] = tempValue;
}
private void printValue() {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
삽입정렬
- 아직 정렬되지 않은 데이터들을 이미 정렬된 부분의 적절한 위치에 삽입해가며 정렬
(자기 보다) 작은 수가 나올 때까지 우측으로 밀어 삽입하는 정렬
- 특징 : 필요할 때만 위치를 바꿈 -> 데이터가 이미 거의 정렬된 상태에서는 어떤 알고리즘보다 빠름
- 단점 : 비교적 느린 알고리즘
- 시간복잡도 : O(N^2)
- 연산법 : N*(N+1) / 2
public class sortAl {
/** * * 알고리즘 *
* * 1. i = 1 *
* * 2. j = i; *
* * 3. t = arr[i]
* * 3. array[j-1] > array[i] && j > 0 인동안 *
* * 3-1. array[j] = array[j-1]; *
* * 3-2. j--; *
* * 4. arr[j] = t; *
* * 5. i++; 반복 */
int value[] = {5, 3, 8, 2, 10, 9, 4, 1};
public void sort() {
for (int i = 1; i < value.length; i++) {
int j = i; int t = value[i];
while (j > 0 && value[j - 1] > t) {
value[j] = value[j - 1]; j--;
}
value[j] = t;
}
printValue();
}
private void printValue() {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
간접정렬
- 값의 배열이 아닌 인덱스 배열을 조작하는 정렬
- 특징 : 값의 배열이 아닌 별도의 인덱스 배열을 조작함
- 시간복잡도 : 삽입 정렬 시 O(N^2)
1. 값의 배열을 기준으로 비교하여 (자기 보다) 왼쪽에 작은 수가 나올 때까지 인덱스 값을 우측으로 민다.
2. 값의 배열을 기준으로 비교하여 왼쪽에 (자기 보다) 작은 수가 나오면 인덱스 값을 삽입한다.
public class sortAl {
int value[] = {5, 3, 8, 2, 10, 9, 4, 1};
int index[] = {0, 1, 2, 3, 4, 5, 6, 7};
public void sort() {
for (int i = 1; i < value.length; i++) {
int j = i; int t = index[i];
while (j > 0 && value[index[j - 1]] > value[t]) {
index[j] = index[j - 1]; j--;
}
index[j] = t;
}
printValue();
}
private void printValue() {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
쉘 정렬
- (자기보다) 작은 수가 나올 때까지 간격만큼 우측으로 밀어 삽입하는 정렬
- 특징 : 삽입 정렬의 확장된 개념, 가장 좋은 간격을 알아내야 하며 간격에 따라 시간복잡도가 달라짐
- 시간복잡도 : 평균O(N^1.5) 최악O(N^2)
- 간격의 초깃값 :
정렬할 값의 수/2
1. (자기 보다) 왼쪽에 작은 수가 나올 때까지 간격만큼 우측으로 민다.
2. 왼쪽 간격에 (자기 보다) 작은 수가 나오면 삽입한다.
3. 반복 후 간격을 줄인다.
public class sortAl {
/** * * 알고리즘 *
* * 1. Gap의 초기값을 구한다. *
* * 2. Gap가 1보다 작으면 끝낸다. *
* * 3. k = 0; *
* * 4. k가 Gap보다 크거나 같으면 7로 간다. *
* * 5. (Gap간격 + k) 요소들에 대해서 삽입정렬을 한다. *
* * 6. k를 하나 증가시키고 4로 간다. *
* * 7. Gap의 다음 값을 구하고 2로 간다. */
int value[] = {5, 3, 8, 2, 10, 9, 4, 1};
public void sort() {
for (int gap = value.length / 2; gap > 0; gap /= 2) {
for (int k = 0; k < gap; k++) {
// TODO : 간격을 중심으로 삽입정렬을 한다.
for (int i = k + gap; i < value.length; i += gap) {
int j = i;
int t = value[i];
while (j >= gap && value[j - gap] > t) {
value[j] = value[j - gap];
j -= gap; // 간격만큼 감소한 인덱스
}
value[j] = t;
}
}
}
printValue();
}
private void printValue() {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
카운팅 정렬/분포수세기 정렬/계수 정렬(직접기수 정렬)
- 특정 키값이 출현하는 빈도를 저장하여 누적분포를 이용해 정렬
- 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘
- 특징 : 같은 키가 많이 있는 배열에 한해 적용할 수 있는 알고리즘(한정된 용도에서만 적합)
- 배열의 크기가 커지면 그만큼 N이 커지므로 더 많은 메모리가 필요해진다.
- 시간복잡도 : O(N)
1. 값의 빈도를 누적분포로 저장한다.
2. 배열을 뒤에서부터 읽는다.
3. 새로운 배열에 빈도를 인덱스(빈도수-1)로 읽어 삽입한다.
4. 빈도 수를 감소시킨다. (반복)
public class sortAl {
/** * 알고리즘 *
* 1. count[] 배열을 0으로 초기화 *
* 2. array[] 배열의 키의 빈도를 계산하여 그 빈도를 count[]에 저장 *
* 3. count[] 배열을 누적분포로 변환 *
* 4. array[] 배열을 뒤에서부터 읽어서(--) b[--count[array[i]]에 저장 *
* 5. b[] 배열을 a[] 배열로 복사한다. *
*
* 예시 *
* 1 3 2 2 3 1 3 2 4 *
* count[1] = 2 (1의 갯수) *
* count[2] = 3 (2의 갯수) *
* count[3] = 3 (3의 갯수) *
* count[4] = 1 (4의 갯수) *
* 누적분포화 *
* count[1] = 2 *
* count[2] = count[1] + count[2] (5) *
* count[3] = count[2] + count[3] (8) *
* count[4] = count[3] + count[4] (9) */
int value[] = {1, 3, 2, 2, 3, 1, 3, 2, 4};
int temp[] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
int count[] = {0, 0, 0, 0, 0};
public void sort() {
for (int i = 0; i < value.length; i++) {
++count[value[i]];
}
for (int i = 2; i <= 4; i++) {
count[i] = count[i - 1] + count[i];
}
for (int i = value.length -1; i >= 0; i--) {
temp[--count[value[i]]] = value[i];
}
printValue();
}
private void printValue() {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
퀵 정렬(분할정복 알고리즘)
- 하나의 리스트를 특정한 값(피벗값)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 분할하는 정렬 (하나의 큰 문제를 두 개의 작은 문제로 분할)
- 비교하면서 찾는 비교 정렬이며, 추가공간을 필요로 하지않기때문에 제자리 정렬(in-place sort)이다.
- 특징 : 이미 정렬되어있는 경우 시간복잡도가 늘어남
- 시간복잡도 : 평균 O(N * logN), O(logN), 최악(N^2)
1. 피벗을 하나 선택한다.
2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다. (파티셔닝)
3. 양 방향에서 찾은 두 원소를 교환한다.
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.
5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)
6. 인접한 부분리스트끼리 합친다. (Conqure : 정복)
public class sortAl {
/** * 알고리즘 *
* 1. 만약 right > left 이면 * 1-1 N 크기의 a 배열을 분할하여 축값의 위치를 mid로 넘긴다. *
* 1-2 퀵 정렬 알고리즘(array, left, mid) *
* 1-3 퀵 정렬 알고리즘(array, mid, right), */
int value[] = {5, 3, 8, 2, 10, 9, 4, 1, 7, 6, 6, 12, 8, 11, 9};
public void sort() {
printValue();
quicksort(value, 0, value.length - 1);
printValue();
}
private void quicksort(int array[], int left, int right) {
if (left >= right) {
return;
}
int tempLeft = left - 1;
int tempRight = right + 1;
int pivotValue = array[(left + right)/2]; // 중위값으로 선택
while (true) {
while (array[++tempLeft] < pivotValue);
while (pivotValue < array[--tempRight]);
if (tempLeft > tempRight) break;
swap(array, tempLeft, tempRight);
}
quicksort(array, left, tempRight);
quicksort(array, tempLeft, right);
}
private void swap(int array[], int index1, int index2) {
int tempValue = array[index1];
array[index1] = array[index2];
array[index2] = tempValue;
}
private void printValue() {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
1) 왼쪽 피벗 선택 방식
public class QuickSort {
public static void sort(int[] a) {
l_pivot_sort(a, 0, a.length - 1);
}
/**
* 왼쪽 피벗 선택 방식
* @param a 정렬할 배열
* @param lo 현재 부분배열의 왼쪽
* @param hi 현재 부분배열의 오른쪽
*/
private static void l_pivot_sort(int[] a, int lo, int hi) {
/*
* lo가 hi보다 크거나 같다면 정렬 할 원소가
* 1개 이하이므로 정렬하지 않고 return한다.
*/
if(lo >= hi) {
return;
}
/*
* 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
* 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
*
* 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
* 분할 정복을 해준다.
*
* [과정]
*
* Partitioning:
*
* a[left] left part right part
* +---------------------------------------------------------+
* | pivot | element <= pivot | element > pivot |
* +---------------------------------------------------------+
*
*
* result After Partitioning:
*
* left part a[lo] right part
* +---------------------------------------------------------+
* | element <= pivot | pivot | element > pivot |
* +---------------------------------------------------------+
*
*
* result : pivot = lo
*
*
* Recursion:
*
* l_pivot_sort(a, lo, pivot - 1) l_pivot_sort(a, pivot + 1, hi)
*
* left part right part
* +-----------------------+ +-----------------------+
* | element <= pivot | pivot | element > pivot |
* +-----------------------+ +-----------------------+
* lo pivot - 1 pivot + 1 hi
*
*/
int pivot = partition(a, lo, hi);
l_pivot_sort(a, lo, pivot - 1);
l_pivot_sort(a, pivot + 1, hi);
}
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(lo)를 반환
*/
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[left]; // 부분리스트의 왼쪽 요소를 피벗으로 설정
// lo가 hi보다 작을 때 까지만 반복한다.
while(lo < hi) {
/*
* hi가 lo보다 크면서, hi의 요소가 pivot보다 작거나 같은 원소를
* 찾을 떄 까지 hi를 감소시킨다.
*/
while(a[hi] > pivot && lo < hi) {
hi--;
}
/*
* hi가 lo보다 크면서, lo의 요소가 pivot보다 큰 원소를
* 찾을 떄 까지 lo를 증가시킨다.
*/
while(a[lo] <= pivot && lo < hi) {
lo++;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
/*
* 마지막으로 맨 처음 pivot으로 설정했던 위치(a[left])의 원소와
* lo가 가리키는 원소를 바꾼다.
*/
swap(a, left, lo);
// 두 요소가 교환되었다면 피벗이었던 요소는 lo에 위치하므로 lo를 반환한다.
return lo;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
2) 오른쪽 피벗 선택 방식
public class QuickSort {
public static void sort(int[] a) {
r_pivot_sort(a, 0, a.length - 1);
}
/**
* 오른쪽 피벗 선택 방식
* @param a 정렬할 배열
* @param lo 현재 부분배열의 왼쪽
* @param hi 현재 부분배열의 오른쪽
*/
private static void r_pivot_sort(int[] a, int lo, int hi) {
/*
* lo가 hi보다 크거나 같다면 정렬 할 원소가
* 1개 이하이므로 정렬하지 않고 return한다.
*/
if(lo >= hi) {
return;
}
/*
* 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
* 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
*
* 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
* 분할 정복을 해준다.
*
* [과정]
*
* Partitioning:
*
* left part right part a[right]
* +---------------------------------------------------------+
* | element < pivot | element >= pivot | pivot |
* +---------------------------------------------------------+
*
*
* result After Partitioning:
*
* left part a[hi] right part
* +---------------------------------------------------------+
* | element < pivot | pivot | element >= pivot |
* +---------------------------------------------------------+
*
*
* result : pivot = hi
*
*
* Recursion:
*
* r_pivot_sort(a, lo, pivot - 1) r_pivot_sort(a, pivot + 1, hi)
*
* left part right part
* +-----------------------+ +-----------------------+
* | element <= pivot | pivot | element > pivot |
* +-----------------------+ +-----------------------+
* lo pivot - 1 pivot + 1 hi
*
*/
int pivot = partition(a, lo, hi);
r_pivot_sort(a, lo, pivot - 1);
r_pivot_sort(a, pivot + 1, hi);
}
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(lo)를 반환
*/
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[right]; // 부분리스트의 오른쪽 요소를 피벗으로 설정
// lo가 hi보다 작을 때 까지만 반복한다.
while(lo < hi) {
/*
* hi가 lo보다 크면서, lo의 요소가 pivot보다 큰 원소를
* 찾을 떄 까지 lo를 증가시킨다.
*/
while(a[lo] < pivot && lo < hi) {
lo++;
}
/*
* hi가 lo보다 크면서, hi의 요소가 pivot보다 작거나 같은 원소를
* 찾을 떄 까지 hi를 감소시킨다.
*/
while(a[hi] >= pivot && lo < hi) {
hi--;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
/*
* 마지막으로 맨 처음 pivot으로 설정했던 위치(a[right])의 원소와
* hi가 가리키는 원소를 바꾼다.
*/
swap(a, right, hi);
// 두 요소가 교환되었다면 피벗이었던 요소는 hi에 위치하므로 hi를 반환한다.
return hi;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
3) 중간 피벗 선택 방식
public class QuickSort {
public static void sort(int[] a) {
m_pivot_sort(a, 0, a.length - 1);
}
/**
* 중간 피벗 선택 방식
* @param a 정렬할 배열
* @param lo 현재 부분배열의 왼쪽
* @param hi 현재 부분배열의 오른쪽
*/
private static void m_pivot_sort(int[] a, int lo, int hi) {
/*
* lo가 hi보다 크거나 같다면 정렬 할 원소가
* 1개 이하이므로 정렬하지 않고 return한다.
*/
if(lo >= hi) {
return;
}
/*
* 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
* 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
*
* 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
* 분할 정복을 해준다.
*
* [과정]
*
* Partitioning:
*
* left part a[(right + left)/2] right part
* +---------------------------------------------------------+
* | element < pivot | pivot | element >= pivot |
* +---------------------------------------------------------+
*
*
* result After Partitioning:
*
* left part a[hi] right part
* +---------------------------------------------------------+
* | element < pivot | pivot | element >= pivot |
* +---------------------------------------------------------+
*
*
* result : pivot = hi
*
*
* Recursion:
*
* m_pivot_sort(a, lo, pivot) m_pivot_sort(a, pivot + 1, hi)
*
* left part right part
* +-----------------------+ +-----------------------+
* | element <= pivot | | element > pivot |
* +-----------------------+ +-----------------------+
* lo pivot pivot + 1 hi
*
*/
int pivot = partition(a, lo, hi);
m_pivot_sort(a, lo, pivot);
m_pivot_sort(a, pivot + 1, hi);
}
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(hi)를 반환
*/
private static int partition(int[] a, int left, int right) {
// lo와 hi는 각각 배열의 끝에서 1 벗어난 위치부터 시작한다.
int lo = left - 1;
int hi = right + 1;
int pivot = a[(left + right) / 2]; // 부분리스트의 중간 요소를 피벗으로 설정
while(true) {
/*
* 1 증가시키고 난 뒤의 lo 위치의 요소가 pivot보다 큰 요소를
* 찾을 떄 까지 반복한다.
*/
do {
lo++;
} while(a[lo] < pivot);
/*
* 1 감소시키고 난 뒤의 hi 위치가 lo보다 크거나 같은 위치이면서
* hi위치의 요소가 pivot보다 작은 요소를 찾을 떄 까지 반복한다.
*/
do {
hi--;
} while(a[hi] > pivot && lo <= hi);
/*
* 만약 hi가 lo보다 크지 않다면(엇갈린다면) swap하지 않고 hi를 리턴한다.
*/
if(lo >= hi) {
return hi;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
병합 정렬(분할정복 알고리즘)
- 항상 반으로 나누어 각자 계산하고 합치는 순간에 정렬
- 특징 : 정확히 반절씩 나눈다는 점에서 최악의 경우에도 시간복잡도 동일함
- 정렬에 사용되는 배열은 반드시 '전역 변수'로 선언해야 함(함수안에서 선언하면 자원의 낭비가 커짐)
- 기존의 데이터를 담을 추가적인 배열이 필요하기때문에 비효율적이라는 의견도 있음
- 시간복잡도 : 평균 O(N * logN), 최악(N * logN)
1. 배열을 최소단위까지 분할한다.
2. 병합시, 부분 배열의 앞에서부터 순차적으로 비교 후 임시 배열에 삽입한다.
3. 임시 배열을 원본 배열에 복사한다.
public class sortAl {
/** * 알고리즘 *
* 1. l < r 인경우 *
* 1) mid = (l + r) / 2 *
* 2) mergeSort(l, mid) *
* 3) mergeSort(mid + 1, r) *
* 4) merge(l, mid, r) */
int value[] = {5, 3, 8, 2, 10, 9, 4, 1, 7, 6, 6, 12, 8, 11, 9};
public void sort() {
int newValue[] = mergeSort(value, 1);
// mergeSort2(value, 0, value.length - 1);
printValue(newValue);
}
public int[] mergeSort(int inputArray[], int n) {
if (n >= inputArray.length) {
return inputArray;
}
int firstIndex = 0;
int secondIndex = firstIndex + n;
int temp[] = new int[inputArray.length];
int tempIndex = 0;
while (firstIndex < inputArray.length) {
int i = firstIndex;
int j = secondIndex;
while (true) {
boolean isExistFirstIndex = i < inputArray.length && i < (firstIndex + n);
boolean isExistSecondIndex = j < inputArray.length && j < (secondIndex + n);
if (isExistFirstIndex && isExistSecondIndex) {
if (inputArray[i] <= inputArray[j]) {
temp[tempIndex++] = inputArray[i++];
} else {
temp[tempIndex++] = inputArray[j++];
}
} else if (isExistFirstIndex) {
temp[tempIndex++] = inputArray[i++];
} else if (isExistSecondIndex) {
temp[tempIndex++] = inputArray[j++];
} else { break; }
}
firstIndex = firstIndex + (n * 2);
secondIndex = firstIndex + n;
}
return mergeSort(temp, n * 2);
}
public void mergeSort2(int inputArray[], int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
mergeSort2(inputArray, l, mid);
mergeSort2(inputArray, mid + 1, r);
merge(inputArray, l, mid, r);
}
}
public void merge(int inputArray[], int l, int mid, int r) {
int tempArray[] = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (inputArray[i] <= inputArray[j]) {
tempArray[k++] = inputArray[i++];
} else {
tempArray[k++] = inputArray[j++];
}
}
for (; i <= mid; ) {
tempArray[k++] = inputArray[i++];
}
for (; j <= r; ) {
tempArray[k++] = inputArray[j++];
} for (int n = 0; n < tempArray.length; n++) {
inputArray[l + n] = tempArray[n];
}
}
private void printValue(int value[]) {
StringBuilder builder = new StringBuilder();
for (int i=0;i<value.length;i++) {
builder.append(value[i]).append(" ");
}
System.out.println(builder.toString());
}
}
(힙 자료구조)
[ 변하지않는 성질 ]
1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 +1
2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 +2
3. 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2
힙 정렬
- 힙(최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조)을 기반으로 한 정렬
- 우선순위 큐 자료구조를 구현하는데 기반을 둠
- 우선순위가 가장 높은 로드가 root노드, 배열로 치면 가장 첫 번째 원소
- 힙 자료구조기반으로 구현된 우선순위 큐 자료구조를 이용하여 정렬
- 반 정렬 상태(부분 정렬을 할때 효과가 좋음)
- 시간복잡도 : O(N*logN)
import java.util.PriorityQueue;
public class test {
public static void main(String[] args) {
int[] arr = {3, 7, 5, 4, 2, 8};
System.out.print(" 정렬 전 original 배열 : ");
for(int val : arr) {
System.out.print(val + " ");
}
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
// 배열을 힙으로 만든다.
for(int i = 0; i < arr.length; i++) {
heap.add(arr[i]);
}
// 힙에서 우선순위가 가장 높은 원소(root노드)를 하나씩 뽑는다.
for(int i = 0; i < arr.length; i++) {
arr[i] = heap.poll();
}
System.out.print("\n 정렬 후 배열 : ");
for(int val : arr) {
System.out.print(val + " ");
}
}
}-> 힙을 만들기 위한 공간을 마련하는 것은 별도의 메모리가 필요하기 때문에 비효율적
| 오름차순으로 구현할 때, 최대 힙 조건을 만족하도록 재구성해야한다. 힙은 항상 부모노드가 자식노드보다 우선순위가 높다. (이때 형제노드 사이에서는 우선순위가 고려되지 않음) 힙 구조는 반 정렬 상태이지 완전정렬상태가 아니기 때문이다. 최소힙으로 정렬하여 쓰게되면 형제간의 우선순위는 고려되지않기때문에 제대로 정렬이 이루어지지 않는다. |
과정 1) 최대 힙 만들기
(추가적인 메모리 공간을 생성하지 않고 원본 배여 안에서 정렬하기 위함)
초기 상태의 배열 자체를 별도의 배열 선언 없이 최대 힙으로 만들어야한다.
가장 작은 서브트리부터 최대 힙을 만족하도록 순차적으로 진행한다.
위와 같이 힙을 만드는 과정을 heapify라고 하는데, 부모노드로부터 자식노드로 진행되기 때문에 sift-down과정이라고도 한다.
과정 2) 정렬하기
항상 root노드는 최댓값을 가지고 있다. 이를 이용하여 최댓값을 하나씩 삭제하면서 배열의 맨 뒤부터 채워나간다.
root원소를 배열의 맨 뒤로 보냄 -> 뒤에 채운 원소를 제외한 나머지 원소들을 다시 최대힙을 만족하도록 재구성
// Top-Down 방식
public class HeapSort {
public static void sort(int[] a) {
sort(a, a.length);
}
private static void sort(int[] a, int size) {
/*
* 부모노드와 heaify과정에서 음수가 발생하면 잘못 된 참조가 발생하기 때문에
* 원소가 1개이거나 0개일 경우는 정렬 할 필요가 없으므로 바로 함수를 종료한다.
*/
if(size < 2) {
return;
}
/*
* left child node = index * 2 + 1
* right child node = index * 2 + 2
* parent node = (index - 1) / 2
*/
// 가장 마지막 요소의 부모 인덱스
int parentIdx = getParent(size - 1);
// max heap
for(int i = parentIdx; i >= 0; i--) {
heapify(a, i, size - 1);
}
for(int i = size - 1; i > 0; i--) {
/*
* root인 0번째 인덱스와 i번째 인덱스의 값을 교환해준 뒤
* 0 ~ (i-1) 까지의 부분트리에 대해 max heap을 만족하도록
* 재구성한다.
*/
swap(a, 0, i);
heapify(a, 0, i - 1);
}
}
// 부모 인덱스를 얻는 함수
private static int getParent(int child) {
return (child - 1) / 2;
}
// 두 인덱스의 원소를 교환하는 함수
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// 힙을 재구성 하는 함수
private static void heapify(int[] a, int parentIdx, int lastIdx) {
/*
* 현재 트리에서 부모 노드의 자식노드 인덱스를 각각 구해준다.
* 현재 부모 인덱스를 가장 큰 값을 갖고있다고 가정한다.
*/
int leftChildIdx = 2 * parentIdx + 1;
int rightChildIdx = 2 * parentIdx + 2;
int largestIdx = parentIdx;
/*
* left child node와 비교
*
* 자식노드 인덱스가 트리의 크기를 넘어가지 않으면서
* 현재 가장 큰 인덱스보다 왼쪽 자식노드의 값이 더 클경우
* 가장 큰 인덱스를 가리키는 largestIdx를 왼쪽 자식노드인덱스로 바꿔준다.
*
*/
if(leftChildIdx <= lastIdx && a[largestIdx] < a[leftChildIdx]) {
largestIdx = leftChildIdx;
}
/*
* left right node와 비교
*
* 자식노드 인덱스가 트리의 크기를 넘어가지 않으면서
* 현재 가장 큰 인덱스보다 오른쪽쪽 자식노드의 값이 더 클경우
* 가장 큰 인덱스를 가리키는 largestIdx를 오른쪽 자식노드인덱스로 바꿔준다.
*
*/
if(rightChildIdx <= lastIdx && a[largestIdx] < a[rightChildIdx]) {
largestIdx = rightChildIdx;
}
/*
* largestIdx 와 부모노드가 같지 않다는 것은
* 위 자식노드 비교 과정에서 현재 부모노드보다 큰 노드가 존재한다는 뜻이다.
* 그럴 경우 해당 자식 노드와 부모노드를 교환해주고,
* 교환 된 자식노드를 부모노드로 삼은 서브트리를 검사하도록 재귀 호출 한다.
*/
if(parentIdx != largestIdx) {
swap(a, largestIdx, parentIdx);
heapify(a, largestIdx, lastIdx);
}
}
}위와 같은 방식은 Top-Down방식인데 heapify(a, largestIdx, lastIdx) 부분이 재귀호출된다.
만약 재귀 호출을 할 경우 정렬해야 할 원소가 많아지고, 매 재귀마다 부모노드와 자식노드가 교환된다면 최악의 경우에는 트리의 높이만큼 재귀호출이 발생한다는 뜻이며 StackOverFlow가 발생할 수 있다.
힙정렬을 재귀함수 호출이 아닌 반복문방식(Bottom-Up)으로 구현한 소스는 다음과 같다.
// Bottom-Up 방식
public class HeapSort {
public static void sort(int[] a) {
sort(a, a.length);
}
private static void sort(int[] a, int size) {
/*
* 부모노드와 heaify과정에서 음수가 발생하면 잘못 된 참조가 발생하기 때문에
* 원소가 1개이거나 0개일 경우는 정렬 할 필요가 없으므로 바로 함수를 종료한다.
*/
if(size < 2) {
return;
}
/*
* left child node = index * 2 + 1
* right child node = index * 2 + 2
* parent node = (index - 1) / 2
*/
// 가장 마지막 요소의 부모 인덱스
int parentIdx = getParent(size - 1);
// max heap
for(int i = parentIdx; i >= 0; i--) {
heapify(a, i, size - 1);
}
for(int i = size - 1; i > 0; i--) {
/*
* root인 0번째 인덱스와 i번째 인덱스의 값을 교환해준 뒤
* 0 ~ (i-1) 까지의 부분트리에 대해 max heap을 만족하도록
* 재구성한다.
*/
swap(a, 0, i);
heapify(a, 0, i - 1);
}
}
// 부모 인덱스를 얻는 함수
private static int getParent(int child) {
return (child - 1) / 2;
}
// 두 인덱스의 원소를 교환하는 함수
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static void heapify(int[] a, int parentIdx, int lastIdx) {
int leftChildIdx;
int rightChildIdx;
int largestIdx;
/*
* 현재 부모 인덱스의 자식 노드 인덱스가
* 마지막 인덱스를 넘지 않을 때 까지 반복한다.
*
* 이 때 왼쪽 자식 노드를 기준으로 해야 한다.
* 오른쪽 자식 노드를 기준으로 범위를 검사하게 되면
* 마지막 부모 인덱스가 왼쪽 자식만 갖고 있을 경우
* 왼쪽 자식노드와는 비교 및 교환을 할 수 없기 때문이다.
*/
while((parentIdx * 2) + 1 <= lastIdx) {
leftChildIdx = (parentIdx * 2) + 1;
rightChildIdx = (parentIdx * 2) + 2;
largestIdx = parentIdx;
/*
* left child node와 비교
* (범위는 while문에서 검사했으므로 별도 검사 필요 없음)
*/
if (a[leftChildIdx] > a[largestIdx]) {
largestIdx = leftChildIdx;
}
/*
* right child node와 비교
* right child node는 범위를 검사해주어야한다.
*/
if (rightChildIdx <= lastIdx && a[rightChildIdx] > a[largestIdx]) {
largestIdx = rightChildIdx;
}
/*
* 교환이 발생했을 경우 두 원소를 교체 한 후
* 교환이 된 자식노드를 부모 노드가 되도록 교체한다.
*/
if (largestIdx != parentIdx) {
swap(a, parentIdx, largestIdx);
parentIdx = largestIdx;
}
else {
return;
}
}
}
}출처 및 참고
https://m.blog.naver.com/ndb796/221228342808
https://st-lab.tistory.com/category/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
반응형
'Programming > Algorithm&DataStructure' 카테고리의 다른 글
| [JAVA 자료구조] ArrayList (0) | 2021.08.04 |
|---|---|
| [JAVA 자료구조] List Interface (리스트 인터페이스) (0) | 2021.08.04 |
| [Algorithm] 시간 복잡도 & Big-O표기법 (0) | 2021.07.30 |
| [Algorithm] 공간 복잡도 (0) | 2021.07.30 |
| [Algorithm] 버블 정렬(Bubble Sort) (0) | 2020.08.10 |
