1. 힙정렬의 정의


힙이란 무엇인가?  힙은 쌓아놓음. 쌓아놓은 더미의 뜻의 단어이다.


선택정렬을 응용한 알고리즘인 힙정렬은 힙의 특성을 이용해서 정렬을 수행한다.


힙은 부모의값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리이다.

이때 부모의 값이 자식보다 항상 작아도 힙이라고한다.(부모와 자식요소의 관계만 일정하면 된다)


부모와 자식관계는 항상 부모의값 >= 자식의값이다. 

따라서 힙의 가장 위쪽에 있는 루트가 가장 큰값이 된다.


힙에서 부모와 자식 관계는 일정하지만 형제사이의 대소관계는 일정하지 않다.



2. 트리의 개념


트리의 가장 윗부분을 루트(root)라고 한다. 그리고 요소의 상하관계를 부모(parent)와 자식(child)이라고 한다. 자식 간의 관계는 형제(sibling)이라고 한다.

완전이진트리란 트리의 한 종류를 말한다. 사람도 유전적인 특징에 의해 분류하는 것 처럼 트리의 종류도 여러가지다. 완전이진트리의 특징은 '완전이진' 상태라는 것이다. 여기서 '완전' 이라는 말은 부모는 자식을 왼쪽부터 추가하는 모양을 유지한다는 뜻이다. 그리고 '이진'이라는 말은 부모가 가질 수 있는 자식의 개수는 최대 2개다 라는 의미이다.


힙의 요소를 배열에 저장하는 과정은 다음 그림과 같다. 가장 위쪽부터 a[0]에 넣고 한단계 아래요소를 왼쪽부터 오른쪽으로 인덱스의 값을 1씩 늘리면서 배열의 각 요소에 힙의 요소를 대입한다.






이 과정을 거치면 부모와 자식의 인덱스 사이에 관계가 성립한다.


1. 부모는 a[(i-1)/2]

2. 왼쪽 자식은 a[i*2+1]

3. 오른쪽 자식은 a[i*2+2]


a[1] 을 저 공식에 대입해보면 부모는 a[0] 왼쪽 자식은 a[3] 8 , 오른쪽 자식은 a[4] 3 이 된다.



3. 힙정렬의 특징


가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘이다.

힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 된다.

힙정렬은 선택정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰값을 구해야 한다.

다시 말해 힙으로 구성된 10개의 요소에서 가장 큰값을 없애면 나머지 9개의 요소 중에서 가장 큰값을 루트로 정해야한다.

따라서 나머지 9개의 요소로 만든 트리도 힙의 형태를 유지할 수 있도록 재구성해야 한다.



힙에서 루트인 10을 꺼낸다. 비어있는 루트 위치로 힙의 마지막 요소(1)을 옮긴다. 이때 1 이외의 요소는 힙 상태를 유지한다.





루트로 이동시킨 1을 올바른 위치로 보내야 한다. 1의 자식은 9와 5인데 힙이 되려면 3개의 값 가운데 가장 큰값이 위쪽에 있어야 한다.

부모의 값>=자식의 값 이라는 힙의 조건을 만족하려면 두 자식을 비교하여 큰 쪽인 9 와 바꾸면 된다.

그러면 1이 왼쪽으로 내려온다.



1의 자식은 8과 3이다. 3개의 값 중 가장 큰 값이 위쪽에 있어야 하므로 8과 위치를 바꾼다.



1의 자식은 6과 7이다. 3개의 값 중 가장 큰 값이 위쪽에 있어야 하므로 7과 위치를 바꾼다.


1. 루트를 꺼낸다.

2. 마지막 요소를 루트로 이동시킨다.

3. 자기보다 큰 값을 가지는 자식요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복한다. 

이때 자식의 값이 작거나 잎에 다다르면 작업이 종료된다.


4. 힙정렬 알고리즘 흐름


1. 힙의 루트 (a[0])에 있는 가장 큰 값(10)을 꺼내 배열 마지막 요소(a[9])와 바꾼다.


2. 가장 큰 값을 a[9]로 옮기면 a[9]는 정렬을 마치게 된다. 

앞에서 살펴본 순서대로 a[0] ~ a[8] 의 요소를 힙으로 만든다. 

그 결과 두번째로 큰 요소인 9가 루트에 위치하게 된다. 

힙의 루트 a[0] 에 있는 가장 큰 값인 9를 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[8]과 바꾼다.


3. 두번쨰로 큰 값을 a[8] ~ a[9] 는 정렬을 마치게 된다. 

그런 다음 a[0] ~ a[7] 의 요소를 힙으로 만든다.

그 결과 세번째로 큰 요소인 8이 루트에 위치하게 된다. 

힙의 루트 a[0]에 있는 가장 큰 값인 8을 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[7]과 바꾼다.


 

위 설명을 그림으로 표현하면




4. 배열로 힙만들기


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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
package myTest4;
 
import java.util.Scanner;
 
// GregorianCalendar형의 배열을 정렬하는 프로그램
// 1. 자연정렬이 필요한 배열 - 요소의 대소관계를 비교하여 정렬합니다.
public class HeapSort {
    
