[Java/백준] 2750.정렬 - 수 정렬하기1 (삽입정렬)

1.문제

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

 

* 시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 삽입 정렬, 거품 정렬 등이 있습니다.

* 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다.

  이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

 

2.삽입정렬 예시

 

3.풀이

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int size = sc.nextInt();
		int[] arr = new int[size];
		
		//수 입력받기
		for(int i=0; i<size; i++) {
			int num = sc.nextInt();
			arr[i] = num;
		}
		
		//삽입정렬
		for(int i=1; i<arr.length; i++) {
			int key = arr[i];	//1번 인덱스부터 시작.
			int j = i-1; 		//0번 인덱스부터 시작. key 앞에 있는 비교군.
			
			//key가 더 작으면 자리이동 event
			while(j>=0 && arr[j]>key ) {
				arr[j+1] = arr[j];	//arr[j] 뒤로 한 칸 이동
				j--;
			}
			
			//key 앞으로 한 칸 이동. event 없을 경우 자리 유지. 
			arr[j+1] = key;
		}
		
		//출력
		for(int i=0; i<arr.length; i++) {
			System.out.println(arr[i]);
		}
		
	}

문제에서 제시한 정렬 중 더 효율적인 삽입정렬을 사용하였다.

 

정처기 공부 할 때 이론상으로만 외웠던 정렬 종류인데 자바 코드로 구현하려니 꽤 애를 먹었다.

여러번 연습해야 할 것 같다.