퀵정렬 포스팅

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

  오늘 포스팅 할 내용은 Android LinearLayout과 비슷한 Java의 Swing LinearLayout Manager 입니다.


Java가 기본적으로 제공하는 레이아웃은 아래와 같습니다.


  "FlowLayout,  BorderLayout, GirdLayout, BoxLayout, GridBagLayout"


우리는 GUI를 만들때, 버튼이나 라벨같은 컴포넌트들이 수직 정렬로 배치 되는걸 선호 합니다.


만약 컴포넌트들을 수직 정렬로 배치한다면, 위 레이아웃 중 무엇을 선택해야 할까요?


하나씩 살펴보겠습니다.




FlowLayout


  FlowLayout은 가로 방향으로 하나씩 쌓아가면서, 가로 방향 공간이 없을 시, 한칸 내려서 다시 가로 방향으로 쌓습니다.


이 특징을 이용하여 우리는 컴포넌트의 가로 크기를 가로 크기를 창 가로 크기 만큼 잡았을 시, 수직 정렬을 구현 할 수 있습니다.


하지만, 컴포넌트의 가로크기를 창 크기만큼 잡아야 한다는 단점과, 창의 크기를 움직였을때, 가로에 남는 공간이 생긴다면 수직정렬이


깨지기도 합니다. padding 크기를 준다 하더라도, 각 컴포넌트에게 JPanel을 감싸야 하는 불편함이 있죠.





BorderLayout


  BorderLayout은 동서남북 가운데 방향에 컴포넌트를 넣을 수 있습니다. 수직 정렬로 쌓으려면 북, 가운데, 남 이렇게 3방향을 써야 하는데요


이렇게 3개의 공간뿐이 쓰질 못하니, 3개의 공간안에 또, JPanel을 배치한 후, 그 JPanel안에 또 컴포넌트를 쌓는 방법밖에 없습니다.


그리고 해보시면 알겠지만, 컴포넌트 사이즈를 원하게 조종하는것도 만만치 않습니다.




GridLayout


  GridLayout은 간단하면서도 짜증납니다. 그 이유는 수직정렬 자체는 쉽습니다.


다만,  GridLayout 레이아웃 특성상 모든 컴포넌트의 크기가 같습니다. 


모든 컴포넌트의 크기가 같아야 하는 경우도 있겠지만, 그런 경우는 흔치 않습니다.





BoxLayout, GridBagLayout


  BoxLayout, GirdBagLayout이 우리가 원하는 수직 정렬을 하기 위해 필요한 레이아웃이라 볼 수 있습니다. 


단점은 너무 어렵습니다.


BoxLayout은 제 개인적으로 사용해 본 결과 이상하게 오작동하며, 


특히 GridBagLayout은 GridBagConstraints라는 제약조건을 설정할 수 있는 객체와 함께 사용하는데, 사용 방법이 무척 어렵습니다.






LinearLayout


 간단한 수직정렬 조차 괜찮은 레이아웃이 없던 상황에, 안드로이드 프로그래밍을 할때 썼었던 LinearLayout이 생각났었습니다. 


있을땐 몰랐는데 없으니까, 참 쓰기 괜찮은 레이아웃 이였다는 생각이 들었습니다.


결국 직접 만들었습니다.  오픈소스로 제작했구요, 해당 URL 은 아래와 같습니다.


https://github.com/Mommoo/FlatSwing/tree/master/src/com/mommoo/flat/layout/linear


사용방법이 어려운건 선호하지 않기 때문에 최대한 간단한 방향으로 만들었습니다.


아래의 코드는 LinearLayout을 이용한 예시입니다.


예시는 전부 수직정렬만 보여주지만, 수평정렬도 가능합니다.


주석을 읽어보면 어렵지 않게 쓰실 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
JFrame frame = new JFrame();
frame.setSize(500,500);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
 
JPanel panel = new JPanel();
panel.setLayout(new LinearLayout(Orientation.VERTICAL, 15));
 
// 기본 컴포넌트 크기입니다.
panel.add(new JButton("Test1"));
 