    // 출력 space1~9 칸수 정의
    static String sp1 = " ", sp2 = "  ", sp3 = "   ";
    static String sp4 = "    ", sp5 = "     ", sp6 = "      ";
    static String sp7 = "       ", sp8 = "        ";
    static String sp9 = "        ";
    
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    static void downHeap(int[] a, int left, int right){
        int temp = a[left];    // 루트
        int child;                    // 큰 값을 가진 노드
        int parent;                // 부모
        
        for(parent = left; parent < (right + 1) / 2; parent = child){
            int cl = parent*2+1;        // 왼쪽 자식
            int cr = cl+1;                // 오른쪽 자식
            child = (cr <= right && a[cr] > a[cl]) ? cr : cl;     // 큰 값을 가진 노드를 자식에 대입
            if(temp >= a[child]){
                break;
            }
            a[parent] = a[child];
        }
        a[parent] = temp;
        
        /* 트리구조 출력하는 소스 시작 */
        int i=0;
        int arrLength  =a.length;
        int k=3;
        int m = 2, n =2;
        int nfloor = 2;
        if(arrLength  > k && arrLength  > 2){
            do{
                // 3,7, 15
                m= m*n; // m=4, m= 8
                k = k+m; // k=7, k= 15
                nfloor++;    // nfloor= 3, nfloor = 4 
            }while(arrLength  > k); // myvalue1 = 10
        }
            
        // if arrLength == 4, 5, 10, 15
        while(i< nfloor-1){ // i=0; nfloor = 4
            String lbranch = "/";
            String rbranch = "\\";
            if(i==0){ // 1층
                System.out.print(sp9+sp9+sp3);
                System.out.println(a[i]);
            }else if(i==1){
                System.out.print(sp9+sp6);
                System.out.print(lbranch);
                System.out.print(sp9+sp3);
                System.out.print(rbranch);
                System.out.println();
                System.out.println(sp9+sp5+a[i]+sp9+sp5+a[i+1]);
            }else{ // 2층, 3층, 4층
                if(nfloor == 3){
                    nfloor3(a, arrLength, lbranch, rbranch, true);
                }else if(nfloor == 4){
                    nfloor3(a, arrLength, lbranch, rbranch, false);
                    int count = arrLength - 8; // 15-7 =8 
                    // 4층 막대기 그리기
                    for(int num=0; num<=count; num++){
                        if(num % 2 == 0){
                            System.out.print(sp6);
                            System.out.print(lbranch);
                        }else{
                            System.out.print(sp3);
                            System.out.print(rbranch);
                        }
                    }
                    System.out.println();
                    
                    // 4층 숫자 출력하기
                    for(int num=8; num<=arrLength; num++){ // 10,9,5,8,3
                        if(num % 2 == 0){
                            System.out.print(sp5);
                            System.out.print(a[num-1]);
                        }else{
                            System.out.print(sp3);
                            System.out.print(a[num-1]);
                        }
                    }
                    System.out.println();
                    System.out.println();
                }
            }
            i++;
        }
        /* 트리구조 출력하는 소스 끝 */
    }
    
    private static void nfloor3(int[] a, int arrLength, String lbranch, String rbranch, boolean flag) {
        // if arrLength 4 4
        int count;
        if(arrLength <= 7){
            count = arrLength - 4;            
        }else{
            count = 3;            
            arrLength = 7;
        }
        // 3층 막대기 출력
        for(int num=0; num<=count; num++){
            if(num % 2 == 0){
                if(num==0){
                    System.out.print(sp7+sp3);
                }else{
                    System.out.print(sp9);
                }
                System.out.print(lbranch);
            }else{
                System.out.print(sp5);
                System.out.print(rbranch);
            }
        }
        System.out.println();
        
        // 3층 숫자 출력
        for(int num=4; num<=arrLength; num++){ // 10,9,5,8,3
            if(num % 2 == 0){
                if(num==4){
                    System.out.print(sp9);
                    System.out.print(a[num-1]);
                }else{
                    System.out.print(sp4);
                    System.out.print(a[num-1]);
                }
            }else{
                System.out.print(sp8);
                System.out.print(a[num-1]);
            }
        }
        if(flag){
            System.out.println();
        }
        System.out.println();
    }
 
    static void heapSort(int[] a, int n){
        for(int i=(n-1)/2; i>=0; i--){    // a[i]~a[n-1]를 힙으로 만들기
            downHeap(a, i, n-1);
        }
        for(int i=n-1; i>0; i--){
            swap(a, 0, i);        // 가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
            downHeap(a, 0, i-1);        // a[0] ~ a[i-1]을 힙으로 만듭니다.
        }
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        System.out.println("힙 정렬");
        System.out.println("요솟수: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }
        
        heapSort(x,nx);    // 배열 x를 힙 정렬합니다.
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("x[" + i + "]=" + x[i]);
        }
    }
}
cs


결과


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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
힙 정렬
요솟수: 
10
x[0]: 10
x[1]: 9
x[2]: 5
x[3]: 8
x[4]: 3
x[5]: 2
x[6]: 4
x[7]: 6
x[8]: 7
x[9]: 1
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                    9
              /           \
             8             5
          /     \        /     \
        7        3    2        4
      /   \      /
     6    1     10
 
                    8
              /           \
             7             5
          /     \        /     \
        6        3     2        4
      /   \      /
     1    9     10
 
                    7
              /           \
             6             5
          /     \        /     \
        1        3     2        4
      /   \      /
     8    9     10
 
                    6
              /           \
             4             5
          /     \        /     \
        1        3     2        7
      /   \      /
     8    9     10
 
                    5
              /           \
             4             2
          /     \        /     \
        1        3     6        7
      /   \      /
     8    9     10
 
                    4
              /           \
             3             2
          /     \        /     \
        1        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
 
오름차순으로 정렬했습니다.
x[0]=1
x[1]=2
x[2]=3
x[3]=4
x[4]=5
x[5]=6
x[6]=7
x[7]=8
x[8]=9
x[9]=10
cs


소스코드와 작업파일 첨부


myTest4.zip

181103 작업파일.pptx



'전체 > 알고리즘' 카테고리의 다른 글

병합정렬  (0) 2018.11.03
퀵정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09


1. 병합정렬


병합정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘이다.




배열 a,와 b를 비교하여 작은 값을 꺼내 c에 넣는다.



2. 두 배열을 병합하는 배열병합 코드



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
package myTest4;
 
