퀵정렬 포스팅

Note.

해당 글은, 퀵정렬의 기본적인 개념은 알고 있다는 전제로 진행합니다.

또한 틀린 내용이 있다면, 가감없이 알려주시면 감사하겠습니다. (_ _)

 

오늘은 퀵정렬 알고리즘에 대해 포스팅합니다.

퀵정렬 알고리즘은 매우 유명해서 검색하면 많은 자료를 찾아볼 수 있을텐데요.

저도 오랜만에 퀵정렬을 공부하려고, 많은 자료를 찾아봤는데 비슷 비슷한 코드를 볼 수 있었습니다.

그런데 말입니다.(김상중 아찌톤) 코드를 왜 그렇게 구성했는지 한번에 이해가지 않았으며, 후에 분석해본 결과 틀린 코드들도 정말 많았습니다.

어쩌면, 퀵정렬 구현이 공식처럼 알려진게 아닌가 싶고 제대로 된 코드 이해없이 비슷하게만 따라하다가 틀린 코드를 작성하는 경우가 많을거 같다는 생각을 했습니다.

그렇기에, 퀵정렬 코드를 단번에 이해못하는 멍청한 저를 위해, 나름대로 개념을 뽀개 봤습니다.

 

해당 포스팅은 아래와 같이 쓸때없는(?) 것을 연구하고 도출한 결과를 설명 해볼까합니다.

  • 왜 많은 자료들의 코드는 pivot index를 항상 끝 방향에 두고 코딩을 하는걸까? 가운데다가 두고 하면 안돼는가?

  • 왜 어떤 코드는 탐색 할 때, pivot 의 값만 비교하고, 어떤 코드는 pivot 값과 왼쪽 index 와 오른쪽 index 크기 비교까지 하는 걸까?

  • 왜 다들 오른쪽 부터, 탐색하는 코드만 작성 하는가? 왼쪽부터 탐색하면 안되는가?

  • SWAP 작업을 마치고, 마지막에 pivot index를 옮길 때, 주의해야할점

 

Pivot을 끝방향(왼쪽 끝 또는 오른쪽 끝)에 두는 이유

저는 이상한 고집이 있어서, 남들이 pivot 을 끝에다가 두면 굳이 가운데다가 해보고싶은 욕구가 있습니다. 지식을 습득할 때, 당연하게 외우기 보다 왜 그렇게만 해야하는지에 대해 아는게 중요하다고 생각하기 때문이지요.


결론적으로, pivot 을 가운데다가 배치를 하게 되면, 코드를 작성하기가 매우 까다로워 집니다.

퀵정렬의 기본개념은, 왼쪽방향과 끝쪽방향에서 서로 접근하며 바꿀 수 있는 수가 나올때 SWAP 을 시도하는것과, SWAP 작업을 마친 후, pivot 자리를 찾아주는 것이 중요합니다. 그래야 pivot 기준으로 왼쪽, 오른쪽 배열로 쪼개서 분할정복 을 시도할 수 있기 때문이지요.


문제는 pivot 이 가운데에 끼여 있으면, pivotSWAP 될수도 있다는것 입니다. 그럴경우, pivot index를 업데이트를 꼭 해주어야 합니다.


그렇지 않으면, 마지막에 pivot 자리를 찾아주는 과정에서 pivot 이 아닌 다른 값을 배치하기 때문이지요.

정리하자면, pivot을 가운데 잡아서 SWAP 작업을 진행하느니, 맨끝쪽에 pivot을 배치하여 SWAP 작업으로부터 안전하게 빼면 index 업데이트를 할 필요가 없습니다.

 

탐색할 때 비교해야할 요소

코드는 짧고 명료하고 간단한것이 매력적입니다. 멍청해서, 어려운건 이해하가 힘들거든요. (나도 똑똑해지고 싶다!!!)

그래서 그런지, 아래 코드가 끌리긴 했습니다. 굳이 왼쪽 index 와 오른쪽 index 를 비교해야 하나 싶었지요.


결론적으로는, 비교를 해야 하는게 맞습니다.

만약 하지 않는다면, index 가 배열 밖으로 벗어날 위험이 있습니다.

아래와 같은 배열이 있다고 가정해봅시다. (pivot 은 맨 왼쪽입니다.)

위 코드를 실행하면, beginIndex 는 결국 배열 크기 밖으로 빠지면서, OutOfIndex 에러가 발생하게 됩니다.

이를 방지하기 위해, beginIndex 의 조건을 배열 크기 보다 작은 경우로 줄 수도 있겠습니다.


하지만 우리가 원하는 것은 beginIndexendIndex 가 만나는 순간이고, endIndex는 배열 크기 보다 무조건 작거나 같으므로 아래와 같이 더 적은 횟수를 수행하는 조건으로 작성할 수 있습니다.

