190520_Day28 정렬

---

190520_Day28

//InQueueTest
package com.encore.j0517;

import java.util.Scanner;

public class IntQueueTester {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        IntQueue s = new IntQueue(64);    // 최대 64개를 인큐할 수 있는 큐

        while (true) {
            System.out.println("현재 데이터 수：" + s.size() + " / "
                                                              + s.capacity());
            System.out.print("1.인큐　2.디큐　3.피크　4.덤프　0.종료：");

            int menu = scan.nextInt();
            if (menu == 0) break;

            int x;
            switch (menu) {
             case 1:                             // 인큐
                System.out.print("데이터：");
                x = scan.nextInt();
                try {
                    s.enque(x);
                 } catch (IntQueue.OverflowIntQueueException e) {
                    System.out.println("큐가 가득 찼습니다.");
                }
                break;

             case 2:                             // 디큐
                try {
                     x = s.deque();
                    System.out.println("디큐한 데이터는 " + x + "입니다.");
                 } catch (IntQueue.EmptyIntQueueException e) {
                    System.out.println("큐가 비어 있습니다.");
                }
                break;

             case 3:                             // 피크
                try {
                     x = s.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                 } catch (IntQueue.EmptyIntQueueException e) {
                    System.out.println("큐가 비어 있습니다.");
                }
                break;

             case 4:                             // 덤프
                s.dump();
                break;
            }
        }
    }
}

//InQueue
package com.encore.j0517;

//정수 데이터를 담는 큐
public class IntQueue {
    private int max;            // 큐의 용량
    private int front;            // 첫 번째 요소 커서
    private int rear;            // 마지막 요소 커서
    private int num;            // 현재 데이터 수
    private int[] que;            // 큐 본체

    // 실행 시 예외：큐가 비어 있음
    public class EmptyIntQueueException extends RuntimeException {
        public EmptyIntQueueException() { }
    }

    // 실행 시 예외：큐가 가득 참
    public class OverflowIntQueueException extends RuntimeException {
        public OverflowIntQueueException() { }
    }

    // 생성자
    public IntQueue(int capacity) {
        num = front = rear = 0;
        max = capacity;
        try {
            que = new int[max];                // 큐 본체용 배열을  생성
        } catch (OutOfMemoryError e) {        // 생성할 수 없음
            max = 0;
        }
    }

    // 큐에 데이터를 인큐
    public int enque(int x) throws OverflowIntQueueException {
        if (num >= max)
            throw new OverflowIntQueueException();            // 큐가 가득 참
        que[rear++] = x;
        num++;
        if (rear == max)
            rear = 0;
        return x;
    }

    // 큐에서 데이터를 디큐
    public int deque() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();                // 큐가 비어 있음
        int x = que[front++];
        num--;
        if (front == max)
            front = 0;
        return x;
    }

    // 큐에서 데이터를 피크 (프런트 데이터를 들여다봄)
    public int peek() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();                // 큐가 비어 있음
        return que[front];
    }

    // 큐에서 x를 검색하여 인덱스(찾지 못하면 -1)를 반환
    public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % max;
            if (que[idx] == x)                                // 검색 성공
                return idx;
        }
        return -1;                                            // 검색 실패
    }

    // 큐를 비움
    public void clear() {
        num = front = rear = 0;
    }

    // 큐의 용량을 반환
    public int capacity() {
        return max;
    }

    // 큐에 쌓여 있는 데이터 수를 반환
    public int size() {
        return num;
    }

    // 큐가 비어 있나요?
    public boolean isEmpty() {
        return num <= 0;
    }

    // 큐가 가득 찼나요?
    public boolean isFull() {
        return num >= max;
    }

    // 큐 안의 모든 데이터를 프런트 → 리어 순으로 출력
    public void dump() {
        if (num <= 0)
            System.out.println("큐가 비어 있습니다.");
        else {
            for (int i = 0; i < num; i++)
                System.out.print(que[(i + front) % max] + " ");
            System.out.println();
        }
    }
}

• 덤프는 데이터가 들어가 있는 공간~! (전체가 아닌 공간 안에 데이터가 있는 공간만!)

• throw 는 return과 같음, 던지는 값이 Exception이란걸 보여주는 것

---

재귀(recursive)

• 어떤 사건이 자기 자신 포함, 다시 자기 자신을 사용하여 정의

• 메소드 내에서 자기메소드 호출

• 프로그램을 간결하게(가독성을 이야기 하는것이 아님) , 코드라인 수를 줄일 수 있다.

• 중요) 인자와 리턴이 명확하지 않으면 잘못된 결과, 또는 무한 반복(명확해야함!)

• 종료조건을 넣어주어야 한다!

• int gildong(int x)
  {
      gildong();
  }

• public class RecursiveTest {
  
  

  int count=1;
  void gildong() {
      System.out.println("동에번쩍 서에번쩍~!!");
      if(count >= 10)return; //종료조건!!

      count++;

      gildong();//재귀호출!!  : 끝나는 조건이 없다면 StackOverflowError발생!!
  }

  public static void main(String[] args) {
      RecursiveTest rt = new RecursiveTest();
      rt.gildong();
  }

}

  팩토리얼

