[PS] 인프런 강의 - Sorting and Searching 3. 삽입 정렬

문제

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 삽입정렬입니다.

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

▣ 출력설명
오름차순으로 정렬된 수열을 출력합니다.

▣ 입력예제 1
6
11 7 5 6 10 9

▣ 출력예제 1
5 6 7 9 10 11

 

풀이

 

❗ 정렬의 회전 횟수 및 비교횟수

정렬은 기본적으로 1번의 회전이 끝나고 찾은 배열의 최소값이나 최대값을, 맨앞이나 맨뒤의 값과 교체하는 것이다.

한 번의 회전 당 하나의 값이 정렬되는 꼴인데,

n개의 값을 정렬한다고 할 때, n-1개를 정렬하면 나머지 하나는 저절로 정렬되기 때문에 n-1번의 회전이 필요하게 된다.

그리고 n개의 값이 있다고 할 때, 맨 마지막 값은 비교할 필요가 없기 때문에 두 값을 비교하는 횟수는 n-1번이면된다.

 

 

삽입 정렬(insertion sort) : 앞서 이미 정렬된 원소들과 비교 해서 알맞은 위치를 찾아서 '삽입' 하는 정렬

• 앞서 이미 정렬된 원소들과 비교하므로 2번째 값부터 체크하면 된다.
• 시간 복잡도 O(n²) 반복문이 두 개

 

gif 출처

 

코드

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = in.nextInt();
		}
		//삽입 정렬 오름차순
		for(int i=1; i<n; i++) { //두번째거 부터 체크
			int check = arr[i]; //밀면 날아가니까 체크할 값은 킵
			int j; //앞의 정렬된 그룹 중 나보다 작은 값 위치
			for(j=i-1; j>=0; j--) {
				if(arr[j] > check) arr[j+1] = arr[j]; //나보다 큰값은 뒤로 민다(i 자리비어서 ㄱㅊ)
				else break; //값이 작으면 체크 끝
			}
			//나보다 작은 값 바로 뒤 빈곳에 넣기
			arr[j+1] = check; //j+1 = for문이 멈춘 인덱스 바로 뒤
		}
		
		for(int x : arr) {
			System.out.print(x+" ");
		}
	}
}