// 설정한 방향과 상반되는 방향의 크기를 부모창 크기 만큼 맞춥니다.
panel.add(new JButton("Test2"), new LinearConstraints().setLinearSpace(LinearSpace.MATCH_PARENT));
 
// 기본 컴포넌트 크기에 가운데 정렬 입니다.
panel.add(new JButton("Test3"), new LinearConstraints().setLinearSpace(LinearSpace.WRAP_CENTER_CONTENT));
 
// 원하는 컴포넌트 크기입니다.
JButton button = new JButton("Test4");
button.setPreferredSize(new Dimension(300,200));
panel.add(button);
 
frame.setContentPane(panel);
frame.setVisible(true);
cs


아래의 스샷은 결과물 입니다.



또한 만든 LinearLayout은 멋진 Weight 속성을 줄 수 있습니다.


무게 속성을 이용한다면, 예쁘게 GUI배치를 할 수 있습니다.


아래의 코드를 참고하세요. 


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
JFrame frame = new JFrame();
frame.setSize(500,500);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
 
JPanel panel = new JPanel();
panel.setLayout(new LinearLayout(Orientation.VERTICAL, 15));
 
// 기본 컴포넌트 크기에 무게 4만큼 차지 합니다.
panel.add(new JButton("Test1"), new LinearConstraints().setWeight(4));
 
// 설정한 방향과 상반되는 방향의 크기를 부모창 크기 만큼 맞추고, 무게 2만큼 차지 합니다.
panel.add(new JButton("Test2"), new LinearConstraints().setWeight(2).setLinearSpace(LinearSpace.MATCH_PARENT));
 
// 기본 컴포넌트 크기에 가운데 정렬이 진행되며 무게 1만큼 차지 합니다.
panel.add(new JButton("Test3"), new LinearConstraints().setWeight(1).setLinearSpace(LinearSpace.WRAP_CENTER_CONTENT));
 
// 원하는 컴포넌트 크기와, 무게 3만큼 차지합니다.
JButton button = new JButton("Test4");
button.setPreferredSize(new Dimension(300,200));
panel.add(button, new LinearConstraints().setWeight(3));
 
//총 무게는 4 + 2 + 1 + 3 = 10이므로, 각 컴포는트는 10에서 무게 크기 만큼 크기를 나눠 가집니다.
 
frame.setContentPane(panel);
frame.setVisible(true);
cs



아래의 스샷은 결과물 입니다.




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


LinearLayout은 현재 만들고 있는 Swing 라이브러리에 있습니다. 


현재 제작중이라... 버그가 있을 수 있습니다. 


알려주시면 빠르게 수정 할 수 있으니, 알려주시면 감사하겠습니다.


좀더 많은 정보를 알고 싶으시면 아래의 URL을 참고해주세요. 


FlatSwing - https://github.com/Mommoo/FlatSwing (멋진 Flat디자인이 적용된 스윙 라이브러리)


감사합니다.

'Java' 카테고리의 다른 글

[Java] 파일 경로 처리하기.  (2) 2019.01.24
JAVA - JNI 사용하기  (2) 2017.09.02
JAVA - DownCasting(다운캐스팅)  (25) 2016.08.27
JAVA - HashMap key 구하기.  (1) 2016.08.25
JAVA - 변수 선언할때 m을 왜 붙일까?  (2) 2016.07.05

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

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 입니다.


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


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


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




  서론이 길었는데요,


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


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


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


기회가 됬으면 합니다.



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




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


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


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



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


감사합니다.






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

Buy me a coffeeBuy me a coffee

오늘은 Enum 자료형에 대해 포스팅 한다.

자바 1.5가 추가 됨으로써, 새로운 참조자료형이 추가 됬다.

그중 하나는, 열거자료형(Enum Type)이라 불리는

새로운 종류의 클래스이다.

보통 자바에서 상수의 열거는 아래와 같이 작성한다.


public static final int AMERICANO = 0;

public static final int CAFE_MOCHA = 1;