생각보다 많은 자료의 코드들이 OutOfIndex 에러가 발생하는것을 목격할 수 있었습니다.

 

 

탐색 순서가 중요한 이유

아까도 말씀드렸다 시피, 저는 이상한 고집이 있어서... 오른쪽 부터 탐색하는 코드가 많으면, 굳이 왼쪽으로 해보고 싶어집니다.(삐뚤게 살거야ㅋㅋㅋ)

해봤더니, 코드가 제대로 동작하지 않았습니다.

이상합니다. 어떤 코드는 왼쪽부터 동작하게 짰었거든요. 그렇다면 탐색 순서가 중요하긴 한가 봅니다.

고민해본결과, 왼쪽 부터 먼저 탐색하는것과 오른쪽 부터 탐색하는 결과의 차이점은 다음과 같습니다.

 

다음 그림에서, pivot을 맨 왼쪽 으로 잡았습니다.

탐색하는 코드는 다음과 같이 왼쪽부터 수행한다고 가정 한다면,

beginIndex8endIndex 도 마찬가지로 8 에 위치하게 됩니다. (index 가 아니라 입니다.!!! )

beginIndexendIndex 가 만났으니 pivot SWAP 작업을 거쳐야 하는데, 자세히 살펴보면 해당 작업을 수행하면 정렬 이 깨져 버립니다.

85 를 바꾼 후, 살펴보면 pivot 값인 5를 기준으로 왼쪽에 작은수만 있어야 하는 8 이 있어버리는 바람에 정렬이 깨져버립니다.

 

그렇다면 오른쪽부터 수행하면 어떻게 될까요?

해보시면 알겠지만, beginIndex 도, endIndex5 에 도달하게 됩니다.

pivot SWAP 작업을 거치더라도, 정렬이 깨지지 않는걸 알 수 있죠.

 

정리하자면 이렇습니다.

왼쪽부터 탐색을 수행하면, pivot 값 보다 큰 값 으로 beginIndexendIndex 가 만나게 되며,

오른쪽 부터 탐색을 수행하면, pivot 값 보다 작은 값 으로 beginIndexendIndex 가 만나게 됩니다.

 

이를 통해, 아래와 같이 생각 할 수 있습니다.

이는, 만약 맨-왼쪽으로 pivot 값 을 잡는다면, SWAP 대상이 pivot 값 보다 작은 값 이여야 하며,

맨-오른쪽으로 pivot 값 을 잡는다면, SWAP 대상이 pivot 값 보다 큰 값 이여야 함을 알 수 있습니다.

즉... 왼쪽부터냐 오른쪽 부터냐는 취향대로 하면 안되고,

pivot의 위치에 따라 반대방향으로 탐색 순서를 잡아야 함을 알 수 있습니다.

 

 

pivot swap 할 때, 주의 해야할점.

SWAP 작업의 마지막은 pivot SWAP 으로 pivot 자리를 찾아주는 것으로, 이는 매우 중요한 작업입니다.

많은 자료의 코드들이 단순하게 beginIndexendIndex 가 만나는 지점의 indexSWAP 을 시켜주는데, 이는 잘못된 코드가 될 수 있습니다.

아래와 같은 배열이 있다고 가정해봅시다. (pivot 은 맨 왼쪽입니다.)

배웠드시, 맨 왼쪽 pivot 이므로 오른쪽 부터 탐색을 수행해야 합니다.

그렇게 되면 beginIndex 와, endIndex5 에 도달하게 됩니다.

 

이때, pivot SWAP 을 진행하고 살펴보면 정렬이 깨지는걸 알 수 있습니다.

이런 현상이 왜 발생하냐면, beginIndex 가 수행할 기회 없이, 일방적으로 endIndex 가 끝으로 와버렸기 때문입니다. 즉 합의에 의한 만남이 아니라 일방적인 만남인것이지요. (말이좀 이상하네)

이런 경우가 있을 수 있기 때문에, pivot SWAP 을 진행할 때는, 데이터 크기 비교 후 진행해야 합니다.

 

정리하자면,

  • pivot 은 가운데다가 둘 수 있지만, SWAP 작업에 영향을 받을 수 있으니, 안전한 장소인 양끝에 두는걸로 하자.
  • index 탐색 작업을 수행 할 때, 배열 크기를 넘을 수 있으니 반드시 left < right 조건과 같이 탐색을 진행하자.
  • pivot 을 오른쪽 끝에 둘거면, 탐색 순서를 왼쪽부터! pivot 을 왼쪽 끝에 둘거면, 탐색 순서를 오른쪽 부터 진행하자.
  • pivot SWAP 을 진행할 때는, 해당 요소의 크기 조건이 안맞는 경우도 있으니 크기 조건을 반드시 추가하자.

 