import java.util.Scanner;
 
public class MergeArray {
    
    // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1]; 
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 정렬을 마친 배열 a,b를 병합하여 배열 c에 저장합니다.
    static void merge(int[] a, int na, int[] b, int nb, int[] c){
        int pa = 0;
        int pb = 0;
        int pc = 0;
        
        while(pa < na && pb < nb){        // 작은 값을 저장합니다.
            c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
        }
        while(pa < na){            // a에 남아있는 요소를 복사합니다.
            c[pc++] = a[pa++];
        }
        
        while(pb < nb){
            c[pc++] = b[pb++];
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int[] a = {2,4,6,8,11,13};
        int[] b = {1,2,3,4,9,16,21};
        int[] c = new int[13];
        
        System.out.println("두 배열의 병합");
        merge(a, a.length, b, b.length, c);        // 배열 a와 b를 병합하여 c에 저장
        System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
        System.out.println("배열 a:");
        for(int i=0; i< a.length; i++){
            System.out.println("a["+i+"]=" + a[i]);
        }
        System.out.println("배열 b:");
        for(int i=0; i< b.length; i++){
            System.out.println("b["+i+"]=" + b[i]);
        }
        System.out.println("배열 c:");
        for(int i=0; i< c.length; i++){
            System.out.println("c["+i+"]=" + c[i]);
        }
    }
}
cs


결과


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
두 배열의 병합
배열 a와 b를 병합하여 배열 c에 저장했습니다.
 
배열 a:
a[0]=2
a[1]=4
a[2]=6
a[3]=8
a[4]=11
a[5]=13
 
배열 b:
b[0]=1
b[1]=2
b[2]=3
b[3]=4
b[4]=9
b[5]=16
b[6]=21
 
배열 c:
c[0]=1
c[1]=2
c[2]=2
c[3]=3
c[4]=4
c[5]=4
c[6]=6
c[7]=8
c[8]=9
c[9]=11
c[10]=13
c[11]=16
c[12]=21
cs



정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬(merge sort)라고 한다.

먼저 배열을 앞부분과 뒷부분으로 나눈다.  배열의 요소 갯수가 12개 이므로 6개의 배열로 각각 나눈다.

두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬 할 수 있다.




3. 병합정렬 소스코드


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
package myTest4;
 
import java.util.Scanner;
 
public class MergeSort {
    
    static int[] buff;        // 작업용 배열
    
    // a[left] ~ a[right] 를 재귀적으로 병합 정렬
    static void __mergeSort(int[] a, int left, int right){
        if(left<right){
            int i;
            int center = (left+right) / 2;
            int p = 0;
            int j = 0;
            int k = left;
            
            __mergeSort(a, left, center);        // 배열의 앞부분을 병합 정렬합니다.
            __mergeSort(a, center+1, right); // 배열의 뒷부분을 병합 정렬합니다.
            
            for(i= left; i<=center; i++){
                buff[p++] = a[i];
            }
            
            while(i<=right && j < p){
                a[k++] = (buff[j] <= a[i])? buff[j++] : a[i++];
            }
            
            while(j<p){
                a[k++] = buff[j++];
            }
        }
    }
    
    // 병합 정렬
    static void mergeSort(int[] a, int n){
        buff = new int[n];        // 작업용 배열을 생성합니다.
        __mergeSort(a,0,n-1);    // 배열 전체를 병합 정렬합니다.
        buff = null;                    // 작업용 배열을 해제합니다.
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        
        System.out.println("병합 정렬");
        System.out.print("배열의 길이 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        for(int i=0; i< nx; i++){
            System.out.print("x[" + i + "] : ");
            x[i] = stdIn.nextInt();
        }
        
        mergeSort(x,nx);        // 배열 x를 병합 정렬합니다.
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("X[" + i + "]= " + x[i]);
        }
    }    
}
 
cs



결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
병합 정렬
배열의 길이 : 10
x[0] : 10
x[1] : 9
x[2] : 8
x[3] : 7
x[4] : 6
x[5] : 5
x[6] : 4
x[7] : 3
x[8] : 2
x[9] : 1
오름차순으로 정렬했습니다.
X[0]= 1
X[1]= 2
X[2]= 3
X[3]= 4
X[4]= 5
X[5]= 6
X[6]= 7
X[7]= 8
X[8]= 9
X[9]= 10
cs



'전체 > 알고리즘' 카테고리의 다른 글

힙정렬, 완전이진트리  (2) 2018.11.04
퀵정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09


1. 퀵정렬


퀵정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘이다.

퀵정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹 1명이 되면 정렬을 마친다.



2. 배열을 두 그룹으로 나누기 (피벗을 구하고 그룹을 나누는 과정)




그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의요소를 오른쪽으로 옮겨야 한다.


1. a[pl] >= x 가 성립하는 요소를 찾을때까지 pl을 오른쪽으로 스캔한다.

2. a[pr] <= x가 성립하는 요소를 찾을떄까지 pr을 오른쪽으로 스캔한다.


이 과정을 통해 pl과 pr이 멈추게 되고 pl이 위치한 지점은 피벗값 이상의 요소가 있는 지점이고

pr이 위치한 지점은 피벗값 이하의 요소가 있는 지점이다.


왼쪽(pl)과 오른쪽(pr) 커서가 가리키는 요소 a[pl]과 a[pr]의 값을 교환한다.

그러면 피하이하의 값은 왼쪽으로 이동하고 피벗이상의 값은 오른쪽으로 이동한다.



교환 후 다시 스캔하면 같이 멈추게된다.


교환 후 다시 스캔하면 두 커서가 교차하게 된다.


pl 과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 두그룹으로 나눠진다.



3. 피벗을 구하고 그룹을 나누는 소스코드


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
package myTest4;
 
