[백준 알고리즘][자바] 2750번 : 수 정렬하기

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

2750번: 수 정렬하기

2022.01.22 - [Algorithm/Theory] - [자바] 단순 선택 정렬과 단순 삽입 정렬

[자바] 단순 선택 정렬과 단순 삽입 정렬

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] numbers = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			int num = Integer.parseInt(br.readLine());
			numbers[i] = num;
		}

		insertionSort(numbers, N);
		
		for(int i = 0 ; i < N ; i++) {
			bw.write(String.valueOf(numbers[i]) + "\n");
		}
	
		br.close();
		bw.flush();
		bw.close();
	}
	
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}

	static void insertionSort(int[] a, int N) {
		for (int i = 1; i < N; i++) { // 두번째 요소부터 시작
			int j;
			int temp = a[i];
			for (j = i; j > 0 && a[j - 1] > temp; j--) { // 앞쪽의 요소와 비교
				a[j] = a[j - 1]; // 왼족의 요소와 교환
			}
			a[j] = temp;
		}
	}
}

사용한 알고리즘은 단순 삽입 정렬로 배열의 두 번째 요소부터 시작하여

앞쪽의 요소와 하나씩 비교하여 알맞은 자리에 삽입하는 단순한 정렬 알고리즘입니다.

오름차순 정렬이기 때문에 아래의 코드에서 자기보다 큰 수이면 계속 교환하다가 작은 수가 나오면 교환을 멈추게 되어

알맞은 위치에 정렬이 됩니다.

for (j = i; j > 0 && a[j - 1] > temp; j--) { // 앞쪽의 요소와 비교
				a[j] = a[j - 1]; // 왼족의 요소와 교환
}