마무으리

위에 진행한 코드는 아래에 경로에서 볼 수 있습니다.

https://github.com/Mommoo/Programmers/blob/master/src/com/mommoo/practice/sort/QuickSort.java

코드를 봐도 이해가 안간다는건 참 속상한 일입니다.

이렇게 분석을 나름 열심히 했는데도 틀린 분석이라면 더 속상할 거 같습니다.

만약에 이 게시글을 보고 틀린점이 있다면, 꼭 알려주셨으면 합니다.

읽어주셔서 감사합니다.

 


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

Buy me a coffeeBuy me a coffee

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


코드를 만들려고 합니다. 


저번에 만들어 놓은 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


안녕하세요. Mommoo 입니다.


오늘은 정렬 중에, 학습하기 쉬운 버블정렬에 대해 포스팅 합니다.


버블 정렬이 어떻게 진행되는지 gif파일로 만들어 봤습니다.


버블정렬?



물속에 있는 거품이 수면위로 보글보글 하게 올라오는 것처럼,


제일 무거운 원소가 배열의 최상단까지 올라가는 과정을 마치 거품이 올라가는 것과 같다 하여 


이름을 버블정렬이라 지었습니다.




버블정렬의 원리



만약 아래와 같은 배열이 있다고 가정해봅시다.


위의 배열을 내림차순으로 정렬 해보려고 합니다. (1 2 3 4 5 6)


버블정렬은 정렬이 안된 배열의 범위내에서, 서로 붙어 있는 배열 요소 2개씩 비교해 나갑니다.


붙어있는 배열요소 2개를 비교했을시, 큰쪽을 뒤쪽으로 배치 한후, 


처음 비교 요소중 2번째 요소와 다음 요소(3번째요소) 를 또 비교합니다. 마찬가지로 2개의 요소중 큰 요소를 배치하구요.


이런식으로 배열의 끝까지 비교를 했을시, 첫 배열범위에서 제일 큰 수가 맨 뒤로 배치 됩니다.


아래의 예시를 보시면 더욱 이해가 잘 될겁니다.




1세트를 마치게 되면 첫번째 배열 범위(1~6번째)에서 제일 큰 숫자인 6이 맨 뒤에 배치 됩니다.


또한, 1세트를 마치면 맨뒤에 요소 6은 정렬이 완료 된 상태 입니다. 따라서, 배열범위를 변경해야 합니다. (1~5번째로 변경)



아래는 2세트 에서의 예시 입니다.



2세트를 마치게 되면 바뀐 배열 범위(1~5번째)에서 제일 큰 숫자인 5가 배열 범위 맨 뒤에 배치됩니다.


또한, 맨뒤의 요소 5,6은 정렬이 완료 된 상태 이므로, 배열 범위를 변경합니다.(1~4번째로 변경)




이런식으로, 한세트가 끝나면, 배열 범위를 바꾼 후 2개씩 비교를 해 나가면, 배열 뒤쪽에서는 내림차순으로 정렬이 됩니다.


결과적으로, 버블정렬의 가장 큰 특징은 범위 내의 제일 큰 숫자를 뒤로 배치 하는 것과, 배열범위를 하나씩 줄여가는것 입니다.



지금까지의 설명을 읽고, 맨 위의 gif를 다시 본다면 재밌게 보실 수 있습니다!.



버블정렬의 성능


소트의 성능을 생각해볼때, 공간복잡도와 시간복잡도를 생각해보게 됩니다.


공간 복잡도는 말그데로, 배열만을 썻느냐, 아님 추가 배열을 썼느냐 등을 가리는 것이고


시간 복잡도는 정렬을 하는데 시간이 얼마나 소요 됬는지를 알아봅니다.


정렬은 공간 복잡도 보다, 시간 복잡도가 직결되므로 시간 복잡도만 알아볼것입니다.


시간복잡도는 보통 빅O 표기법으로 표시를 하는데,


빅O 표기법은 걸린시간의 최악의 경우만을 표기합니다. 


또한, 걸린 시간에서 부수적인 계산요소들은 생략하여 표기합니다.


버블정렬의 빅O 표기법을 구해보자면 아래와 같습니다.


만약 배열이 정렬 된 상태에서 정렬이 걸린시간을 생각하면, 한번만 비교해본후, 


정렬된걸 감지한후, 더이상 비교와 교환을 하지 않습니다. 


만약 배열의 크기가 n이라 하면, 교환은 한번도 이루어지지 않고, 비교만 (n번)합니다. (최선의 상황)


위의 배열 예시는 정렬이 하나도 되지 않은 최악의 상황입니다. 오히려 역으로 정렬된 상태입니다.