import java.util.Scanner;
 
public class Partition {
    
    // 배열 요소 a[idx1] 과 a[idx2] 의 값을 바꾼다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 배열을 나눈다.
    static void partitionArray(int[] a, int n){
        int pl = 0;            // 왼쪽커서
        int pr = n-1;         // 오른쪽커서
        int x = a[n/2]; // 피벗(가운데 위치 값)
        // x = a[5]
        // a[0] 
        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                swap(a, pl++, pr--);
            }
        }while(pl <= pr);
        
        System.out.println("피벗의 값은 " + x + "입니다.");
        
        System.out.println("피벗 이하의 그룹");
        for(int i=0; i<= pl-1; i++){
            System.out.print(a[i] + " ");        // a[0] ~ a[pl-1]
        }
        System.out.println();
        
        if(pl > pr+ 1){
            System.out.println("피벗과 일치하는 그룹");
            for(int i= pr+1; i<=pl-1; i++){    // a[pr+1] ~ a[pl-1]
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
        
        System.out.println("피벗 이상의 그룹");
        for(int i=pr+1; i<n; i++){        // a[pr+1] ~ a[n-1]
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        System.out.println("배열을 나눕니다.");
        System.out.print("배열의 길이 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"] : ");
            x[i] = stdIn.nextInt();
        }
        partitionArray(x, nx);            // 배열 x를 나눕니다.
    }
}
cs


결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
배열을 나눕니다.
배열의 길이 : 9
x[0] : 5
x[1] : 7
x[2] : 1
x[3] : 4
x[4] : 6
x[5] : 2
x[6] : 3
x[7] : 9
x[8] : 8
피벗의 값은 6입니다.
피벗 이하의 그룹
5 3 1 4 2 
피벗 이상의 그룹
6 7 9 8 
cs



4. 퀵정렬 코드 ( 재귀, 비재귀 )


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
80
81
82
83
84
85
86
87
88
89
90
91
92
package myTest4;
 
import java.util.Scanner;
 
import myTest1.IntStack;
 
public class QuickSort {
    
    // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1]; 
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 재귀 사용 퀵정렬
    static void quickSort(int[] a, int left, int right){
        int pl = left;                    // 왼쪽 커서
        int pr = right;                // 오른쪽 커서
        int x = a[(pl+pr ) /2];    //피벗
        
        System.out.printf("a[%d]~a[%d] : {",left, right);
        for(int i = left; i<right; i++){
            System.out.printf("%d, ", a[i]);
        }
        System.out.printf("%d}\n", a[right]);
        
        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                swap(a, pl++, pr--);
            }
        }while(pl <= pr);
        
        if(left < pr) quickSort(a, left, pr);
        if( pl< right) quickSort(a, pl, right);
        
    }
    
    // 비재귀 사용 퀵정렬
    static void notRecurQuickSort(int[] a, int left, int right){
        IntStack lstack = new IntStack(right - left + 1);
        IntStack rstack = new IntStack(right - left + 1);
        
        lstack.push(left);
        rstack.push(right);
        
        while(lstack.isEmpty() != true){
            int pl = left = lstack.pop();        // 왼쪽 커서
            int pr = right = rstack.pop();     // 오른쪽 커서
            int x = a[(left + right) / 2];        // 피벗
            
            do{
                while(a[pl] < x) pl++;
                while(a[pr] > x) pr--;
                if(pl <= pr){
                    swap(a, pl++, pr--);
                }
            }while(pl <= pr);
            
            if(left < pr){
                lstack.push(left);        // 왼쪽 그룹 범위의
                rstack.push(pr);        // 인덱스를 푸시합니다.
            }
            if(pl < right){
                lstack.push(pl);            // 오른쪽 그룹 범위의
                rstack.push(right);    // 인덱스를 푸시합니다.
            }    
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        System.out.println("퀵정렬");
        System.out.print("배열의 길이 : ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"] : ");
            x[i] = scanner.nextInt();
        }
        
        quickSort(x, 0, nx-1);            
//        notRecurQuickSort(x, 0, nx-1);
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("x["+i+"]=" + x[i]);
        }
    }
}
cs


결과


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
퀵정렬
배열의 길이 : 9
x[0] : 5
x[1] : 8
x[2] : 4
x[3] : 2
x[4] : 6
x[5] : 1
x[6] : 3
x[7] : 9
x[8] : 7
a[0]~a[8] : {5, 8, 4, 2, 6, 1, 3, 9, 7}
a[0]~a[4] : {5, 3, 4, 2, 1}
a[0]~a[2] : {1, 3, 2}
a[0]~a[1] : {1, 2}
a[3]~a[4] : {4, 5}
a[5]~a[8] : {6, 8, 9, 7}
a[5]~a[6] : {6, 7}
a[7]~a[8] : {9, 8}
오름차순으로 정렬했습니다.
x[0]=1
x[1]=2
x[2]=3
x[3]=4
x[4]=5
x[5]=6
x[6]=7
x[7]=8
x[8]=9
cs


퀵정렬에서 분할과정 출력을 통해 어떻게 분할 되는지 확인 할 수 있었다.




'전체 > 알고리즘' 카테고리의 다른 글

힙정렬, 완전이진트리  (2) 2018.11.04
병합정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09


1. 쉘 정렬


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
package myTest4;
 
import java.util.Scanner;
 
public class ShellSort {
    
