[백준/BAEKJOON] 2750번 수 정렬하기 JAVA

 

1.

버블정렬이다.

 

첫 번째 인덱스부터 시작하여 뒤의 인덱스들의 값들과 비교하여 최솟값들을 차곡차곡 쌓아나가는 방법이다. 가장 구현하기 쉽다는 장점이 있으나 시간복잡도가 O(n2) 으로 그리 좋은 성능의 알고리즘은 아니다. 아마 정렬을 구현해보거나 접해본 분들이라면 한 번 쯤은 보았을 코드다.

 

2.

가장 간단한 방법으로, Arrays.sort() 메소드를 쓰는 방법이다. Arrays.sort() 는 자바에서 기본으로 제공되는 메소드로, 자체 정렬 알고리즘을 구현 할 필요 없이 sort() 안에 배열만 넣어주면 자동으로 해당 배열이 정렬되어 나온다. Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 쓰고 있기 때문에 시간복잡도는 평균 O(nlogn) 으로 좋은 성능을 내고 있다. 물론 최악의 경우에는 O(n2)  이기 때문에 저격 데이터를 넣을 경우 효율은 떨어질 수 있다. 이와 관련해서는 수 정렬하기 2 을 풀면 알 수 있다. 그럼에도 나쁘지 않은 알고리즘인 것은 맞다. (사실상 직접 비교 정렬 알고리즘은 O(nlogn) 이 마지노선 시간복잡도로 보고 있다.)

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
 
		// Bubble sort
		for(int i = 0; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				if(arr[i] > arr[j]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
		
		for(int val : arr) {
			System.out.println(val);
		}
 
	}
}