[인프런_버블 정렬] 2. 버블 정렬

2. 버블 정렬

 

<<풀이>>

 

-강사님 풀이-

강사님은 "버블 정렬"로 푸셨다. 

버플 정렬은 근접한 값들을 비교해서 순서를 바꿔주는 것이다. 그거를 반복해서 오름차순인 경우 오른쪽 부터 큰값을 밀어 넣는 형식이다.

버블 이라는 단어는 밑 그림처럼 근접한 값들과 비교하면서 표시해놓은 것인데 이런 모양에 본 따서 명칭을 붙인 것이다! 

 

 

이 문제에서 배운 것은 버블 정렬이라는 것과 버블 정렬을 할 때의 이중 for문의 형식이다.

 for(int i = 0; i < n - 1; i++) {
           for(int j = 0; j < n -i -1; j++)

이중 for문에서 안 쪽 for문을 보면 ' j < n -i -1' 를 볼 수 있는데, 버블 정렬 형식상 가장 큰값을 오른쪽에 하나씩 밀어 넣는다. 그렇다면 오른쪽은 이미 정렬 된 형태인 것이다. 따라서 굳이 다시 검사를 해서 정렬을 할 필요가 없기 때문에 딱 그 전까지만 보고 정렬하는 형태인 셈이다. 그렇게 해야 불필요한 계산을 줄이고 효율을 높일 수 있기 때문이다. 이러한 표현도 잘 알아두자!

 

import java.util.*;

class Main {
    private int[] solution(int n, int[] arr) {
       for(int i = 0; i < n - 1; i++) {
           for(int j = 0; j < n -i -1; j++) {
               if(arr[j] > arr[j + 1]) {
                   int tmp = arr[j];
                   arr[j] = arr[j + 1];
                   arr[j + 1] = tmp;
               }
           }
       }
       return arr;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        for(int x : T.solution(n, arr)) {
            System.out.print(x + " ");
        }
    }
}