- 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한것
- n = 3 , n! = 3 * 2 * 1
- 0! = 1 ,  n! = n * (n-1)

```java
package j0520;

import java.util.Scanner;

public class FactorialTest
{
    int factorial(int n)
    {
        if(n>0)
            return n * factorial(n-1); // 재귀호출
        else
            return 1; // 종료조건 (되돌아오기 기능)
    }//factorial


    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("1 이상의 정수 입력하세요");
            int n = sc.nextInt(10);
        FactorialTest ft = new FactorialTest();
            System.out.println( n + "의 팩토리얼 값은 " + ft.factorial(n) + "입니다.");
    }
}

//MyThrowDefine Test
package j0520;


class A
{
    void hello(String name)
    {
        if(name == null)
        {
        throw new NullPointerException(); // 강제 예외발생, void반환형에서는 return문과 같이 메소드를 제어
        }
        System.out.println("안녕, " + name);

    }
}
class My
{
    A a;
    public My()
    {
    A a = new A();
    }


    void callTest(String name)
    {
        try
        {
            a.hello(name);
        }catch (NullPointerException e) {
            System.out.println("이름 값을 전달하세요");
        }
    }
}
public class MyThrowDefineTest
{
    public static void main(String[] args)
    {
        My m = new My();
        String str = null;

        if(str == null)
        {
            System.out.println("#반드시 이름을 입력하세요");
            return;
        }
        m.callTest(str);
    }
}

//하노이

public class HanoiTest {
/*

<중간(값)수 구하기>
 - 조건 : 규칙적인(일정한) 수의 나열

 예)   1 2 3 의 중간값  : 2
     -------
     전체총합: 6
     왼쪽     : 1
     오른쪽  : 3   ===> 6-1-3  : 2

     4 5 6 7 8
     ---------
     전체총합: 30
     왼쪽     : 9
    오른쪽   : 15    ===> 30-9-15: 6 


move (3, 1, 3)     {1,2,3}원반을 1막대  ---> 3막대

     move(2, 1, 2)   {1,2}원반을 1막대  ---> 2막대
          move(1,1,3)   {1}원반을 1막대 --->  3막대  
              >>>  if문 false
                       >>>★  1       1 ------> 3
              >>>  if문 false
                       >>>★ 2            1 ------> 2    
          move(1,3,2)   {1}원반을 3막대 ---> 2막대
              >>>  if문 false
                       >>>★  1       3 ------> 2
              >>>  if문 false
     -----------------------------------------------
      >>>★ 3                 1 ------> 3
     -----------------------------------------------

     move(2, 2, 3) 
          move(1, 2, 1)
              >>> if문 false
                       >>>★ 1        2 ------> 1 
              >>> if문 false
                >>> ★2            2 ------> 3
          move(1, 1, 3)
              >>> if문 false
                       >>>★ 1        1 ------> 3
              >>> if문 false


*/    
    void move(int no, int x, int y) {
        //no:이동할 원반(원반갯수)  ,  x: 좌측기둥(막대)   , y: 우측기둥(막대)

        if(no>1)
            move(no-1, x,  6-x-y);

        System.out.println("["+no+"원반 옮기기]>> ["+x+"]번기둥 ----> ["+y+"]번기둥");

        if(no>1)
            move(no-1, 6-x-y, y);
              //  2, 2, 3
    }//move

    public static void main(String[] args) {
         HanoiTest ht = new HanoiTest();
         ht.move(5, 1, 3);//원반 3개를   1번막대에서 3번막대로 이동!!
    }

}

단순 삽입 정렬

• 선택요소 : 2번째 요소부터 선택 1씩 증가
• 선택요소를 그보다 더 앞쪽 알맞은 위치에 삽입하는 작업을 반복

선택정렬

import java.util.Scanner;

public class SelectionSortTest {
    void swap(int[]a, int idx1, int idx2) {//배열의 데이터 교환
        int temp = a[idx1];
        a[idx1]= a[idx2];
        a[idx2]= temp;
    }//swap    

   void selectionSort(int[]a, int n){
       for(int i=0; i<n-1; i++) {//
           int min=i;//min인덱스                                    0 , 1, 2, 3 (맨앞번지를 최소값이라고 간주)
           for(int j=i+1; j<n; j++) {//최소값 구하기  j= 1 , 2, 3, 4
             //[23,12,9,8,10]
             // 0   1 2 3  4
               if(a[j] < a[min]) {//기준최소값 보다 작은 값을 발견시
                   min = j;
               }
           }
           swap(a,i,min);
           //[8,12,9,23,10]
          //  0  1 2  3  4
       }
   }//selectionSort

   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);    

       System.out.println("==선택정렬==");
       System.out.print("요소수: ");
       int num = scan.nextInt();
       int []array = new int[num];

       for (int i = 0; i < array.length; i++) {
           System.out.print("array["+i+"]:");
           array[i]= scan.nextInt();
       }

       SelectionSortTest sst= new SelectionSortTest();
          sst.selectionSort(array, num);
       System.out.println("===== 선택정렬 후 결과 =====");
       for (int i = 0; i < array.length; i++) {
          System.out.println("array["+i+"]="+ array[i]);
       }    
   }
}

버블정렬

import java.util.Scanner;

public class BubbleSortTest {

/*

     int[] arr =   8   1   3   4   5   6   2
       인덱스        :  [0] [1] [2] [3] [4] [5] [6]





     int[] arr =   1   3   6   4   7   8   9
       인덱스        :  [0] [1] [2] [3] [4] [5] [6] 
                                      -------
                                  -------
                              -------
                          -------
                           4   6
                       ------
                  -------
    1회전 결과)     1   3   4   6   7   8   9
                                     ------
                                 ------
                             ------
                         -------
                     -------                                                        
    2회전 결과)     1   3   4   6   7   8   9   ===> 교환이 한번도 실행하지 않음!!


*/


    void swap(int[]a, int idx1, int idx2) {//배열의 데이터 교환
        int temp = a[idx1];
        a[idx1]= a[idx2];
        a[idx2]= temp;
    }//swap

    void bubbleSort(int[]a, int n) {
        int cnt=0;
        for(int i=0; i<n-1; i++) {//비교할 왼쪽 데이터, 정렬된 데이터(아래 for문을 1회 반복할때마다 최소값을 저장) 

            for(int j=n-1;  j>i; j--) {
            //비교할 오른쪽 데이터 [끝번지:(끝번지-1)], [(끝번지-1):(끝번지-2)]

                //비교횟수
                cnt++;
                if(a[j-1] > a[j]) {//오름차순의 경우
                    swap(a, j-1,  j);
                }
            }

        }
        System.out.println("비교횟수==>"+ cnt);
    }//bubbleSort



    public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);    

       System.out.println("==버블정렬==");
       System.out.print("요소수: ");
       int num = scan.nextInt();
       int []array = new int[num];

       for (int i = 0; i < array.length; i++) {
           System.out.print("array["+i+"]:");
           array[i]= scan.nextInt();
       }

       BubbleSortTest bst = new BubbleSortTest();
         bst.bubbleSort(array, num);
       System.out.println("===== 버블정렬 후 결과 =====");
       for (int i = 0; i < array.length; i++) {
          System.out.println("array["+i+"]="+ array[i]);
       }
    }//main
}

버블정렬

import java.util.Scanner;

public class BubbleSortTest2 {

/*

     int[] arr =   8   1   3   4   5   6   2
       인덱스        :  [0] [1] [2] [3] [4] [5] [6]





     int[] arr =   1   3   6   4   7   8   9
       인덱스        :  [0] [1] [2] [3] [4] [5] [6] 
                                      -------
                                  -------
                              -------
                          -------
                           4   6
                       ------
                  -------
    1회전 결과)     1   3   4   6   7   8   9     : exchg ==> 1
                                     ------
                                 ------
                             ------
                         -------
                     -------                                                        
    2회전 결과)     1   3   4   6   7   8   9   ===> 교환이 한번도 실행하지 않음!!
                                                 : exchg ==> 0

*/


    void swap(int[]a, int idx1, int idx2) {//배열의 데이터 교환
        int temp = a[idx1];
        a[idx1]= a[idx2];
        a[idx2]= temp;
    }//swap

    void bubbleSort(int[]a, int n) {
        int cnt=0;
        for(int i=0; i<n-1; i++) {//비교할 왼쪽 데이터, 정렬된 데이터(아래 for문을 1회 반복할때마다 최소값을 저장) 


            int exchg = 0;//교환0번
            for(int j=n-1;  j>i; j--) {
            //비교할 오른쪽 데이터 [끝번지:(끝번지-1)], [(끝번지-1):(끝번지-2)]

                //비교횟수
                cnt++;
                if(a[j-1] > a[j]) {//오름차순의 경우
                    exchg++;        
                    swap(a, j-1,  j);
                }
            }//안쪽for
            if(exchg==0)break;  //이미 정렬이 되어있다면

        }//바깥for

        System.out.println("비교횟수==>"+ cnt);
    }//bubbleSort



    public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);    

       System.out.println("==버블정렬==");
       System.out.print("요소수: ");
       int num = scan.nextInt();
       int []array = new int[num];

       for (int i = 0; i < array.length; i++) {
           System.out.print("array["+i+"]:");
           array[i]= scan.nextInt();
       }

       BubbleSortTest2 bst = new BubbleSortTest2();
         bst.bubbleSort(array, num);
       System.out.println("===== 버블정렬 후 결과 =====");
       for (int i = 0; i < array.length; i++) {
          System.out.println("array["+i+"]="+ array[i]);
       }
    }//main
}

Exception 위에는 Throwable이 있음
프로그램적으로 고칠 수 없는 것 : error
프로그램 실행 중 예기치 못한 경우 : Exception

RuntimeException 이 0으로 나눌때의 발생( int a = b/c; 에서 발생하는 ) 하는 ArrayIndexOutOfBoundsException의 부모임.