[Java] Sort 함수
정렬 함수 테스트
정렬 방식
- Bubble Sort. O(N^2)
- Selection Sort. O(N^2)
- Insertion Sort. O(N^2)
- Quick Sort. avg O(N*logN), max O(N^2) - 이미정렬된 경우
- Merge Sort. O(N*logN) 보장, 단점 정렬시 메모리 필요함.
- Heap Sort. N/2*logN (N이 클경우 logN은 값은 작은 값으로 결과적으로) > O(N)
- Counting Sort. O(N) 특정 범위 조건
Bubble Sort.
성능 O(N^2)
package sort;
public class BubbleSort {
public static void main(String[] args) {
// 버블O(N^2) < 선택O(N^2) < 삽입O(N^2)
// 10 + 9 + .... + 1 = 10*(10+1)/2 = 55 (등차 수열)
// 버블 정렬의 시간 복잡도 O(N*N) = O(N^2)
// 선택 정렬과 시간 복잡도는 같으나, 매번 비교와 자리 바꿈으로 인해서 버블 정렬이 정렬중 제일 성능이 느림.
System.out.println("버블 정렬 : 바로 옆값과 비교하여 작은것을 앞으로, 실행시 마다 젤 큰값이 제일 뒤로 보내짐");
int[] num = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
int len = num.length;
System.out.println("Origin-----------------------------------------");
for(int d=0 ; d<len ; d++) {
System.out.format("%4d",num[d]);
}
System.out.println("");
System.out.println("Sort-------------------------------------------");
for(int i=0 ; i<len ; i++) {
for(int j =0 ; j<(len-1-i) ; j++) {
if( j < len-1 && num[j] > num[j+1] ) {
int temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
//System.out.format("%4d",num[j]);
}//end for
//System.out.println("");
//출력용
for(int d=0 ; d<len ; d++) {
System.out.format("%4d",num[d]);
}
System.out.println("");
}//end for
}
}
// 출력 결과
Origin-----------------------------------------
1 10 5 8 7 6 4 3 2 9
Sort-------------------------------------------
1 5 8 7 6 4 3 2 9 10
1 5 7 6 4 3 2 8 9 10
1 5 6 4 3 2 7 8 9 10
1 5 4 3 2 6 7 8 9 10
1 4 3 2 5 6 7 8 9 10
1 3 2 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Selection Sort.
성능 O(N^2)
package sort;
public class SelectionSort {
public static void main(String[] args) {
// 10 + 9 + .... + 1 = 10*(10+1)/2 = 55 (등차 수열)
// 선택 정렬의 시간 복잡도 O(N*N) = O(N^2)
System.out.println("선택 정렬 : 가장 작은 수를 제일 앞으로 이동");
int[] num = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
int len = num.length;
System.out.println("Origin-----------------------------------------");
for(int d=0 ; d<len ; d++) {
System.out.format("%4d",num[d]);
}
System.out.println("");
System.out.println("Sort-------------------------------------------");
for(int i=0 ; i<len ; i++) {
//System.out.println("[i]"+num[i]);
int midx = i; //Min Value Index
for(int j =i ; j<len ; j++) {
if( num[midx] > num[j] ) {
midx = j;
}
}
//최소값 교체
if( midx != i ) {
int temp = num[i];
num[i] = num[midx];
num[midx] = temp;
}
//출력용
for(int d=0 ; d<len ; d++) {
System.out.format("%4d",num[d]);
}
System.out.println("");
}//end for
}
}
// 출력 결과
선택 정렬 : 가장 작은 수를 제일 앞으로 이동
Origin-----------------------------------------
1 10 5 8 7 6 4 3 2 9
Sort-------------------------------------------
1 10 5 8 7 6 4 3 2 9
1 2 5 8 7 6 4 3 10 9
1 2 3 8 7 6 4 5 10 9
1 2 3 4 7 6 8 5 10 9
1 2 3 4 5 6 8 7 10 9
1 2 3 4 5 6 8 7 10 9
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Insertion Sort.
성능 O(N^2)
package sort;
public class InsertionSort {
public static void main(String[] args) {
// 삽입 정렬의 시간 복잡도 O(N*N) = O(N^2) 이나, 선택과 버블 정렬 대비, 중간 연산이 멈출수 있어서 시간을 줄일수 있음
System.out.println("삽입 정렬 : 바로 옆값과 비교하여 작은것을 앞으로, 실행시 마다 젤 큰값이 제일 뒤로 보내짐");
int[] num = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
int len = num.length;
System.out.println("Origin-----------------------------------------");
for(int d=0 ; d<len ; d++) {
System.out.format("%4d",num[d]);
}
System.out.println("");
System.out.println("Sort-------------------------------------------");
for(int i=0 ; i<len ; i++) {
for(int j = i ; j >= 0 ; j--) {
// 교체
if(j > 0 && num[j-1] > num[j] ){
int temp = num[j];
num[j] = num[j-1];
num[j-1] = temp;
}else {
continue;
}
}
//출력용
for(int d=0 ; d<len ; d++) {
System.out.format("%4d",num[d]);
}
System.out.println("");
}
}
}
// 출력 결과
Origin-----------------------------------------
1 10 5 8 7 6 4 3 2 9
Sort-------------------------------------------
1 10 5 8 7 6 4 3 2 9
1 10 5 8 7 6 4 3 2 9
1 5 10 8 7 6 4 3 2 9
1 5 8 10 7 6 4 3 2 9
1 5 7 8 10 6 4 3 2 9
1 5 6 7 8 10 4 3 2 9
1 4 5 6 7 8 10 3 2 9
1 3 4 5 6 7 8 10 2 9
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 9 10
Quick Sort.
avg O(N*logN), max O(N^2) - 이미정렬된 경우
package sort;
public class QuickSort {
public static void print(int[] num) {
//출력용
for(int d=0 ; d<num.length ; d++) {
System.out.format("%4d ",num[d]);
}
System.out.println("");
}
public static void print(int[] num,int l,int r) {
//출력용
for(int i=0 ; i < num.length ; i++) {
String s ="";
String e ="";
if( i >= l && i <= r-1 ){ //대상 범위
s="(";
e=")";
}
if( i == r ){ //pivot
s="[";
e="]";
}
System.out.format("%1s%2s%1s ",s,String.valueOf(num[i]),e);
}
System.out.println("");
}
public static void quickSort(int[] num, int l, int r) {
if( l < r) {
print( num, l, r);
int p = partition(num, l, r);
quickSort(num, l, p - 1); //p 왼쪽 구간 재정렬
quickSort(num, p + 1, r); //p 오른쪽 구간 재정렬
}
}
//partition 함수 호출시 pivot의 위치를 확정하는 역할을 함
public static int partition(int[] num, int l, int r) {
int pV = num[r]; //제일 마지막 값을 pivot으로
int i = l - 1 ; // pivot 보다 작은 수의 갯수 (-1)부터 시작
for(int j = l ; j <= r-1 ; j++) {//처음부터 pivot까지 순회
if(num[j] <= pV) { // <= 오름 차순
//if(num[j] > pV) { // <= 내림 차순
i++;
swap(num, i, j);
}
}//end
swap(num, (i+1), r );//pivot보다 작은 수의 다음에 pivot으로 위치시킴
return (i+1);//pivot에 위치를 반환함.
}
public static void swap(int[] num, int a, int b) {
int temp = num[a];
num[a] = num[b];
num[b] = temp;
}
public static void main(String[] args) {
// 퀵 정렬의 시간 복잡도 평균 O(N*logN) 이지만, 피봇값 선택에 따라서 최악의 경우 O(N^2) 까지 출력됨.
// 퀵 정렬은 분할 알고리즘(편향된 분할 가능, 이미 정렬된 배열에서는 O(N^2) 발생 가능)
// avg O(N*logN), max O(N^2)
int[] num = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
//int[] num = {2,1,3,4,5,7};
quickSort(num, 0, num.length - 1);
System.out.println("=================================================");
print(num);
}
}
// 출력 결과
( 1) (10) ( 5) ( 8) ( 7) ( 6) ( 4) ( 3) ( 2) [ 9]
( 1) ( 5) ( 8) ( 7) ( 6) ( 4) ( 3) [ 2] 9 10
1 2 ( 8) ( 7) ( 6) ( 4) ( 3) [ 5] 9 10
1 2 ( 4) [ 3] 5 8 7 6 9 10
1 2 3 4 5 ( 8) ( 7) [ 6] 9 10
1 2 3 4 5 6 ( 7) [ 8] 9 10
=================================================
1 2 3 4 5 6 7 8 9 10
Merge Sort.
O(N*logN) 보장, 단점 정렬시 메모리 필요함.
package sort;
public class MergeSort {
static int[] new_num;
public static void initTemp(int len) {
new_num = new int[len];
}
public static void print(int[] num) {
//출력용
for(int d=0 ; d<num.length ; d++) {
System.out.format("%4d ",num[d]);
}
System.out.println("");
}
public static void print(int[] num,int l,int m,int r) {
//출력용
System.out.format(" %d - %d - %d \t", l, m, r);
for(int i=0 ; i < num.length ; i++) {
String s ="";
String e ="";
if( i == l ){ //대상 범위 S
s="(";
e="";
}else if( i == r ){ //대상 범위 EW
s="";
e=")";
}else if( i == m ){ //중간값
s="[";
e="]";
}
System.out.format("%1s%2s%1s ",s,String.valueOf(num[i]),e);
}
System.out.println("");
}
public static void mergeSort(int[] num, int l, int r) {
if( l < r ) { // 1개 이상에서
int m = (l + r)/2; // 중앙점 m을 발견
//int m = l + (r - 1)/2; // 중앙점 m을 발견 (위 식과 같으나 overflow 방지)
//System.out.format(" %d - %d - %d \n", l, m, r);
print( num,l, m ,r);
if(l==8 && m==8 && r==9) {
System.out.format("");
}
mergeSort( num, l, m); // 오른쪽 파트 정렬
mergeSort( num, m+1, r); //왼쪽 파트 정렬
merge( num, l, m, r);
}
}
public static void merge(int[] num, int l, int m, int r) {
int i = l ; //왼쪽 시작 index지점
int j = m + 1; // 오른쪽 시작 지점
int k = l;
// 적을 값을 저장함.
// l[i,,,,,,]m[j,,,,,,]r
// [k,,,,,,,,,,,,]
while( i <= m && j <= r){
if(num[i] <= num[j]) { //오른쪽, 왼쪽 arrary의 첫번째 값을 비교하여 이동함
new_num[k] = num[i];
i++; //다음 값으로 이동함
}else {
new_num[k] = num[j];
j++;
}
k++; //저장 위치 이동
}// end while
//남은 데이터 삽입
if( i > m ) {
//j쪽 배열만 남은 경우
for(int t = j ; t <= r ; t++ ) {
new_num[k] = num[t];
k++;
}
}else {
//i쪽 배열만 남은 경우
for(int t = i ; t <= m ; t++ ) {
new_num[k] = num[t];
k++;
}
}
//정렬된 배열을 모두 입력
for(int t = l ; t <= r ; t++ ) {
num[t] = new_num[t];
}
}
public static void main(String[] args) {
// 병합 정렬의 시간 복잡도 O(N*logN) 값 보장,
// 병합 정렬은 분할 알고리즘(중간 범위 분할 알고리즘)
// 반씩 나눠서 합치면서 정리함.
// 병합과 재정렬을 위해서 기존 데이터를 저장할 추가적인 메모리가 필요함.(단점 메모리 비효율, 장점 N*logN 속도 보장)
int[] num = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
//int[] num = {2,1,3,4,5,7};
initTemp(num.length);
mergeSort(num, 0, num.length - 1);
System.out.println("=========================================");
print(num);
}
}
// 출력 결과
0 - 4 - 9 ( 1 10 5 8 [ 7] 6 4 3 2 9)
0 - 2 - 4 ( 1 10 [ 5] 8 7) 6 4 3 2 9
0 - 1 - 2 ( 1 [10] 5) 8 7 6 4 3 2 9
0 - 0 - 1 ( 1 10) 5 8 7 6 4 3 2 9
3 - 3 - 4 1 5 10 ( 8 7) 6 4 3 2 9
5 - 7 - 9 1 5 7 8 10 ( 6 4 [ 3] 2 9)
5 - 6 - 7 1 5 7 8 10 ( 6 [ 4] 3) 2 9
5 - 5 - 6 1 5 7 8 10 ( 6 4) 3 2 9
8 - 8 - 9 1 5 7 8 10 3 4 6 ( 2 9)
=========================================
1 2 3 4 5 6 7 8 9 10
Heap Sort.
N/2*logN (N이 클경우 logN은 값은 작은 값으로 결과적으로) > O(N)
package sort;
public class HeapSort {
// Heap 완전 인트리
// Min Heap 가장 작은 값이 위로 오도록
// Max Heap 가장 큰 값이 위로 오도록
public static void swap(int[] num, int a, int b, boolean debug) {
int temp = num[a];
num[a] = num[b];
num[b] = temp;
if(debug) {
//출력용
for(int d=0 ; d<num.length ; d++) {
System.out.format("%4d",num[d]);
}
System.out.println("");
}
}
public static void print(int[] num) {
//출력용
for(int d=0 ; d<num.length ; d++) {
System.out.format("%4d ",num[d]);
}
System.out.println("");
}
public static void main(String[] args) {
// N/2*logN (N이 클경우 logN은 값은 작은 값으로 결과적으로) > O(N)
//int[] num = {1, 2, 3, 4, 5, 6, 7, 8, 9 , 10};
int[] num = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
int len = num.length;
//자료 구조를 힙 구조로 정렬함.
for(int i=1 ; i<len ; i++) { //1부터 시작함.
int c = i; //자식 위치
do {
int root = (c-1)/2; //부모의 위치
//System.out.format("%d(%d) ", i, root);
//1(0) 2(0) 3(1) 4(1) 5(2) 6(2) 7(3) 8(3) 9(4)
if(num[root] < num[c]){ //자식이 부모보다 클 경우 swap
swap(num, root, c, false);
}
c = root; //자식을 부모로 이동하여, 재귀로 내려감
System.out.format("%d ", c);
}while (c != 0 );
System.out.println("");
}
System.out.println("------------------------------");
print(num);
System.out.println("------------------------------");
//크기 축소를 줄이고 힙을 만듬
for(int i=len-1 ; i >= 0 ; i--) {
swap(num, 0, i, true); // 0번째 원소가 가장 큰값으로 가장 큰 값과 가장 작은 값을 교체함.
int root = 0;
int c = 1;
do {
c = 2 * root + 1;
//자식 좌우 중에 더 큰 값을 찾기
if(c < i-1 && num[c] < num[c+1] ) {
c++;
}
//루트보다 자식이 더 크면 교환함.
if( c < i && num[root] < num[c] ) {
swap(num, root, c, true);
}
root = c;
}while( c < i );
}
System.out.println("------------------------------");
print(num);
}
}
// 출력 결과
0
0
1 0
1 0
2 0
2 0
3 1 0
3 1 0
4 1 0
------------------------------
10 9 6 3 8 5 4 1 2 7
------------------------------
7 9 6 3 8 5 4 1 2 10
9 7 6 3 8 5 4 1 2 10
9 8 6 3 7 5 4 1 2 10
2 8 6 3 7 5 4 1 9 10
8 2 6 3 7 5 4 1 9 10
8 7 6 3 2 5 4 1 9 10
1 7 6 3 2 5 4 8 9 10
7 1 6 3 2 5 4 8 9 10
7 3 6 1 2 5 4 8 9 10
4 3 6 1 2 5 7 8 9 10
6 3 4 1 2 5 7 8 9 10
6 3 5 1 2 4 7 8 9 10
4 3 5 1 2 6 7 8 9 10
5 3 4 1 2 6 7 8 9 10
2 3 4 1 5 6 7 8 9 10
4 3 2 1 5 6 7 8 9 10
1 3 2 4 5 6 7 8 9 10
3 1 2 4 5 6 7 8 9 10
2 1 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
------------------------------
1 2 3 4 5 6 7 8 9 10
Counting Sort.
O(N) 특정 범위 조건
package sort;
public class CountingSort {
public static void main(String[] args) {
// 특정 범위 조건이 있는 경우 빠름, O(N)
int count[] = new int[6]; //1~5
int[] num = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
int len = num.length;
//count 초기화
for(int i=0;i<count.length;i++) {
count[i] = 0;
}
for(int i=0;i<num.length;i++) {
count[num[i]]++;
}
for(int i=1;i<count.length;i++) {
for(int j=0;j<count[i];j++) {
System.out.format("%d ",i);
}
}
System.out.println("");
}
}
// 출력 결과
1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5