반응형
https://github.com/mbk1991/Algorithm_DataStructure/tree/master/Algorithm_DataStructure%2Fsrc%2Fmain%2Fjava%2FAlgorithm%2Fsort
정렬 알고리즘을 공부 중 알고리즘과 배열 생성 방법을 선택하여 정렬하는 프로그램을 만들어보았다. 여러가지 정렬 알고리즘을 공부하는 김에 객체 지향적으로 만들어보고자 하였다.
개선할 점이 아주 많은 코드이다. 정렬 알고리즘들이 잘 동작하지만 우선 속도가 끔찍하게 느리다. 많은 이유가 있겠지만 불필요한 비교 및 오토박싱 등으로 과도한 객체 생성을 하고 있는 것으로 보인다. 성능 개선을 위하여 기본 타입을 사용하는 등 여러모로 개선이 많이 필요하다. 자바 기본기와 이펙티브 자바 서적을 읽으면서 조금씩 리펙토링을 해나가보자. SOLID원칙 준수 및 디자인 패턴 활용을 통한 객체지향적 리펙토링도 필요하다.
JUnit으로 점진적으로 유닛테스트를 해가며 직접 정렬 알고리즘을 구현하였고 디버깅을 적극 활용하니 굉장히 편리했다.
Main.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
package Algorithm.sort;
import java.util.*;
public class Main {
public static <T> void main(String[] args){
String sort;
String gen;
Scanner sc = new Scanner(System.in);
System.out.println("정렬 알고리즘의 종류를 입력하세요. (버블,삽입,선택,퀵,머지)");
sort = sc.nextLine().replace(" ","").toLowerCase();
System.out.println("정렬 대상 배열 생성 방법을 입력하세요. (랜덤, 입력)");
gen = sc.nextLine().replace(" ","").toLowerCase();
try{
Sorter sorter = SorterFactory.getSorter(sort,gen);
T[] T = sorter.getArr();
System.out.println("정렬 전--- ");
if(T.length <= 100){
System.out.println(Arrays.toString(T));
}
sorter.measureSort(T);
System.out.println("정렬 후--- ");
if(T.length <= 100){
System.out.println(Arrays.toString(T));
}
}catch(Exception e){
System.out.println("입력값을 확인 후 다시 이용해주세요.");
}
}
}
|
cs |
Sort.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public abstract class Sort {
private String name;
public Sort(String name){
this.name = name;
}
public abstract <T> void sort(T[] T);
public String getName(){
return this.name;
}
}
|
cs |
BubbleSort.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
import static Algorithm.sort.sortalgorithm.SortTool.compareT;
import static Algorithm.sort.sortalgorithm.SortTool.swap;
public class BubbleSort extends Sort{
public BubbleSort(String name){
super(name);
}
@Override
public <T> void sort(T[] T) {
boolean flag = true;
for(int i=0; i<T.length; i++){
for(int j=0; j<T.length-i-1; j++){
if(compareT( T[j], T[j+1]) > 0){
swap(T,j,j+1);
}
flag = false;
}
if(flag){
break;
}
}
}
}
|
cs |
InsertionSort.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import static Algorithm.sort.sortalgorithm.SortTool.compareT;
import static Algorithm.sort.sortalgorithm.SortTool.insert;
public class InsertSort extends Sort {
public InsertSort(String name) {
super(name);
}
@Override
public <T> void sort(T[] T) {
for (int i = 1; i < T.length; i++) {
for (int j = 0; j <= i - 1; j++) {
if (compareT(T[i], T[j]) < 0) {
insert(T, i, j); // i번째 인덱스의 값을 j번째 인덱스의 위치에 삽입
}
}
}
}
}
|
cs |
SelectionSort.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import static Algorithm.sort.sortalgorithm.SortTool.compareT;
import static Algorithm.sort.sortalgorithm.SortTool.swap;
public class SelectionSort extends Sort {
public SelectionSort(String name){
super(name);
}
@Override
public <T> void sort(T[] T) {
for(int i=0; i<T.length; i++){
int minIndex = i;
for(int j=i+1; j<T.length; j++){
if(compareT(T[minIndex], T[j]) > 0){ // j번째 인덱스의 값이 minIndex의 값보다 작으면
minIndex = j;
}
}
swap(T,i,minIndex);
}
}
}
|
cs |
QuickSort.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
package Algorithm.sort.sortalgorithm;
import static Algorithm.sort.sortalgorithm.SortTool.compareT;
import static Algorithm.sort.sortalgorithm.SortTool.swap;
/**
* 퀵정렬(QuickSort)
* 시간복잡도 O(nlogn)의 준수한 정렬
* 피벗(pivot)이라는 기준점을 정하고
* 피벗보다 작은 수는 피벗의 왼쪽, 피벗보다 큰 수는 피벗의 오른쪽으로 배치한다.
* 자연스럽게 피벗으로 정해진 요소의 위치는 확정된다.
* 피벗의 왼쪽부분과 오른쪽 부분에 대하여 재귀적으로 처리하여 정렬을 완성한다.
*
*/
public class QuickSort extends Sort {
public QuickSort(String name) {
super(name);
}
@Override
public <T> void sort(T[] T) {
int start = 0;
int end = T.length - 1;
qckSort(T, start, end);
}
public <T> void qckSort(T[] T, int s, int e) {
int pivotIndex = partition(T, s, e);
if (pivotIndex - s > 1) {
qckSort(T, s, pivotIndex - 1);
}
if (e - pivotIndex > 1) {
qckSort(T, pivotIndex + 1, e);
}
}
public <T> int partition(T[] T, int s, int e) {
int pivotIndex = s;
int i = s + 1;
int j = e;
while (i < j) {
while (compareT(T[i], T[pivotIndex]) < 0 && i < j) {
i++;
}
while (compareT(T[j], T[pivotIndex]) > 0 && i < j) {
j--;
}
swap(T, i, j);
}
if (compareT(T[j], T[pivotIndex]) < 0) {
swap(T, pivotIndex, j);
} else {
swap(T, pivotIndex, --j);
}
pivotIndex = j;
// System.out.println(Arrays.toString(T));
return pivotIndex;
}
}
|
cs |
MergeSort.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
package Algorithm.sort.sortalgorithm;
import java.util.Arrays;
import static Algorithm.sort.sortalgorithm.SortTool.compareT;
public class MergeSort extends Sort {
public MergeSort(String name){
super(name);
}
@Override
public <T> void sort(T[] T) {
T[] src = Arrays.copyOf(T, T.length);
int start = 0;
int end = T.length-1;
mergeSort(T, src, start, end);
}
public <T> void mergeSort(T[] dest, T[] src, int s, int e){
int length = e - s;
if(length < 1){
return;
}
int m = (s + e) >>> 1;
mergeSort(dest, src, s, m);
mergeSort(dest, src, m+1, e);
for(int j=s; j<=e; j++){
src[j] = dest[j];
}
for(int k=s, p1=s, p2=m+1; k<=e; k++){
if(p2 > e || p1 <= m && compareT(src[p1], src[p2]) < 0){
dest[k] = src[p1++];
}else{
dest[k] = src[p2++];
}
}
// System.out.println(Arrays.toString(T));
}
}
|
cs |
ArrGenerator.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public abstract class ArrGenerator {
private String name;
public ArrGenerator(String name){
this.name = name;
}
public abstract <T> T[] genArr();
public String getName(){
return this.name;
}
}
|
cs |
RandomGen.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
package Algorithm.sort.arrgen;
import java.util.Random;
public class RandomGen extends ArrGenerator{
private final int KOREAN_UNIKODE_START = 0XAC00;
private final int KOREAN_UNICODE_BOUND = 0XD7A3 - 0XAC00;
public RandomGen(String name){
super(name);
}
@Override
public <T> T[] genArr() {
Random rd = new Random();
boolean randomLength = false; // true: 범위내에서 배열의 길이 랜덤 생성, false: 고정길이
int lengthFrom = 0;
int lengthTo = 100;
int intBound = 1000;
int length = randomLength? (rd.nextInt(lengthFrom + 1)+ lengthTo) : lengthTo;
int rand = rd.nextInt(2);
// int rand = 1;
T[] T;
if(rand == 0){
String[] tmp = new String[length];
for(int i = 0; i < tmp.length; i++){
tmp[i] = (char)(rd.nextInt(KOREAN_UNICODE_BOUND) + KOREAN_UNIKODE_START) + "";
}
T = (T[])tmp;
}else{
Integer[] tmp = new Integer[length];
for(int i = 0; i < tmp.length; i++){
tmp[i] = rd.nextInt(intBound);
}
T = (T[]) tmp;
}
if(randomLength){
System.out.println("길이 "+lengthFrom+"~"+(lengthFrom + lengthTo)+"의 String 또는 int 배열을 랜덤으로 생성하여 반환합니다.");
}else{
System.out.println("길이" + lengthTo + "의 String 또는 int 배열을 랜덤으로 생성하여 반환합니다.");
}
return T;
}
}
|
cs |
InputGen.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
package Algorithm.sort.arrgen;
import java.util.Scanner;
public class InputGen extends ArrGenerator {
public InputGen(String name){
super(name);
}
@Override
public <T> T[] genArr() {
Scanner sc = new Scanner(System.in);
System.out.println("숫자 및 문자를 공백으로 구분하여 입력하세요.\n(문자가 없을 경우 int 배열, 문자가 있을 경우 String 배열 반환) >>");
String strInput = sc.nextLine();
strInput.trim();
T[] T;
String[] strArr = strInput.split(" +");
Integer[] intArr = new Integer[strArr.length];
for(int i=0; i<strArr.length; i++){
try{
intArr[i] = Integer.parseInt(strArr[i]);
}catch(NumberFormatException e){
T = (T[]) strArr;
return T;
}
}
T = (T[]) intArr;
return T;
}
}
|
cs |
SortTool.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
package Algorithm.sort.sortalgorithm;
public class SortTool {
public static <T> void swap(T[] T, int leftIndex, int rightIndex){
T tmp = T[leftIndex];
T[leftIndex] = T[rightIndex];
T[rightIndex] = tmp;
}
public static <T> void insert(T[] T, int targetIndex, int locationIndex){
if(targetIndex < locationIndex){
return;
}
T tmp = T[targetIndex];
for(int i=targetIndex; i>locationIndex; i--){
T[i] = T[i-1];
}
T[locationIndex] = tmp;
}
public static <T> int compareT(T t1, T t2){
if(t1 instanceof Integer && t2 instanceof Integer){
return (Integer) t1 - (Integer) t2;
}else{
String strT1 = (String) t1;
String strT2 = (String) t2;
return strT1.compareToIgnoreCase(strT2);
}
}
}
|
cs |
Sorter.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
package Algorithm.sort;
import Algorithm.sort.arrgen.ArrGenerator;
import Algorithm.sort.sortalgorithm.Sort;
public class Sorter {
private Sort sort;
private ArrGenerator aGen;
public Sorter(Sort sort, ArrGenerator aGen){
this.sort = sort;
this.aGen = aGen;
}
public <T> Sorter doSort(T[] T){
System.out.println(sort.getName() + " : 정렬을 수행합니다.");
sort.sort(T);
return this;
}
public <T> T[] getArr(){
System.out.println(aGen.getName() + " : 정렬할 배열을 생성합니다.");
return aGen.genArr();
}
public <T> void measureSort(T[] T){
long start;
long end;
System.out.println("정렬전 시각 : " + (start = System.currentTimeMillis()));
sort.sort(T);
System.out.println("정렬후 시각 : " + (end = System.currentTimeMillis()));
System.out.println("정렬소요시간 : " + (end -start));
}
}
|
cs |
SorterFactory.java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
package Algorithm.sort;
import Algorithm.sort.arrgen.InputGen;
import Algorithm.sort.arrgen.ArrGenerator;
import Algorithm.sort.arrgen.RandomGen;
import Algorithm.sort.sortalgorithm.*;
public class SorterFactory {
private final static String[] CHK_SORT = {"버블,bubble","삽입,인서트,insert","선택,셀렉트,셀렉션,select","퀵,quick","병합,머지,merge"};
private final static String[] CHK_GEN = {"랜덤,random","입력,input"};
private SorterFactory(){}
public static Sorter getSorter(String sort, String gen) throws Exception {
Sort s = null;
ArrGenerator a = null;
sort = sort.replace(" ","");
gen = gen.replace(" ","");
for(int i=0; i<CHK_SORT.length; i++){
if(CHK_SORT[i].contains(sort)){
switch(i){
case 0: s = getBubbleSort(); break;
case 1: s = getInsertSort(); break;
case 2: s = getSelectionSort(); break;
case 3: s = getQuickSort(); break;
case 4: s = getMergeSort(); break;
}
}
}
for(int i=0; i<CHK_GEN.length; i++){
if(CHK_GEN[i].contains(gen)){
switch(i){
case 0: a = getRandomGen(); break;
case 1: a = getInputGen(); break;
}
}
}
if(s == null && a == null){
throw new Exception();
}
return new Sorter(s,a);
}
private static BubbleSort getBubbleSort(){
return new BubbleSort("Bubble Sort!");
}
private static InsertSort getInsertSort(){
return new InsertSort("Insert Sort!");
}
private static SelectionSort getSelectionSort(){
return new SelectionSort("Selection Sort!");
}
private static QuickSort getQuickSort(){
return new QuickSort("Quick Sort!");
}
private static MergeSort getMergeSort(){
return new MergeSort("Merge Sort!");
}
private static RandomGen getRandomGen(){
return new RandomGen("Random Generator!!");
}
private static InputGen getInputGen(){
return new InputGen("Input Generator!!");
}
}
|
cs |
반응형
'개발 > 개발관련' 카테고리의 다른 글
| [개발관련] 사설 IP 관련 조사 (0) | 2023.08.10 |
|---|---|
| [개발관련] Docker 조사 (0) | 2023.08.10 |
| [개발관련] No Test Roots Found (0) | 2023.08.03 |
| [개발관련] Package name 'main.java.Algorithm. ... ' does not correspond to the file path 'Algorithm. ...' (0) | 2023.08.03 |
| [개발관련] API(Application Programming Interface)에 대한 이해 (0) | 2023.07.22 |