오늘은 앞선 버블정렬 - 이론 포스팅에서 언급한 버븡절렬 개념을 토데로


코드를 만들려고 합니다. 


저번에 만들어 놓은 Sort 클래스를 상속 받아서 만들어 볼겁니다.


아래의 2개 포스팅을 참고하세요.


http://mommoo.tistory.com/65 - 버블정렬 이론 

http://mommoo.tistory.com/64 - Sort 클래스 설계



아래는 완성된 소스 입니다.




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
public class BubbleSort extends Sort{
    private int version;
 
    public BubbleSort(int version){
        this.version = version;
        start();
    }
    
    /* Naming sort */
    @Override
    protected String getSortName() {
        if(version == 0 ) return "Normal Bubble Sort";
        else if(version == 1 ) return "Advance Bubble Sort";
        return "Bubble Sort";
    }
 
    @Override
    public void sort(){
        if(version == 0) normal();
        else if(version == 1) advance();
    }
 
    private void normal(){
        int size = DATA_LENGTH - 1;
        for(int i = 0 ; i < size ; size--){
            for(int index = 0 ; index < size; index++){
                /*
                   If the value of preceding array element is less than the value of target array element,
                   Swap two values
                */
                if(TARGET_DATA_ARRAY[index] > TARGET_DATA_ARRAY[index+1])
                    swap(index,index+1);
            }
        }
    }
 
    private void advance(){
        int size = DATA_LENGTH - 1;
        for(int i = 0 ; i < size ; size--){
            boolean isSwap = false;
            for(int index = 0 ; index < size; index++){
                /*
                   If the value of preceding array element is less than the value of target array element,
                   Swap two values
                   Any array element doesn't swap is that means already aligned.
                   So if isSwap variable is false, escape for-operator
                */
                if(TARGET_DATA_ARRAY[index] > TARGET_DATA_ARRAY[index+1]) {
                    isSwap = true;
                    swap(index,index+1);
                }
            }
            if(!isSwap) return;
        }
    }
}
 
cs




완성된 버블소트는 2가지 버전이 있습니다.


하나는 평범한 버블소트, 나머지는 개선된 버블소트 입니다.


Sort 클래스 덕분에, 지금 만드는 Bubble 소트는 sort 메서드에 로직을 기입하고,


생성자에서 start() 메서드만 사용해주면 끝입니다.


23번째의 normal() 메서드가 평범한 버블소트 로직입니다.


앞선 포스팅의 이론데로, 배열의 처음부터 끝까지 큰 숫자를 맨 뒤로 보낸후,


배열의 사이즈를 하나씩 줄여나가며, 그다음 큰숫자를 계속 뒤로 배치하는 방법입니다.


하지만 이 로직은, 배열의 사이즈가 0이 되기전에 이미 정렬이 완료되어 더이상 진행하지 않아도 되는 경우를 생각하지 않습니다.


하지만 개선된 버블소트는 만약 이미 정렬이 완료 되었다면 진행을 멈출수 있도록 로직이 구성되어있습니다.


37번째의 advance() 메서드가 개선된 버블소트 로직입니다.


이렇게 BubbleSort 클래스가 완성이 되었다면, 결과를 출력할 클래스를 하나 더 만들어야 합니다.


또한, 콘솔에 이쁘게 출력하기 위해 만든 클래스가 있습니다. 


해당 클래스는 따로 설명드리지 않고 그냥 잘 쓰셨으면 합니다.


아래에 2개의 클래스 코드가 있습니다.


SortRunner.java - 결과물 출력 클래스 (main 함수 위치)


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
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Calendar;
 
/**
 * Created by mommoo on 2017-04-05.
 */