위의 배열은 비교를 n번 + n-1번 + n-2번 + n-3번 + n-4번 +.....+ 1번 하므로, 결국 n*(n+1)/2 의 비교횟수와


n*(n+1)/2의 교환 횟수를 가집니다. (최악의 상황


따라서 빅O 표기법의 조건중 하나인 최악의 상황 n*(n+1)/2으로 따지는데, 


이것을 아래와 같이 부수적인 계산요소들은 생략합니다.


따라서 빅O 표기법은 O(n^2) 입니다.


이는 앞으로 볼 정렬에 비교한다면, 느린편에 속합니다.


다음 포스팅은 버블정렬 - 자바코드 편을 포스팅 하겠습니다.


읽어주셔서 감사합니다.

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

Buy me a coffeeBuy me a coffee

안녕하세요. Mommoo 입니다.


앞으로 버블 정렬,선택 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬을 만들어 볼텐데요,


이러한 정렬 들을 만들기 쉽게, 디버깅을 편하게 하기 위해 조상 클래스 Sort를 만들어 보고자 합니다.


기본목표는 아래와 같습니다.


    • 정렬들간의 비교분석을 위해 같은 배열 데이터를 참조하게 한다.
    • 데이터의 갯수만 변경하면 데이터가 갯수에 맞게, 랜덤값이 자동적으로 생성되게 한다.
    • 정렬들간의 비교를 위하여 공통된 행위 설계. ( sort할때 걸리는 시간, sort가 성공했는지 여부, 규격화된 디버깅 설계 등등...)
    • Comparable 인터페이스를 구현 해, Sort클래스를 상속받는 수 많은 정렬 클래스들이 시간 순으로 랭크화 하게 한다.


먼저 완성된 소스입니다.


특이점등을 설명해드리자면...


▶  6번의 DATA_LENGTH 변수는 추후에, 데이터 갯수를 표시하기 위해 public으로 공개했습니다.


▶  16번의 static 초기화 부분에서는 자동적으로 랜덤 값을 넣어주며, sort가 성공했는지 여부를 알기 위해

미리 sort된 배열도 하나 만들었습니다.


▶  각각의 자식 클래스마다 공통된 배열의 값을 참조를 해야하지만, 자식만의 배열을 가져야 하므로,

28번의 배열을 protected로 추가했습니다.


▶  36, 39번의 메서드는 각 자식 클래스마다 독립적인 내용이므로 자식에게 구현을 맡겼습니다.


▶  42번의 start 메서드는 자식 클래스가 start 메서드를 사용했을시, sort가 진행되고 sort 진행시간이 기록됩니다.

또한, 프린팅을 줄 맞춰서 예쁘게 하기위해, 프린팅 정보중 너비가 제일 긴 텍스트의 길이를 저장했습니다.


▶  58번의 swap 함수는 sort에서 빠지지 않는 swap기능을 미리 구현해놓았습니다.


▶  117번의 toString메서드는 자식 클래스의 소트가 진행됬을경우, 정보를 프린팅 하기위해 구현했습니다.


▶  129번의 compareTo 메서드는 Comparable을 구현하기위해 오버라이딩 했습니다. 추후에

자식클래스들을 시간순으로 정렬하기 위해 작성했습니다.


준비한 내용은 여기까지 입니다.


다음 포스팅은, 이러한 Sort 클래스를 상속받아 Bubble 소트를 만들어보겠습니다!

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

Buy me a coffeeBuy me a coffee

  안녕하세요. Mommoo 입니다.


오랜만에 글을 쓰네요. 이전 포스팅들을 읽어보시면 아시겠지만, 


저의 문체(?) 중 하나는 높임말을 사용하지 않는 것이었는데요.


오늘 부로 생각이 바뀌었습니다.  이제부터는 높임말을 사용하려 합니다.




  서론이 길었는데요,


이번에 준비한 포스팅 들은 지금 보시는거 포함해서, 버블정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 퀵 정렬 이렇게 


총 6개 정도가 될 예정입니다. 저도 많이 부족하지만, 초보자들이 쉽게 배울 수 있도록 포스팅 순서 배치와


내용의 질적인 측면을 신경을 많이 썼습니다.  아무쪼록, 저 포함해서 서로 다같이 공부 할 수 있는


기회가 됬으면 합니다.



 만들어진 자바 데이터 정렬 프로젝트의 결과물은 아래와 같습니다.




물론 코드도 공개를 하지만,


각 정렬이 무엇이며, 직접 짜보는 과정에서 배운 개념과 중요하다 생각하는 점 등을


포스팅으로 작성 할 예정입니다.



첫번째 포스팅은 버블 정렬 부터 입니다.


감사합니다.






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

Buy me a coffeeBuy me a coffee

+ Recent posts