#14. 5주차 과제 1 [Chap06_6-1 ~ 6-3]

스터디를 중도 하차 했다.

국비과정을 수료하며 각양각색의 언어를 1주일 단위로 소화하고 있는 내게

DoIt이 제시하는 자료구조 알고리즘까지 소화할 자신이 없었기 때문이다.

 

중도하차라니... 첫째 스터디원 분들께 무척 죄송하고,

둘째 스스로의 역량을 잘못판단했다는 씁쓸함이 느껴진다. 

 

물론 기본적인 알고리즘에 대한 이해를 쌓는 일은 중요하다.

다만, 개발자 입문을 준비하는 내게는 현업에서 쓰일 Spring + Front단 언어들(css, js 등)의

숙련도를 올리는 것이 더 필요한 일이라고 결정했다.

 

하지만 이왕 펼친 책이니 천천히라도 하던 것처럼 책에 있는 코드 업로드를 할 예정이다. 

 

6챕터는 '정렬'에 관한 내용이다.

 

---

6-1. (BubbleSort1) 

 : 버블정렬이란, 이웃한 두 요소의 대소관계를 비교하여 교환을 반복하여 정렬하는 방식을 말한다.

 : 아래 코드에서는 bubbleSort 메서드에 비교할 배열, 배열의 길이를 매개변수로 보내고

   메서드안에서 다시 swap 메서드를 호출하여 교환을 반복하는 방식을 취하고 있다.

 

package practice;
 
import java.util.Scanner;
 
public class BubbleSort_6_1 {
    //버블정렬 버전1
    
    
    static void swap(int[]a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
 
    
    static void bubbleSort(int[]a, int n) {
        for (int i = 0; i < n-1; i++) {
            
            for (int j = n-1; j > i; j--) 
                if(a[j-1]>a[j])    swap(a, j-1, j);            
        }
    }
    
 
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int nx;    //정렬할 배열의 크기
        int[]x; // 정렬할 배열
        
        System.out.println("버블정렬 (버전1)");
        System.out.print("요솟수: ");        nx = stdIn.nextInt();
        x = new int[nx];
        
        for (int i = 0; i < nx; i++) {
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }
        
        bubbleSort(x,nx);
        
        System.out.println("오름차순으로 정렬했습니다.");
        
        for (int i = 0; i < nx; i++) 
            System.out.println("x["+i+"]= "+x[i]);
        
        
    }
}
 

---

6-2. (BubbleSort2)

 : 어떤 경우 정렬이 빨리 끝날 수도 있는데 6-1 코드에서는 그것을 판단하는 코드가 없었다.

 : 21번째 줄 if(exchg==0) break;  문으로

   불필요한 정렬을 끊어줌으로써 알고리즘을 개선한 코드이다.

package practice;
 
import java.util.Scanner;
 
public class BubbleSort2_6_2 {
    
    static void swap(int[]a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    static void bubbleSort2(int[]a, int n) {
        for (int i = 0; i < n-1; i++) {
            int exchg = 0;    //패스의 교환 횟수
            for (int j = n-1; j > i; j--) {
                if(a[j-1]>a[j]) {
                    swap(a, j-1, j);
                    exchg++;
                }
                if(exchg==0) break;    //교환이 이루어지지 않으면 종료
            }
            
        }
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int nx;    
        int[]x; 
        
        System.out.println("버블정렬 (버전2)");
        System.out.print("요솟수: ");        nx = stdIn.nextInt();
        x = new int[nx];
        
        for (int i = 0; i < nx; i++) {
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }
        
        bubbleSort2(x,nx);
        
        System.out.println("오름차순으로 정렬했습니다.");
        
        for (int i = 0; i < nx; i++) 
            System.out.println("x["+i+"]= "+x[i]);
    }
}
 
 

---

6-3. (BubbleSort3)

 : 1,2 번 코드의 경우 일정 정렬이 된 이후 '비교'는 하고 '교환'은 하지 않는 경우가 있었다.

 : 3번 코드에서는 위와 같은 경우를 , last 변수를 도입함으로써 개선하였다.

 

package practice;
 
import java.util.Scanner;
 
public class BubbleSort3_6_3 {
    
    static void swap(int[]a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    static void bubbleSort3(int[]a, int n) {
        int k = 0;
        
        while(k < n-1) {
            int last = n-1;
            
            for (int j = n - 1; j > k; j--) {
                
                if(a[j-1] > a[j]) {
                    swap(a, j-1, j);
                    last = j;
                }
                
                k=last;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int nx;    
        int[]x; 
        
        System.out.println("버블정렬 (버전3)");
        System.out.print("요솟수: ");        nx = stdIn.nextInt();
        x = new int[nx];
        
        for (int i = 0; i < nx; i++) {
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }
        
        bubbleSort3(x,nx);
        
        System.out.println("오름차순으로 정렬했습니다.");
        
        for (int i = 0; i < nx; i++) 
            System.out.println("x["+i+"]= "+x[i]);
    }
 
}