public class SortRunner {
    public static void main(String[] args){
 
        Sort[] sorts = new Sort[]{
                new BubbleSort(0),
                new BubbleSort(1)
        };
        
        /* Sort sort-objects */
        Arrays.sort(sorts);
 
        /* Create sort printing board */
        SortBoardMaker board = new SortBoardMaker(sorts);
 
        /* Write additional information */
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy. MM. dd. hh:mm");
        String author = "Author : Mommoo";
        String title = "Title : SortProject";
        String time = "Time : "+simpleDateFormat.format(Calendar.getInstance().getTime());
 
        /* Set additional information */
        board.setAdditionalInfo(new String[]{author,title,time,"Data Length : "+Sort.DATA_LENGTH});
 
        /* print board */
        System.out.println(board);
    }
}
cs




SortBoardMaker.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
70
71
72
73
74
75
76
77
78
79
/**
 * Created by mommoo on 2017-04-18.
 */
public class SortBoardMaker {
    private final StringBuilder TOP_BOTTOM_BORDER_BUILDER = new StringBuilder();
    private final StringBuilder BLANK_LINE_BUILDER = new StringBuilder();
    private final StringBuilder CONTENT_BUILDER = new StringBuilder();
    private int textWidth;
    private String[] information;
 
    SortBoardMaker(Sort[] sorts){
 
        /* Make sort-object printing */
        for(int i = 0, size = sorts.length ; i < size ; i++){
            final int RANK = i+1;
            final String SORT_NAME = sorts[i].getRegulationSortName();
            final String SORT_TIME = sorts[i].getRegulationSpendTime();
            final boolean SORT_SUCCESS = sorts[i].isSortSuccess();
 
            CONTENT_BUILDER.append("##   ")
                    .append(RANK).append(".")
                    .append(" [ Name ] ")
                    .append(SORT_NAME)
                    .append(" [ Time ] ")
                    .append(SORT_TIME)
                    .append(" [ Sort Success ] ")
                    .append(SORT_SUCCESS)
                    .append("   ##")
                    .append("\n");
            /* Have to sub enter-character(\n) length */
            if(i == 0) textWidth = CONTENT_BUILDER.length() -1;
        }
 
        /* Make top and bottom line of board :  ################### */
        for (int i=0 ; i< textWidth ; i++ ) TOP_BOTTOM_BORDER_BUILDER.append("#");
 
        /* Make blank line of board : ##         ## */
        for (int i = 0 ; i < textWidth ; i++) BLANK_LINE_BUILDER.append(" ");
        BLANK_LINE_BUILDER.replace(0,1,"#");
        BLANK_LINE_BUILDER.replace(1,2,"#");
        BLANK_LINE_BUILDER.replace(textWidth - 2,textWidth - 1,"#");
        BLANK_LINE_BUILDER.replace(textWidth - 1,textWidth,"#");
 
    }
 
    public void setAdditionalInfo(String[] information){
        this.information = information;
    }
 
    @Override
    public String toString() {
 
        StringBuilder additionalInfo = new StringBuilder();
        StringBuilder tempBuilder = new StringBuilder();
        if (this.information != null){
            for(String info : this.information){
                tempBuilder.append(BLANK_LINE_BUILDER.toString());
                tempBuilder.replace(5,5+info.length(),info).append("\n");
                additionalInfo.append(tempBuilder.toString());
                tempBuilder.delete(0,additionalInfo.length());
            }
        }
 
        return tempBuilder
                .append(TOP_BOTTOM_BORDER_BUILDER).append("\n")
                .append(BLANK_LINE_BUILDER).append("\n")
                .append(additionalInfo)
                .append(BLANK_LINE_BUILDER).append("\n")
                .append(CONTENT_BUILDER)
                .append(BLANK_LINE_BUILDER).append("\n")
                .append(TOP_BOTTOM_BORDER_BUILDER)
                .toString();
    }
}
 
cs



SortRunner.java에서 main함수를 실행하면 아래와 같이 결과가 나옵니다.


본인이 원하는 정보를 수정 할 수 있게 클래스들을 작성하였으니, 알맞게 수정하시면 되겠습니다.




