[알고리즘]정렬

package Algorithm;

import java.util.Arrays;

import DataStructure.Heap;

// 정렬의 알고리즘을 공부한다.
// 정렬은 알고리즘의 종류별로 함수를 만든다.
// 정렬을 할 데이터는 int 배열이며 리스트를 사용하는 경우도 있다.

public class Sort {

public static void main(String[] args) {
Sort s = new Sort();// 함수를 사용하기 위한 객체 생성
int[] a = { 5, 3,4,3,23,5,6,7,12,3,4,5,32,23,5,3,6,8,0,56,1,2}; // 정렬할 데이터

int[] b = Arrays.copyOf(a, a.length);

// 버블 정렬
System.out.print("버블 정렬 : [");
for(int i : s.bubbleSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");

// 카운트 정렬
b = Arrays.copyOf(a, a.length);
System.out.print("카운트 정렬 : [");
for(int i : s.countSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");

// 삽입 정렬
b = Arrays.copyOf(a, a.length);
System.out.print("삽입 정렬 :\t[");
for(int i : s.insertSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");

// 선택 정렬
b = Arrays.copyOf(a, a.length);
System.out.print("선택 정렬 : [");
for(int i : s.selectSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");

// 퀵 정렬
b = Arrays.copyOf(a, a.length);
System.out.print("퀵 정렬 : [");
for(int i : s.quickSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");

// 병합정렬
b = Arrays.copyOf(a, a.length);
System.out.print("병합 정렬 : [");
for (int i : s.mergeSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");

// 셸 정렬
b = Arrays.copyOf(a, a.length);
System.out.print("셸 정렬 : [");
for (int i : s.shellSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");

// 힙 정렬
b = Arrays.copyOf(a, a.length);
System.out.print("힙 정렬 : [");
for (int i : s.heapSort(b)) {
System.out.print(i + ", ");
}
System.out.println("]");
}

/* 버블정렬(Bubble Sort) */
public int[] bubbleSort(int[] data) {
int temp = 0; // 임시로 저장할 변수
for (int i = data.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (data[j] > data[j + 1]) { // 오름차순으로 정렬한다.
// j번째 데이터와 j+1번째 데이터를 서로 바꾼다.
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
} // end for 2
} // end for 1

return data;
}// end method bubbleSort

// 버블정렬은 구현이 매우 간단하다.
// 순서에 맞지 않는 요소를 인접한 요소와 교환한다.
// 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열의 모든 다른 요소들과 교환되어야 한다.
// 거의 사용되지 않는 정렬방법

/* 카운트 정렬 */
public int[] countSort(int[] a) {
// 배열의 값은 정수만 받는 것으로 한다.
int[] count = null; // 각 숫자의 개수를 저장할 배열
int[] result = new int[a.length]; // 정렬된 값을 저장할 배멸
int max = 0; // a의 최대값, 만약 음의 정수만 있으면 최댓값은 0이 된다.
int min = 0; // a의 최솟값, 만약 양의 정수만 있으면 최솟값은 0이 된다.

for (int i : a) { // 최대값, 최소값을 찾는다.
if (max < i) {
max = i;
}

if (min > i) {
min = i;
}
}

count = new int[max - min + 1]; // 범위만큼 배열을 만든다.
// 인덱스는 값 +min을 사용한다.(0 ~ min+max)

for (int i : a) { // 각 숫자의 개수를 구한다.
count[i + min]++;
}

for (int i = 0; i < count.length - 1; i++) {// count값을 누적한다. 나중에 인덱스가 된다.
count[i + 1] = count[i] + count[i + 1];
}

int index = 0;
for (int i : a) { // count값을 인덱스로 사용하여 정렬한다.
index = count[i + min] - 1; // 인덱스를 구한다.
result[index] = i; // 인덱스에 저장한다.
count[i + min]--; // 인덱스를 하나 줄인다.
}

return result;
}// end method countSort

/* 삽입 정렬 */
public int[] insertSort(int[] a) {
int[] result = new int[a.length]; // 정렬된 배열 -> 반환할 배열
result[0] = a[0]; // 초기값을 넣어준다.

for (int i = 1; i < a.length; i++) {
for (int j = i - 1; j >= 0; j--) { // 값을 배열에 넣어주면서 정렬
if (result[j] > a[i]) {
result[j + 1] = result[j]; // 값을 뒤로 보낸다.
result[j] = a[i]; // 값을 저장한다.
} else {
result[j + 1] = a[i]; // 삽입할 값이 작지않으면 저장
break;
}

} // end for2
} // end for1
return result;
}// end method insertSort

// 삽입정렬은 안정한 정렬방법이다.
// 대부분의 데이터가 미리 정렬되어 있으면 매우 효율적이다.
// 데이터 수가 많으면 적합하지 않다.

/* 선택 정렬 */
public int[] selectSort(int[] a) {
int min; // 최소값의 위치를 저장
int temp = 0; // 값의 위치를 바꾸기 위한 임시변수

for (int i = 0; i < a.length - 1; i++) {
min = a.length - 1; // 최솟값으로 배열의 마지막 값을 사용
for (int j = i; j < a.length; j++) {// 작은값을 앞에 보내고 나머지값만 비교
if (a[min] > a[j]) {
min = j;
}
} // end for2

// 최소값을 위치에 넣는다.
temp = a[i];
a[i] = a[min];
a[min] = temp;

} // end for1

return a;
}// end method selectSort

// 선택정렬은 자료의 이동 횟수가 미리 결정된다.
// 선택정렬은 안정성을 만족하지 않는다. - 같은 데이터가 있으면 상대적 위치가 변경될 수 있다.

/* 퀵 정렬 */
public int[] quickSort(int[] data) { // 기준값으로 좌우로 나누는 과정을 반복해 정렬
if (data.length == 1 || data.length == 0) {
return data;
} else if (data.length == 2) {
if (data[0] > data[1]) {
int temp = data[0];
data[1] = data[0];
data[0] = temp;
}
return data;
}

int low = 1; // 값을 비교할 위치1 -> 작은값
int high = data.length - 1; // 값을 비교할 위치2 -> 큰값
int temp = 0; // 임시 값

while (true) {
if (low > high) {
break;
} else if (data[low] < data[0]) {
low++;
continue;
} else if (data[high] > data[0]) {
high--;
continue;
} else {
/* 기준보다 낮은 값과 높은값의 위치를 바꾼다. */
temp = data[high];
data[high] = data[low];
data[low] = temp;
low++;
high--;
} // end if-else1
} // end while

/* high 위치와 기준값을 바꾼다. */
temp = data[high];
data[high] = data[0];
data[0] = temp;

/* 기준값으로 좌우 배열로 나누어 다시 함수를 실행한다 */
int[] left = new int[high]; // 왼쪽의 배열
int[] right = new int[data.length - high - 1]; // 오른쪽의 배열

for (int i = 0; i < high; i++) { // 배열을 복사
left[i] = data[i];
}
left = quickSort(left); // 정렬
for (int i = 0; i < high; i++) { // 배열을 복사
data[i] = left[i];
}

for (int i = 1; i < right.length + 1; i++) {
right[i - 1] = data[high + i];
}
right = quickSort(right); // 정렬
for (int i = 1; i < right.length + 1; i++) {
data[high + i] = right[i - 1];
}

return data;
}// end method quickSort

// 배열은 참조변수이므로 받은 배열을 계속 넘겨 새로운 배열을 많이 생성하지 않고 정렬 할 수 있다.
// 그런 방식으로 만들려면 매개변수에 index값을 여러개 넘겨 주어야 한다.
// 퀵정렬은 속도가 빠르다. - 데이터가 정렬이 되어 있으면 버블 정렬과 비슷할 정도로 느리다.

/* 병합 정렬 */
public int[] mergeSort(int[] data) {
if (data.length == 1) {
return data;
}
/* 배열을 두개로 나누어 각자 정렬한 후 결합한다. */
int n = data.length / 2; // 나눌 기준값

/* 분해 부분 */
int[] div1 = new int[n]; // 좌측 배열
for (int i = 0; i < div1.length; i++) {
div1[i] = data[i];
}
div1 = mergeSort(div1); // 정렬된 배열을 저장

int[] div2 = new int[data.length - n]; // 우측 배열
for (int i = 0; i < div2.length; i++) {
div2[i] = data[n + i];
}
div2 = mergeSort(div2); // 정렬된 배열을 저장

/* 결합 부분 */
int[] result = new int[div2.length + div1.length]; // 결과를 저장할 배열
int d1 = 0;
int d2 = 0;
for (int i = 0; i < result.length; i++) {
if (d1 < div1.length && d2 < div2.length) {
if (div1[d1] > div2[d2]) {
result[i] = div2[d2++];
continue;
} else {
result[i] = div1[d1++];
continue;
}
} else if (d2 < div2.length) {
result[i] = div2[d2++];
continue;
} else {
result[i] = div1[d1++];
}
}

return result;
}// end method mergeSort

// 배열은 참조변수이므로 받은 배열을 계속 넘겨 새로운 배열을 많이 생성하지 않고 정렬 할 수 있다.
// 그런 방식으로 만들려면 매개변수에 index값을 여러개 넘겨 주어야 한다.
// 합병정렬은 크기가 큰 데이터를 정렬할 때 리스트를 사용하면, 퀵 정렬을 포함한 어떤 정렬보다 효율적이다.
// 합병정렬은 데이터 분포의 영향을 덜받는다.(정렬시간이 동일)
// 합병정렬은 연결리스트로 구현하면 이동은 무시할 정도로 작아진다.

/* 셀 정렬 */
public int[] shellSort(int[] data) { // 삽입정렬을 보완한 알고리즘이다.
int step = data.length;
while (true) {
/* 부분배열에 저장할 간격 계산 */
step = step / 2;
if (step % 2 == 0) {
step++;
}
/* 부분 배열에 저장 */
int[][] temp = new int[step][data.length]; // 부분배열을 저장할 이차원배열
int row = 0;
int col = 0;
for (int i : data) {
if (row > data.length - 1) { // 행이 부분 배열의 길이를 넘어가면 다음 부분배열에 저장한다.
row = ++col; // 부분 배열이 넘어가면 시작을 1칸 미룬다.
}

// 각 부분 배열에 step간격으로 값을 저장한다.
temp[col][row] = i;
row += step;
}

/* 정렬 */
for (col = 0; col < step; col++) { // 행 단위(부분배열 단위)로 각자 정렬을 한다.
int t = 0; // 정렬하기위한 임시 변수

/* 실제 부분배열로 정렬 */
for (row = col + step; row < data.length; row += step) { // 새로 추가되는 데이터의 위치
t = temp[col][row];
for (int j = row - step; j >= 0; j -= step) {
if (temp[col][j] > t) {
temp[col][j + step] = temp[col][j];
temp[col][j] = t;
} else {
temp[col][j + step] = t;
break;
}
} // end for3
} // end for2
} // end for1

/* 부분 배열을 통합 */
for (int i = 0; i < data.length; i++) {
col = i % step; // 몫, 열의 값이된다.
data[i] = temp[col][i];
}

if (step == 1) { // step이 1이면 종료
break;
}
}

return data;
}// end method shellSort

// 교환되는 요소들이 최종 위치에 있을 가능성이 높다
// 부분 배열에서 어느정도 정렬된 상태여서 부분배열의 개수가 1이면 삽입정렬보다 더욱 빠르게 수행된다.
// 알고리즘이 간단하여 쉽게 구형할 수 있다.

/* 힙 정렬 */
/*
 * 힙(heap) 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 최댓값, 최솟값을 쉽게 구할 수 있는 자료구조 일종의 반정렬
 * 상태(느슨한 정렬 상태)를 유지한다. - 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도 힙은 중복된 값을 허용한다. 표준적인
 * 자료구조는 배열이다. - 부모노드의 index*2(왼쪽)와 index*2+1(오른쪽)은 자식 노드(index는 1에서 부터 시작 - 구현이
 * 쉽다.)
 */

public int[] heapSort(int[] data) {// 오름차순으로 정렬하기 위해 최소힙을 구현
// 힙정렬을 하기위해 먼저 힙을 구현해야한다.
Heap heap = new Heap(data.length); // 데이터의 크기만큼 힙을 생성

for (int i : data) {
heap.add(i); // 데이터들을 힙에 저장
} // end for1

for (int i = 0; i < data.length; i++) {
data[i] = heap.get(); // 힙의 데이터를 하나씩 저장
}

return data;
}// end method heapSort
}// end class Sort