    static void shellSort(int[] a, int n){
        for(int h= n/2; h>0; h /= 2){
            for(int i=h; i<n; i++){
                int j;
                int tmp = a[i];
                for(j=i-h; j>= 0 && a[j] > tmp; j-= h){
                    a[j+h] = a[j];
                }
                a[j+h] = tmp;
                for(int k=0; k<n; k++){
                    System.out.print(a[k]);
                }
                System.out.println();                
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("셀 정렬(버전 1)");
        System.out.print("배열의 길이: ");
        
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        
        for(int i=0; i<arrayLength; i++){
            System.out.print("array["+i+"]:");
            array[i] = scanner.nextInt();
        }
        
        shellSort(array, arrayLength);        
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.println("array["+i+"]:" + array[i]);
        }
        System.out.println();
    }
}
cs



쉘 정렬 결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
셀 정렬(버전 1)
배열의 길이: 6
array[0]:6
array[1]:5
array[2]:4
array[3]:3
array[4]:2
array[5]:1
354621
324651
321654
231654
123654
123654
123564
123456
오름차순 정렬완료
array[0]:1
array[1]:2
array[2]:3
array[3]:4
array[4]:5
array[5]:6
cs


2. 증분값 h를 변경한 쉘정렬 


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
package myTest4;
 
import java.util.Scanner;
 
public class ShellSortChangeHvalue {
    
