[TIL] Java 버블정렬, 선택정렬, 퀴즈파티

✍ Today I Learned

[버블 정렬 Bubble Sort]

• 버블 정렬이란? 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.
• 시간 복잡도는 O(n^2), 공간 복잡도는 O(n)이다.
• 교환 연산(swap)이 많이 일어나기 때문에 비효율적이지만 구현이 매우 간단하고 직관적이다.
• 안정 정렬(Stable Sort)이다.
• 버블 정렬 참고자료

// 버블 정렬
int temp = 0;
for (int i = 0; i < intArr.length; i++) {
    for (int j = 1; j < intArr.length-i; j++) {
        if (intArr[j-1] > intArr[j]) {
            // 왼쪽이 더 크다면 자리를 바꿔줌(swap)
            temp = intArr[j-1];
            intArr[j-1] = intArr[j];
            intArr[j] = temp;
        }
    }
}

버블정렬의 동작원리

 

[배열 메서드 Sort Method]

• Arrays.sort() - java.util.arrays 클래스의 sort() 메서드를 이용하여 배열을 정렬할 수 있다.
• Collections.reverseorder() - 역 정렬을 하고 싶다면 java.util.Collections 클래스의 reversOrder() 메서드를 이용하면 된다. 기본 타입 배열을 역 정렬하고 싶다면 래퍼 클래스로 만들어 Comparator를 두 번째 인자에 넣어준다.
• Arrays.sort() 참고자료

import java.util.Arrays;

public class Sort{
    public static void main(String[] args)  {
        int arr[] = {4,23,33,15,17,19};
        // 순차정렬
        Arrays.sort(arr);

        for (int i : arr) {
            System.out.print("["+i+"]");
        }
    }
}

import java.util.Arrays;

public class Sort{
    public static void main(String[] args)  {
        Integer arr[] = {4,23,33,15,17,19};
        // 역정렬
        Arrays.sort(arr,Collections.reverseOrder());

        for (int i : arr) {
            System.out.print("["+i+"]");
        }
    }
}

• 위의 예시에서 나온 반복문은 forEach문이다. 모든 배열의 요소를 출력할 때 유용하다.

 

[선택 정렬 Selection Sort]

• 선택 정렬이란? 버블 정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
• 시간 복잡도는 O(n^2), 공간 복잡도는 O(n)이다.
• 버블 정렬에 비해 교환 횟수가 적기 때문에 비교적 효율적이다.
• 불안정 정렬(Unstable Sort)이다.
• 선택 정렬 참고자료

// 선택 정렬
int minIdx, temp;
for (int i = 0; i < intArr.length-1; i++) {
    minIdx = i;
    for (int j = i+1; j < intArr.length; j++) {
        if(intArr[j] < intArr[minIdx]) {
            minIdx = j;
        }
    }
    // 현재 위치의 값과 최솟값을 바꿔줌(swap)
    temp = intArr[minIdx];
    intArr[minIdx] = intArr[i];
    intArr[i] = temp;
}

선택정렬의 동작원리

 

[퀴즈 1 절기 맞추기]

• 변수명은 알아보기 쉽게, 연산은 항상 괄호를 적어준다.
• 정답이어도 시도 횟수 올라가도록 count++; 를 설정한다.
• 반복문이 끝난 후 게임 종료 멘트를 출력한다.

 

[퀴즈 2 점수 받아서 출력하기]

• 배열에 저장되어야 하는 데이터들의 타입이 다 다르기 때문에 타입별로 배열을 만들어 저장해야 한다.
• 소수점은 java.text.DecimalFormat 클래스의 format() 메서드를 이용해서 조정한다.

import java.text.DecimalFormat;
...
DecimalFormat df = new DecimalFormat("#.##");
...
System.out.println(df.format(avrgs[i]));

• 모든 선언문은 주로 시작 부분 쪽에 배치한다.
• 나보다 높은 총점을 파악하여 랭킹을 출력할 수 있다.

 

[퀴즈 3 숫자 야구 게임]

• 자바스크립트는 이벤트로 코드의 흐름을 컨트롤하는 느낌이었다면, 자바는 더 큰 그림을 그려서 직접 모든 흐름을 컨트롤하는 느낌이다.
• 정답을 맞힐 때까지 계속해서 유저의 답을 입력받아야 하므로 while문으로 시작한다.
• 유저의 입력 숫자는 split() 메서드를 사용하여 배열을 만들기 위해 문자열로 받는다. (만약 숫자로 받고 싶다면 100의 자리, 10의 자리, 1의 자리로 나누어 배열을 만든다.)
• 이후 for문에서 문자열을 숫자로 바꾸고 int 배열에 저장한다.
• 이중 for문으로 컴퓨터와 유저 숫자를 비교해서 스트라이크와 볼을 판단한다.
• 항상.. 오타에.. 주의하자... 하

 

[퀴즈 4 호텔 객실 관리 프로그램]

• 자바스크립트처럼 안내문구가 계속 노출되어 있는 게 아니기 때문에 여러 번 반복해서 문구를 노출하려면 반복 문안에서 출력해야 한다.
• 초기화는 항상 해두는 게 좋다.
• while문으로 전체 프로그램을 반복하고 조건절에 flag를 넣어 예외 발생 시 프로그램을 종료시킨다.
• 메뉴 선택은 switch문으로 구현한다.
• 인덱스 번호에 접근하는 것만 잘해도 그렇게 어렵지 않다!
• 자바스크립트에서는 호수를 객체에 저장했다면 자바에서는 2차원 배열을 출력할 때 데이터를 가공한다.