몇번 돌려보시면 확실히 개선된 버블소트가 항상 빠르게 나옵니다.


오늘 포스팅은 여기까지 입니다.


다음 코드 포스팅 역시, SortRunner 클래스와 Sort 클래스를 활용하여 선택정렬을 포스팅 할 예정입니다.


읽어주셔서 감사합니다.




포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee
  1. 2018.12.20 00:57

    코드상에서 normal과 advance의 차이점이 아래가 맞는지요?

    -normal 은 정렬할 데이터가 '최악의 상황'이 아니더라도 최악의 상황에 맞추어 '전수 검사'를 실행
    -advance는 정렬할 데이터가 '최악의 상황'일 경우 normal과 동일 혹은 조금 더 많은 시간이 소요되나 최악의 상황이 아닐 경우 중간에 정렬이 다 끝나면 정렬과정을 중단하여 시간 단축

    근데 코드를 잘 이해 못하겠네요. if(!isSwap) return; 이게 작동이 되면 정렬이 완료되었다는 뜻인데 이게 'isSwap 변수가 true값이 아닌 경우 다음 코드를 실행' 이라는 뜻이 아닌가요? 부정연산자에 대한 개념을 잘 못잡겠습니다.
    if not (isSwap)
    isSwap이 true일 경우 = if not true
    isSwap이 false일 경우 = if not false

    1차 for문에서 isSwap = false; 로 매번 값을 대입해주고 있는데
    if(!false) return; = isSwap이 false가 아니면(true 이면)
    if(!true) return; = isSwap이 true가 아니면(false 이면)

    너무 헷갈리네요.
    if(!isSwap) 에서 isSwap은 '무조건 true 임'을 가정한 상태로 if(!) 부정연산자가 작동하는지요?
    코드상 isSwap이 if문에서 무조건 true 값이어야 정상적으로 작동한다는 이야기인데 어째서 부정연산자(!)를 넣으면 변수의 값이 true 를 기준으로 연산하는지 궁금합니다. 저는 부정연산자 뒤에 붙는 값이 true면 false, false면 true 이렇게 계산하는걸로 이해했는데 뭐가 잘못 이해한건지 올려주신 코드를 이해하지 못하고 있습니다 ㅠㅠ

    1. 1차 for문에서 매번 isSwap = false; 로 값을 대입
    2. 정렬 시도가 이루어지면 isSwap = true; 을 실행, 아니면 false 값 그대로 유지
    2-1. 정렬 시도가 이루어졌을때 if(!true) = return;
    2-2. 정렬 시도가 이루어지지 않았을 때 if(!false) = return;

    혹 부정연산자 뒤에 붙는값이 true, false 처럼 직접적인 값이 아닌 변수가 오게되면 무조건 'if not true' 로 계산해서
    if(!IsSwap)은 if(false != IsSwap) 으로 계산이 되어버리는 것인지요?

    • Mommoo 2018.12.21 02:31 신고

      개선된 버블정렬은, 정렬 중간에 이미 정렬이 다 됬을 경우 탐색을 멈춤으로써, 성능을 개선하는 방법입니다.

      이때, 이미 정렬이 다 되었는가를 탐색하기 위해 저는
      "Swap 행위를 한번이라도 했느냐?"
      라는 논리식으로, 검사했습니다.

      예를들어, 만약 Swap 행위를 한번이라도 했다면, 그것은 아직 정렬이 되지 않았음을 알 수 있습니다.
      반대로, 만약 Swap 행위가 단 한번도 실행되지 않았다는 뜻은, Swap 할것이 없다. 즉, 정렬이 다 되었음을 알 수 있는것이지요.

      코드로 잘 표현했어야 하는데...
      오해의 소지를 만든거 같네요.
      답변이 도움이 되었음 하구요,
      읽어주셔서 감사합니다.

+ Recent posts