[백준 2750] 수 정렬하기1 - 버블정렬 구현(Java)

https://www.acmicpc.net/problem/2750

수 정렬하기 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5
5
2
3
4
1

예제 출력 1 복사

1
2
3
4
5

---

풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine()); // 1번째 줄 읽음

        int N = Integer.parseInt(st.nextToken()); // N : 숫자의 개수
        int[] A = new int[N]; // 크기 N의 배열 선언
        int swapCount = 0; // swap count

        // 원본배열에 값 넣기
        for(int i=0; i<N; i++){
            A[i] = Integer.parseInt(br.readLine());
        }

        // 버블정렬을 구현하는 영역
        for(int i=0; i<N-1; i++){
            swapCount = 0;
            for(int j=0; j<N-1-i; j++){
                if(A[j] > A[j + 1]){
                    swap(A, j, j+1);
                    swapCount++;
                }
            }
            if(swapCount ==0) break;
        }

        for (int i=0; i<N; i++){
            sb.append(A[i]).append("\n");
        }

        System.out.println(sb);
    }

    public static void swap(int[] A, int i, int j){
        int temp = 0;
        temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

 

• Arrays.sort()를 사용해도되지만 일부러 버블정렬로 구현하였다.
• 버블정렬은 인접한 두개의 데이터를 비교하여 정렬을 수행한다.
• 버블정렬은 한번의 루프를 돌때마다 1개의 데이터가 정렬된다.
• i는 0 ~ N-1까지 순회한다. -> 루프 수 의미
• j는 0 ~ N-1-i까지 순회한다. -> 정렬하는 범위 의미
• 만약 특정한 루프의 전체영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도된다.(swapCount)