[백준 2750 / 2751 Java] 수 정렬하기 - 선택 정렬 / Arrays / Collections

선택 정렬

첫 번째 인덱스부터 시작하여 뒤의 인덱스들의 값들과 비교하여 최솟값들을 차곡차곡 쌓아나가는 방법으로

구현하기 쉬우나 시간 복잡도가 O(n²)로 성능이 좋지 못하다는 단점이 있다.

 

1. 주어진 리스트 중에 최소값을 찾는다. (기본 오름차순)

2. 그 값을 맨 앞에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

4. 하나의 원소만 남을 때까지 위의 과정을 반복한다.

 

import java.util.Scanner;

// 선택 정렬을 이용한 방법
public class Ex1 {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] arr = new int[n];
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		
		// 선택 정렬을 이용한 오름차순 정렬
		// i를 비교 기준, j를 비교하는 대상으로 보자
		for(int i = 0; i < n; i++) {
			
			for(int j = i + 1; j < n; j++) { // i+1: 두번째 요소부터 비교
				
				if(arr[i] > arr[j]) { // 기준보다 더 작은 값이 있다면
					// 값을 교환
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
			
		}

		for(int val : arr) {
			System.out.println(val);
		}
		
	}

}

 

Arrays.sort()

dual-pivot Quicksort 알고리즘

 

import java.util.Arrays;
import java.util.Scanner;

// Arrays 클래스를 이용한 방법
public class Ex1_1 {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] arr = new int[n];
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		for(int val : arr) {
			System.out.println(val);
		}
		
	}

}

 

Collections.sort()

Timsort 반복 합병 및 삽입정렬 알고리즘

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

// Collections 클래스를 이용한 방법
public class Ex2 {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int n = sc.nextInt();
		
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i = 0; i < n; i++) {
			list.add(sc.nextInt());
		}
		
		Collections.sort(list);
		
		for(int val : list) {
			sb.append(val).append('\n');
		}
		
		System.out.println(sb);
		
	}

}