public static final int CAFE_LATTE = 2;


public static final int APPLE_JUICE = 0;

public static final int ORANGE_JUICE = 1;

public static final int GRAPE_JUICE = 2;


책에서 말하길, 이 기법은 int enum 기법이라 한다.

하지만, 이 기법은 치명적인 단점이 있다. AMERICANO 와 APPLE_JUICE는 우리가 보고있는 이름은 틀리지만,

값은 0으로 같은 상황이다. 즉, 아래와 같은 메서드가 있다고 가정할 시,


public static void makeCoffee(int coffeeType){

  //..........

}


해당 메서드는 APPLE_JUICE를 넣더라도 컴파일 오류 없이, 아메리카노를 넣은 것과 똑같이 잘 실행이 된다. 

이유는 위에서도 적었다 시피, 같은 0값이기 때문이다.

또한, 우리는 값 0으로 구분하는 것이 아닌 이름, 즉 변수명으로 구분한다. 변수명을 보고

이것이 아메리카노, 오렌지 쥬스등을 파악하기 때문이다. 하지만, int enum기법은 문자열로 변환하기가 녹록치 않다.

원하는 문자열로 변환해주는 메서드 if ~ else 조합으로 만들 수는 있겠지만, 해서는 안될 짓이다.

왜냐하면 아이템이 추가 될때마다, 단적으로 else를 추가해 줘야하고,  

그 메서드로 인해 영향을 받는 모든 코드들을 수정해야 하기때문에 유지보수에 큰 난항을 겪기 때문이다.


그렇다면, 문자열로 변환하기 쉽게 toString() 메서드를 제공하는, String 클래스를 이용하여 아래와 같이 열거형을 만들면 어떨까? 

public static final String AMERICANO = "0";

위와 같이 열거형을 구성하면, AMERICANO.toString()을 실행하면 원하는 문자열인 "AMERICANO"를 얻을 수 있지만,

String enum 패턴이라 불리는 이 패턴은 해서는 안 될 패턴이다. 

문자열 비교는 성능을 떨어 트릴 수 있고, 클라이언트 입장에서

인자를 넣기를 AMERICANO변수를 이용하지 않고, "0"으로 메서드를 실행 할 수 있는 가능성이 있기 때문에, 좋지 않다.

이렇게 됬었을 시, 설계자가 AMERICANO를 바꿨을시, 클라이언트의 코드는 원하느 결과가 나오지 않을 뿐더러,

컴파일 오류가 나지 않는 경우는 버그를 찾기 힘들기 때문이다.


이러한 문제점을 해결하기 위한 대안이 바로 열거형 자료형인 Enum 이다.

위에서 예로 적은 상수들을 아래와 같이 Enum 열거형으로 바꿔보았다.

public enum Coffee { AMERICANO, CAFE_MOCHA, CAFE_LATTE }

public enum JUICE { APPLE_JUICE, ORANGE_JUICE, GRAPE_JUICE }

위 enum클래스는 클라이언트가 접근 할 수 있는 생성자가 없다. 또한 final 이 내부적으로 선언되 있으므로,

객체생성, 상속이 되지 않는다. 


enum의 장점 중 하나는 컴파일 시점 시 형 안정성을 제공해준다. 

Coffee자료형은 반드시 Coffee안에 존재하는 열거 상수를 받아야 하지,

JUICE의 열거 상수가 들어가면 컴파일 오류가 발생한다. 

위에서 말한 int enum의 문제점인 makeCoffee안에 APPLE_JUICE를 넣더라도 실행되는걸 막을 수 있단 얘기이다.

또한 enum은 같은 값을 가진 상수들을 평화롭게 공존 시킬 수 있는데,

enum의 이름으로 각 상수들을 구분 할 수 있기 때문이다.

enum은 각 상수마다 toString 메서드를 사용 할 수 있어, 문자열로 쉽게 변환이 가능하다.

enum역시 클래스므로, 변수와 메서드를 추가 할 수 있다. 

위에서 작성한 열거 상수들은 변수가 아닌 상수임에 유의 하자.