    static void shellSort2(int[] a, int n){
        int h;
        for( h = 1; h<n/9; h=h*3+1);
        
        for(;h>0; h/=3){
            for(int i= h; i<n; i++){
                int j;
                int tmp = a[i];
                for(j=i-h; j>=0 && a[j] > tmp; j-=h){
                    a[j+h] = a[j];
                }
                a[j+h] = tmp;
                for(int k=0; k<n; k++){
                    System.out.print(a[k]);
                }
                System.out.println();                        
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("셀 정렬(버전 2)");
        System.out.print("배열의 길이: ");
        
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        
        for(int i=0; i<arrayLength; i++){
            System.out.print("array["+i+"]:");
            array[i] = scanner.nextInt();
        }
        
        shellSort2(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.println("array["+i+"]:" + array[i]);
        }
        System.out.println();
    }
}
cs



증분값 h를 변경한 쉘정렬 결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
셀 정렬(버전 2)
배열의 길이: 6
array[0]:6
array[1]:5
array[2]:4
array[3]:3
array[4]:2
array[5]:1
564321
456321
345621
234561
123456
오름차순 정렬완료
array[0]:1
array[1]:2
array[2]:3
array[3]:4
array[4]:5
array[5]:6
cs


'전체 > 알고리즘' 카테고리의 다른 글

병합정렬  (0) 2018.11.03
퀵정렬  (0) 2018.11.03
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07



1. 단순 선택 정렬


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 myTest4;
 
import java.util.Scanner;
 
public class SimpleSelectionSort {
    
    static void selectionSort(int[] a, int n){
        for(int i=0; i<n-1; i++){ 
            int min = i ;    // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록 min = 0
            for(int j = i+1; j < n; j++){ 
                if(a[j] < a[min]){ 
                    min = j ;
                }
            }
            swap(a, i, min);
        }
    }
    
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            System.out.print(array[i]);
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
    }    
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        selectionSort(array, arrayLength);    
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs



단순 선택 정렬결과


1
2
3
4
5
6
7
8
9
10
11
12
배열의 길이: 5
array[0] :5
array[1] :4
array[2] :3
array[3] :2
array[4] :1
54321
14325
12345
12345
오름차순 정렬완료
12345
cs



2. 단순 삽입 정렬


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
package myTest4;
 
import java.util.Scanner;
 
public class SimpleInsertSort {
    
    static void insertionsort(int[] a, int n){
        for(int i=1; i<n; i++){
            int j;
            int tmp = a[i];
            for(j=i; j>0 && a[j-1] > tmp; j--){
                a[j] = a[j-1];
            }
            a[j] = tmp;
            for(int k=0; k<n; k++){
                System.out.print(a[k]);
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        insertionsort(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs



단순 삽입 정렬결과


1
2
3
4
5
6
7
8
9
10
11
12
배열의 길이: 5
array[0] :5
array[1] :4
array[2] :3
array[3] :2
array[4] :1
45321
34521
23451
12345
오름차순 정렬완료
12345
cs



'전체 > 알고리즘' 카테고리의 다른 글

퀵정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07
재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07


1. 정렬이란?


정렬은 이름, 학번, 키 등 핵심 항목의 대소관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말함.

정렬 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할수 있음.


키 값이 작은데이터를 앞으로 놓으면 오름차순(ascending order) 정렬

키 값이 큰 데이터를 앞으로 놓으면 내림차순(descending order) 정렬


내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘

외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘


졍렬 알고리즘의 핵심 요소 : 교환, 선택, 삽입



2. 버블정렬


이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다.


요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음으로 이동함.

이런 일련의 과정(비교, 교환 작업)을 패스(pass)라고 함.


모든 정렬이 끝나면 n-1회의 패스가 수행되어야 함.


1. 버블정렬 방법 1


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
package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
 
    }
    
    // 6 4 3 7 1 9 8
    static void bubbleSort(int[] array, int arrayLength){
        for(int i=0; i< arrayLength-1; i++){ 
            System.out.println("패스" + i);
            for(int j=arrayLength-1; j>i; j--){    
                if(array[j-1] > array[j]){ // 앞의 요소가 뒤의 요소보다 크다면
                    swap(array, j-1, j);
                }else{ // 앞의 요소가 뒤의 요소보다 작다면
                    for(int k=0; k<array.length; k++){
                        if(j-1 == k){
                            System.out.print(array[k]+"-");
                        }else{
                            System.out.print(array[k]);
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("패스"+i+" 정렬결과 ");
            for(int l=0; l<array.length; l++){
                System.out.print(array[l]);
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 1");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs



결과1


버블 정렬 방법 1
배열의 길이: 7
array[0] :6
array[1] :4
array[2] :3
array[3] :7
array[4] :1
array[5] :9
array[6] :8
패스0
643719+8
64371-89
6437+189
643+1789
64+13789
6+143789
패스0 정렬결과 
1643789
패스1
164378-9
16437-89
1643-789
164+3789
16+34789
패스1 정렬결과 
1364789
패스2
136478-9
13647-89
1364-789
136+4789
패스2 정렬결과 
1346789
패스3
134678-9
13467-89
1346-789
패스3 정렬결과 
1346789
패스4
134678-9
13467-89
패스4 정렬결과 
1346789
패스5
134678-9
패스5 정렬결과 
1346789
오름차순 정렬완료
1346789
cs



2. 정렬 된 상태가 있는 요소가 있을때 교환횟수 기록하는 버블 정렬 방법 2


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
package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort2 {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
        if(idx1 == 0){
            for(int i=0; i<array.length; i++){
                System.out.print(array[i]);
            }
            System.out.println();
        }
    }
    
    // 정렬된 상태에서 교환횟수 기록
    static void bubbleSort2(int[] array, int arrayLength){
        for(int i=0; i<arrayLength-1; i++){
            int exchg = 0;                    // 패스의 교환 횟수를 기록합니다.
            System.out.println("패스" + i);
            for(int j=arrayLength-1; j>i; j--){
                if(array[j-1] > array[j]){
                    swap(array, j-1, j);
                    exchg++;
                }else{ // 앞의 요소가 뒤의 요소보다 작다면
                    for(int k=0; k<array.length; k++){
                        if(j-1 == k){
                            System.out.print(array[k]+"-");
                        }else{
                            System.out.print(array[k]);
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("교환횟수: "+exchg);
            if(exchg == 0) break;        // 교환이 이루어지지 않으면 종료한다.
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 2");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort2(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs


결과2


버블 정렬 방법 2
배열의 길이: 7
array[0] :1
array[1] :3
array[2] :9
array[3] :4
array[4] :7
array[5] :8
array[6] :6
패스0
139478+6
13947+68
1394-678
139+4678
13-49678
1-349678
교환횟수: 3
패스1
134967-8
13496-78
1349+678
134-6978
13-46978
교환횟수: 1
패스2
134697-8
13469+78
1346-798
134-6798
교환횟수: 1
패스3
134679+8
13467-89
1346-789
교환횟수: 1
패스4
134678-9
13467-89
교환횟수: 0
오름차순 정렬완료
1346789
cs


3. 정렬된 요소를 제외하고 정렬해야 하는 위치를 last로 저장하는 버블정렬 방법 3


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 myTest3;
 
import java.util.Scanner;
 
public class BubbleSort3 {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
        if(idx1 == 0){
            for(int i=0; i<array.length; i++){
                System.out.print(array[i]);
            }
            System.out.println();
        }
    }
    
    // 앞에 3개의 요소가 정렬된 1 3 9 4 7 8 6 인 배열이 있다고 하면
    // 3개의 요소를 제외한 4개의 요소에 대해 비교 교환을 수행해야 한다.
    // 교환을 수행할 때마다 오른족 요소의 인덱스 값을 last에 저장함.
    static void bubbleSort3(int[] array, int arrayLength){
        int k=0;
        while(k<arrayLength-1){ // 0<6 , 3<6, 4<6
            int last = arrayLength-1; // last = 6
            for(int j= arrayLength-1; j>k; j--){ // j=6, 6>0 // j=6, 6>3
                if(array[j-1] > array[j]){ // array[5] > array[6]
                    swap(array, j-1, j);
                    last = j; // last = 3 // last = 4 // last = 5 // last = 6
                }
            }
            k = last; // k=3 // k= 4 // k=5 // k=6
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 3");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort3(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs


결과3


버블 정렬 방법 3
배열의 길이: 7
array[0] :1
array[1] :3
array[2] :4
array[3] :9
array[4] :6
array[5] :7
array[6] :8
1349+678
13469+78
134679+8
오름차순 정렬완료
1346789
cs


4.  홀수번째 패스는 가장 작은 요소를 맨 앞으로 옮기고 

짝수번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식 사용한 버블정렬


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
80
81
82
83
84
85
86
87
88
package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort4 {
    
    static void swap1(int[] array, int idx1, int idx2){ // j, j+1
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx2];
        array[idx2] = array[idx1];
        array[idx1] = t;        
    }
 
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap2(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
    }
    // 8 9 1 3 4 5 6
    // 1 3 4 8 7 9 2
    // 9 1 3 4 6 7 8 배열이 있다면
    // 두번째 요소부터 정렬되어있지만 bubbleSort3 메소드 사용시 빠른시간안에 정렬작업을 할수 없음.
    // 맨 앞에 있는 요소의 값(9)는 1회의 패스를 거쳐도 한칸씩만 뒤로 옮겨지기 때문
    // 홀수 번째 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식 사용
    // 칵테일 정렬, 쉐이커 정렬
    static void bubbleSort4(int[] array, int arrayLength){
        int k=0;
        int pathCount = 0;
        while(k<arrayLength-1){ // 0<6 , 3<6, 4<6
            int last = arrayLength-1; // last = 6W
            if(k%2 == 0){ // 짝수
                pathCount++;
                System.out.println("짝수패스" + pathCount);
                for(int j= 0; j<arrayLength-1; j++){ // 5 6
                    if(array[j] > array[j+1]){ // array[0] > array[1]
                        swap1(array, j, j+1);
                        last = 1;
                    }
                }
            }else{    // 홀수
                pathCount++;
                System.out.println("홀수패스" + pathCount);
                for(int j= arrayLength-1; j>=k; j--){ // j=6, 6>1; j--;
                    if(array[j-1] > array[j]){ // array[5] > array[6]
                        swap2(array, j-1, j);
                        last = 0; 
                    }
                }
            }            
            k = last; // k=3 // k= 4 // k=5 // k=6
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 4");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort4(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs


결과4


버블 정렬 방법 4
배열의 길이: 7
array[0] :8
array[1] :9
array[2] :1
array[3] :3
array[4] :4
array[5] :5
array[6] :6
짝수패스1
89+13456
819+3456
8139+456
81349+56
813459+6
홀수패스2
8+134569
짝수패스3
18+34569
138+4569
1348+569
13458+69
홀수패스4
오름차순 정렬완료
1345689
cs




'전체 > 알고리즘' 카테고리의 다른 글

쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07
재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07
배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07


8퀸 문제란?


- 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓아라.


퀸 배치하기


8개의 퀸을 배치하는 조합은 

체스판은 64칸(8x8)이므로 처음에 퀸을 1개 배치할 떄는 64칸 중 아무 곳이나 선택할 수 있다.

다음 퀸을 배치할 때는 나머지 63칸에서 임의로 선택한다.


마찬가지로 8번째까지 생각하면 다음과 같이


64x63x62x61x60x59x58x57 = 178,462,987,637,760 가지 조합이 만들어짐.


8퀸문제의 조건을 만족하는지 조사 불가..


퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로 아래와 같은 규칙을 세울수 있다.


규칙 1. 각 열에 퀸을 1개만 배치한다.


퀸을 배치하는 조합의 수는 많이 줄어든다.

8*8*8*8*8*8*8*8 = 16,777,216 이다.


같은행에 퀸이 2개 이상 배치되면 안된다.


규칙 2. 각 행에 퀸을 1개만 배치한다.


이렇게 하면 조합의 개수가 줄어든다.



1. 가지뻗기를 하며 재귀적으로 각 열에 1개의 퀸을 배치하는 조합을 나열


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
package myTest2;
 
public class QuuenB {
    // 가지뻗기
    // 규칙 1. 각 열에 퀸을 1개만 배치한다.
    // 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열
    static int[] pos = new int[8];    // 각 열의 퀸의 위치
    
    // 각 열의 퀸의 위치를 출력한다.
    static void print(){
        for(int i=0; i<8; i++){
            System.out.printf("%2d",pos[i]);
        }
        System.out.println();
    }
    
    static void set(int i){
        for(int j=0; j<8; j++){
            // pos[0] = 0
            pos[i] = j;        // 퀸을 j행에 배치한다.
            if(i==7){        // 모든 열에 배치한다.
                print();
            }else{
                set(i+1);    // 다음 열에 퀸을 배치한다.
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);        // 0열에 퀸을 배치한다.
    }
}
cs



결과



가장 마지막에 7 7 7 7 7 7 7 7 모든 퀸이 7행에 배치된 것을 확인할 수 있다.



2. 분기한정법을 사용하여 각 행, 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열


가지뻗기로 퀸을 배치하는 조합을 나열할 수 있지만 8퀸 문제 답을 얻을 수 없다.


규칙 2. 각 행에 퀸을 1개만 배치한다.


규칙 2를 적용해 다시 구현


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
package myTest2;
 
public class QuuenBB {
    // 분기 한정법
    // 규칙 1. 각 열에 퀸을 1개만 배치한다.
    // 규칙 2. 각 행에 퀸을 1개만 배치한다.
    static boolean[] flag = new boolean[8];    // 각 행에 퀸을 배치했는지 체크
    static int[] pos = new int[8];                        // 각 열의 퀸의 위치
    
    // 각 열의 퀸의 위치를 출력함.
    static void print(){
        for(int i=0; i<8; i++){
            System.out.printf("%2d", pos[i]);
        }
        System.out.println();
    }
    
    // i열에 알맞은 위치에 퀸을 배치한다.
    static void set(int i){
        for(int j = 0; j < 8; j++){
            if(flag[j] == false){    // j행에는 퀸을 아직 배치하지 않았다면
                pos[i] = j;                // 퀸을 j행에 배치한다.
                if( i== 7){            // 모든 열에 배치한 경우
                    print();
                }else{
                    flag[j] = true;
                    set(i+1);
                    flag[j] = false;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);        // 0열에 퀸을 배치한다.
    }
}
cs



결과



flag를 사용하여 같은행에 중복하여 퀸이 배치되는 것을 방지한다.

j행에 퀸을 배치하면 true 배치되지 않는 다면 false이다.


3. 8퀸 문제 구현


퀸이 행방향과 열방향으로 서로 겹치지지 않는 조합을 나열했지만

퀸은 대각선 방향으로도 이동할 수 있기 때문에 어떤 대각선에서 보더라도 퀸을 1개만 배치하는 한정조작을 추가해야한다.


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
package myTest2;
 
public class EightQueen {
 
    static boolean[] flag_a = new boolean[8];    // 각 행에 퀸을 배치했는지 체크
    static boolean[] flag_b = new boolean[15];    //  ↗ 대각선 방향으로 퀸을 배치했는지 체크
    static boolean[] flag_c = new boolean[15];    //  ↘ 대각선 방향으로 퀸을 배치했는지 체크
    static int[] pos = new int[8];
    
    // 각 열의 퀸의 위치를 출력
    static void print(){
        StringBuilder oneLine0 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine1 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine2 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine3 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine4 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine5 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine6 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine7 = new StringBuilder("□□□□□□□□");
        
        for(int i=0; i<8; i++){
            
            System.out.printf("%2d", pos[i]);
            int value1 = pos[i]; // 4 
            if(value1 == 0){
                oneLine0.setCharAt(i, '■');
            }else if(value1 == 1){
                oneLine1.setCharAt(i, '■');
            }else if(value1 == 2){
                oneLine2.setCharAt(i, '■');
            }else if(value1 == 3){
                oneLine3.setCharAt(i, '■');
            }else if(value1 == 4){
                oneLine4.setCharAt(i, '■');
            }else if(value1 == 5){
                oneLine5.setCharAt(i, '■');
            }else if(value1 == 6){
                oneLine6.setCharAt(i, '■');
            }else if(value1 == 7){
                oneLine7.setCharAt(i, '■');
            }
        }
        System.out.println();
        String whole = oneLine0 +"\n" + oneLine1 +"\n" + 
                               oneLine2 +"\n" + oneLine3 +"\n" + 
                               oneLine4 +"\n" + oneLine5 +"\n" + 
                               oneLine6 +"\n" + oneLine7 +"\n"; 
        System.out.println(whole);
        System.out.println();
    }
    
    // i열에 알맞은 위치에 퀸을 배치
    static void set(int i){
        for(int j=0; j<8; j++){
            if(flag_a[j] == false                     // 가로(j행)에 아직 배치하지 않았습니다.
                    && flag_b[i+j] == false         // 대각선 ↗에 아직 배치하지 않았습니다.
                    && flag_c[i-j+7] == false){    // 대각선 ↘에 아직 배치하지 않았습니다.
                pos[i] = j;
                if(i == 7){
                    print();
                }else{
                    flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = true;
                    set(i+1);
                    flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = false;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);
    }
}
cs



결과



flag_b, flag_c 로 방향대각선을 체크하는 배열로 

각각의 대각선 방향에 대해 퀸이 배치되었을 때 체크 하는 배열 인덱스는 flag_b[ i+j ] flag_c[ i-j+7 ] 이다.



소스코드 첨부


myTest1.zip






'전체 > 알고리즘' 카테고리의 다른 글

단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09
재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07
배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07
스택 알고리즘 구현  (0) 2018.10.03


재귀


어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될때 재귀적(recursive)이라고 한다.


1은 자연수, 

자연수 n의 바로 다음수도 자연수


재귀적 정의에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의할수 있다.

재귀를 효과적으로 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 할 수 있다.



1. 재귀 메소드 사용, 미사용 팩토리얼 값 구하기



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
package myTest2;
 
import java.util.Scanner;
 
public class Factorial {
    // 팩토리얼을 재귀적으로 구현
    // 재귀 메서드를 사용하여 양의 정수 n의 팩토리얼을 반환한다.
    static int factorial(int n){
        if(n>0) return n * factorial(n-1);
        else return 1;
    }
    
    // 자기 자신을 부르지 않고 구현한 메서드
    static int notUsingRecursive(int n){
        if(n>0){
            int value = 1;
            for(int i=n; i>0; i--){ 
                value = value * i; 
            }
            return value;
        }else{
            return 1;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("정수를 입력하세요: ");
        int x = scanner.nextInt();
        System.out.println(x+ "의 팩토리얼은 " + factorial(x) + "입니다.");
        System.out.println(x+ "의 재귀메서드 사용안한 메서드는 " + notUsingRecursive(x) + "입니다.");
    }
}
cs


결과



2. 유클리드 호제법을 사용하여 두 정수의 최대공약수를 재귀적으로 구하는 방법



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
package myTest2;
 
import java.util.Scanner;
 
public class EuclidGCD {
    // 재귀를 사용하여 정수 x,y 의 최대공약수 반환
    static int gcd(int x, int y){ 
        if(y == 0) return x;
        else return gcd(y, x%y);
    }
    
    // 재귀를 사용하지 않고 정수 x,y 의 최대공약수 반환
    static int notUsingRecursive(int x, int y){
        if(y == 0) {
            return x;
        }else { 
            int value1 = y; 
            int value2 = y ;
            y = x % y;    
            while(y!=0){
                value2 = y; 
                y = value1 % value2; 
                value1 = value2;
            }
            return value2;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("두 정수의 최대공약수를 구합니다.");
        System.out.print("정수를 입력하세요 : ");    int x = scanner.nextInt();
        System.out.print("정수를 입력하세요 : ");    int y = scanner.nextInt();
 
        System.out.println("최대공약수는" + gcd(x,y) + "입니다.");
        System.out.println("최대공약수는" + notUsingRecursive(x,y) + "입니다.");
    }
}
cs


재귀를 사용하지 않고 정수 x,y 의 최대공약수 반환메소드, 재귀를 사용한 메소드를 구현하였다.


결과



3. 재귀를 사용한 하노이의 탑 구현



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
package myTest2;
 
import java.util.Scanner;
 
public class Hanoi {
    
    // 재귀함수
    static void move(int no, int x, int y){
        
        if(no > 1){
            move(no-1, x, 6-x-y);
        }
        
        String stringX = "";
        String stringY = "";
        if(x==1) stringX = "A";
        if(y==1) stringY = "A";
        if(x==2) stringX = "B";
        if(y==2) stringY = "B";
        if(x==3) stringX = "C";
        if(y==3) stringY = "C";
        
        System.out.println("원반[" + no + "]을" + stringX + "기둥에서 " + stringY + "기둥으로 옮김");
        if(no > 1){
            move(no-1, 6- x-y, y);
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("하노이의 탑");
        System.out.println("원반 개수 : ");
        int n = scanner.nextInt();
        move(n, 1, 3);    // 1번 기둥의 n개의 원반을 3번 기둥으로 옮김
    }
}
cs


결과




소스 코드


myTest1.zip




'전체 > 알고리즘' 카테고리의 다른 글

버블정렬 여러가지 방법 구현  (0) 2018.10.09
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07
배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07
스택 알고리즘 구현  (0) 2018.10.03
이진검색 알고리즘 (구현 메소드 사용, Arrays.binarySearch 라이브러리 사용)  (0) 2018.10.03

+ Recent posts

티스토리툴바