백준 2750 수 정렬하기 자바

시간 복잡도가 O(n²)인 정렬 알고리즘을 사용.

예를 들면 삽입 정렬, 거품 정렬 등이 있다.

 

삽입 정렬로 풀어보았다.

import java.util.*;
public class Main{
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int num[] = new int[n];

		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt(); // 숫자를 입력받음

			for (int j = i; j > 0; j--) {// 이전 숫자들과 비교하여
				if (num[j] < num[j - 1]) {// 바로 이전 숫자보다 작으면 순서 바꿈
					int tmp = num[j];
					num[j] = num[j - 1];
					num[j - 1] = tmp;
				} else {// 작지 않다면 이전 숫자들은 다 정리된 것이므로 다음 숫자로 넘어감
					break;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			System.out.println(num[i]);
		}
    }
}

 

삽입 정렬에 대한 개념 확인~!

https://marobiana.tistory.com/85

[JAVA] Insertion Sort (삽입정렬)