변수와 메서드를 추가 하는 이유는 간단하다. 상수를 좀더 멋지게 사용하고 싶은 생각이 있는 것이다.


해당 내용은 다음 포스팅에서 계속한다.


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

Buy me a coffeeBuy me a coffee

이번 포스팅은 저번에 이어


마지막 차례인 DownCating(다운 캐스팅)이다.


아래의 URL은 현재 기술할 내용을 이해하기 위해


필요한 내용을 기술한 포스팅이다.


http://mommoo.tistory.com/40 - 캐스팅

http://mommoo.tistory.com/41 - 업캐스팅


이전 업캐스팅 내용을 토데로 복습하자면


자바에서는 관련있는 데이터 끼리 형변환이 가능 했었다.


ex) (Child 클래스가 Parent 클래스를 상속받은 경우)


Parent parent = new Child();


윗 경우는 업캐스팅이라 했었고, 형변환 기호( (Parent) )를 붙여주지 않더라도


생략이 가능하다.


그렇다면 반대인 경우는 어떨까?


Child child = new Parent();


앞서 포스팅에서 기술 한 것처럼, 관련있는 데이터 끼리는


캐스팅이 가능하다고 했다. 하지만 , 위의 경우는 성립하지 않는다.


왜냐하면 앞서 포스팅에서 덧붙여 설명했던 개념인,


변수가 원하는 정보를 다 채워줘야하는 원칙에 어긋난다.


Child 클래스는 Parent 클래스를 상속받았기 때문에 Parent 클래스보다는 


Child 클래스가 더욱 많은 데이터를 가졌을 것이다.


즉,


child 변수가 원하는 정보는 Child 클래스의 데이터 전부를 원하는데,


Parent 인스턴스 ( new Parent(); ) 는 Parent 데이터만 가지고 있을 뿐,


Child의 데이터를 가지지 않는다. 그러므로 빨간줄이 그어지면서


컴파일 오류를 발생시킨다.



그렇다면, 위의 경우에서 형변환을 시켜준다면 어떨까?


Child child = (Child)new Parent();


개발툴에서 확인해보면, 컴파일 오류에서 벗어나면서 빨간줄이 사라질 것이다.


하지만, 저 코드는 런타임 오류가 발생한다.


이유는 아래와 같다.



"컴파일러에게 프로그래머가 형변환을 함으로써, 일단 데이터를 맞게 넣어준것 처럼 보여준다.


컴파일러는 문법이 맞다고 생각하여 넘어간다.


하지만, 프로그램이 실제로 동작할때, new Parent(); 인스턴스는 Child 형 데이터로 바꾸지 못한다는 것을


깨닫고, 런타임 오류를 뿜으며 프로그램이 종료된다. "



그렇다면, 왜 런타임 오류를 발생할까? 


그 이유는 JVM은 new Parent(); 인스턴스를 Child 데이터로 형변환 하려 했지만,


Child 데이터가 무엇인지 모르기 때문이다. 조금더 구체적인 이유는


Child 데이터는 만드는 프로그래머 마다 성질이 다를 것인데, 그것을 JVM 추리하지 못하기 때문이다.


이전 캐스팅 포스팅에서 나오길, 기본자료형 끼리는 추리가 가능하기 때문에,


알아서 알맞은 데이터 크기로 변환하여 넣어준다고 설명했다.


하지만, 위와 같이 참조형 데이터를 캐스팅 할때는, 


속성,성질이 정해져 있지 않은 참조형 데이터는 JVM이 알길 이 없다.


Child 데이터에 Parent 데이터를 넣는 경우는 화살표가 아래로 향하므로,


다운캐스팅이라 한다. 


위와 같은 예시에서 봤드시,


다운캐스팅은 일반적으로 성립하지 않는다. 


하지만, 다운캐스팅이 성립되는 경우가 존재한다.


아래의 예시를 보자.


Parent parent = new Child(); 


Child child = (Child)parent;


위의 예시는 다운 캐스팅이 성립되는 경우의 수이다.


