[백준/BOJ] Bronze2 - 2750번 수 정렬하기 (JAVA)

문제

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

입력

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

출력

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

풀이

N의 최댓값이 1000 밖에 되지 않아서 시간복잡도를 고려하지 않고 정렬 중 가장 기본이되는 버블소트로 정렬을 해주었다

i와 j에 대한 범위를 기억하는 것과 swap을 해주는 코드가 포인트 인 것 같다.

버블소트에서 총 라운드와 각 라운드 별 비교 횟수는 다음과 같다.

 

총 라운드: N-1

각 라운드 별 비교 횟수: N-(라운드 횟수)

j<N-i-1 인 이유는 i가 0부터 시작하기 때문에 라운드 횟수를 빼주기 위해서 -1을 해줘야하는 것이다.

 

버블 소트에 대한 자세한 내용은 아래 블로그에 상세히 설명되어 있다. 

https://st-lab.tistory.com/195

 

자바 [JAVA] - 거품 정렬 (Bubble Sort)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A[] = new int[N];
		
		for(int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		for(int i = 0; i < N-1; i++) {
			for(int j = 0; j < N-i-1; j++) {
				if(A[j] > A[j+1]) {
					int temp = A[j];
					A[j] = A[j+1];
					A[j+1] = temp;
				}
			}
		for(int i1 : A) {
			System.out.println(i1);
		}
		}
	}

}