[인프런 알고리즘] Chpater 6, 2번 문제 (버블 정렬)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec06_02 {
    public static int[] solution(int[] arr) {
        for(int i = 0; i < arr.length - 1; ++i)
        {
            for(int j = 0; j < arr.length - 1 - i; ++j)
            {
                if(arr[j] > arr[j + 1])
                {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        for (int i : solution(arr)) {
            System.out.print( i + " ");
        }
    }
}

 

설명

• 외부 루프 (i)
  -배열을 여러 번 순회하며 정렬을 반복한다.
  -첫 번째 순회가 끝나면 배열에서 가장 큰 값이 배열의 마지막으로 “버블”처럼 올라간다.
  -이 과정을 배열의 길이 arr.length - 1 만큼 반복하면서 정렬이 완료된다.
  
  
• 내부 루프 (j)
  -배열의 인접한 두 요소를 비교하는 역할을 한다.
  -배열의 j번째 요소와 j+1번째 요소를 비교하여 arr[j]가 arr[j+1]보다 크면 두 값을 교환한다.
  -각 반복(iteration)마다 가장 큰 요소가 배열의 마지막 부분으로 이동하기 때문에, 내부 루프의 범위는 arr.length - 1 - i로 점점 줄어든다. 즉, 이미 정렬된 부분은 다시 확인하지 않는다.
  
  
• 교환 작업
  -내부 루프에서 arr[j] > arr[j + 1] 조건이 성립하면 두 요소의 값을 서로 교환한다. 이를 통해 작은 값이 앞으로, 큰 값이 뒤로 이동하게 된다.