왜 성립이 되는것일까?

 

parent 변수는 Parent클래스 형태의 변수지만, 


태생이 Child 인스턴스 인 데이터를 넣어주었다.


그러한 정보를 가지고 있는 parent 변수를 다시 Child 클래스형태로


다운캐스팅을 하였다.  parent변수 상태는 Parent 클래스형 상태이지만,


다운캐스팅을 해주는 경우 ( (Child)parent ) 태생이 Child 클래스 형이므로,


JVM이 parent 변수를 태생 정보인 Child 클래스 데이터 형으로 


다운캐스팅을 해줄 수 있는 것이다.




결과적으로, 다운캐스팅은 보통 성립하지 않는 문법이지만,


위와같이 업캐스팅이 선행된 경우, 다운캐스팅이 성립되는 경우가 존재한다.









'Java' 카테고리의 다른 글

JAVA - JNI 사용하기  (2) 2017.09.02
JAVA - [SWING] LinearLayout 사용하기.  (0) 2017.08.25
JAVA - HashMap key 구하기.  (1) 2016.08.25
JAVA - 변수 선언할때 m을 왜 붙일까?  (2) 2016.07.05
JAVA - UpCasting(업캐스팅)  (9) 2016.06.07

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

Buy me a coffeeBuy me a coffee

오늘은 캐스팅의 관해서 포스팅 한다. (형변환이라 부르기도 한다.)


캐스팅은 OOP(객체지향프로그래밍) 에서 매우 중요하다.


왜냐하면 캐스팅은 OOP의 다형성과 관련이 있기 때문이다.


자바를 통해서 설명하겠다. (어떤 언어든 상관없다.)


자바에서의 데이터형은 아래와 같이 크게 2가지로 나눌 수 있다. 


데이터형 : 기본형 , 참조형.


자바에서 기본형은 8가지다. ( boolean, int, short, byte,double, long, float, char ) 이다.


자바에서 참조형은 만들기 나름이지만, 예시를 들자면, 많이쓰는 String 정도가 되겠다.


캐스팅의 목적은 데이터를 바꾸는 것이 주목적이 아닌, 


코드를 적는 프로그래머가 이미 데이터 정보에 대해 이해한 가정하에, OOP의 다형성 측면에서 사용한다.


기본 데이터형에서의 캐스팅은 원칙적으로 데이터손실을 막고자 한다.


아래의 예시를 보자.


int a = 1.0; 


위의 예시는 컴파일 에러가 뜬다.


변수는 분명 int 정보만 원하고 있다. 1.0이라는 실제데이터는 int 정보를 이미 가지고 있고, 소수점을 표현하는


double형 데이터이다. 변수라는 것은 원하는 정보가 실제데이터에 있을 시, 문제 없이 받아 올 수 있다.


하지만 위의 예시는 왜 컴파일 에러가 뜰까?


답은 실제 데이터 1.0이라는 것이 a 변수에 들어 가면 1로 바뀌기 때문에 실제 데이터가 손실되는것을 막고자 하는 것이다.


하지만, 코드를 작성하는 프로그래머가 데이터가 손실된 다는 것을 이미 알고 있고 OOP의 다형성을 이용하고 싶을때는


아래와 같이 캐스팅을 하는 것이다. 


int a = (int)1.0;


실제데이터 앞에 (데이터 자료형) 을 붙여주면 캐스팅이 된다. 따라서 a 에는 1.0 대신 캐스팅된 1이 들어간다.


반대의 상황은 어떨까? 아래의 상황을 보자.


double b = 1;


위의 상황은 컴파일 에러가 뜨지 않는다. 하지만 의문을 가져야 한다.


분명 변수가 원하는정보는 더블형 데이터 자료형 이지만, 실제 데이터는 1이라는 int 자료형만 넣었다.


원칙으로는 변수가 원하는 정보를 충족하지 않을 시, 컴파일 에러가 떠야 한다.


하지만 컴파일 에러가 뜨지 않는 이유가 무엇일까?


그 이유는 기본형 끼리의 캐스팅이기 때문이다. 분명 실제 데이터는 1밖에 넣질 않았지만,


기본 자료형은 이미 컴파일러가 알고 있는 자료형이다. 따라서, 더블형 데이터의 형태를 추측으로 알 수 있는 것이다.


즉, 컴파일러가 자동적으로 더블형으로 바꿔주는 것이지, 원칙으론 안된다는 것을 알아야 한다.







실제로, 다음 포스팅할 다운캐스팅 같은 경우는 참조형 끼리의 형변환 이므로, 컴파일러는 참조형 데이터를 추리하지 못한다.


따라서, 윗 개념과 일맥상통하게 기본적으로 다운캐스팅은 성립되지 않는 개념이다. 


다음 포스팅때 업캐스팅과 다운캐스팅에 대해 그 의문을 풀어볼 것이다.



http://mommoo.tistory.com/41 - 업캐스팅

http://mommoo.tistory.com/51 - 다운캐스팅 



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

Buy me a coffeeBuy me a coffee

List와 Map의 차이 2편이다.


1편에서는 List에 대해 포스팅 했고,


오늘은 Map에 대해 포스팅한다.


아래는 1편 URL이다.


http://mommoo.tistory.com/33



Map을 이용해 저장할때는 List처럼


뭉텅이로 저장하는것이 아니라, Map에 아이템을 저장할때마다, 빈 공간을 찾아 저장한다.


따라서 List보다는 데이터 저장속도가 느릴 수 있다.  Map의 가장 큰 특징이라면,


쌍을이루는 Key와 Value값을 이용한다는 것이다.


따라서 단순한 포지션(0~10 같은 인덱션)보다는, 저장하고 싶은 데이터가 특별한 Key값을


가질때 Map을 사용하는것이 좋다. 아래의 예시는 자바언어로 작성하였다.



HashMap<String,String> hashMap = new HashMap<>();

hashMap.put("Key1" , " 키값이 Key1인 Value 입니다. ");

hashMap.put("Key2" , " 키값이 Key2인 Value 입니다. ");

hashMap.put("Key3" , " 키값이 Key3인 Value 입니다. ");

hashMap.put("Key4" , " 키값이 Key4인 Value 입니다. ");


System.out.println(hashMap.get("key1");

System.out.println(hashMap.get("key2");

System.out.println(hashMap.get("key3");

System.out.println(hashMap.get("key4");



------------- consol  -----------------


키값이 Key1인 Value 입니다.

키값이 Key2인 Value 입니다.

키값이 Key3인 Value 입니다.

키값이 Key4인 Value 입니다.


위의 예시는 key값을 String으로 데이터도 String으로 작성하였다.


만약 동일한 Key값을 사용하면 기존의 Key값을 가지고 있는 value가 사라지고


후에 저장한 valuse 값이 셋팅이 된다. key만 다르다면 value 값이 중복되도 상관 없다.


Map은 콘솔에 찍힌거와 같이 키값이 의미가 있을때 좋은 자료구조 이다.


ArrayList안에 원하는 데이터를 검색하는 경우에는 0번부터 해당 데이터가 있을때까지


검색을 해야하지만, (원하는 데이터의 index를 모르는 경우) hashMap의 경우는 


key값을 통해서 빠르게 데이터를 검색한다. 


요소의 추가 삭제는 List보다 성능이 나을때가 많다. 따라서, 검색성능은 기본적으로 Map이 좋다.



정리하자면,  Map 은빈번한 검색과, 범위데이터가 아닌 특정 데이터를 순간마다 캐치해야할 때 유리한 자료구조이다. 





'용어정리 > 프로그래밍용어' 카테고리의 다른 글

URL 이란?  (2) 2016.06.14
URI 이란?  (0) 2016.06.13
List와 Map의 차이 (1)  (0) 2016.04.26
XML 이란?  (9) 2016.01.26
상수(constant) 와 리터럴(literal)이란?  (16) 2016.01.06

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

Buy me a coffeeBuy me a coffee

+ Recent posts