문제
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²) 반복문이 두 개
코드
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+" ");
}
}
}
'PS(Java) > 인프런 강의 문제' 카테고리의 다른 글
[PS] 인프런 강의 - Sorting and Searching 2. 버블 정렬 (0) | 2022.11.12 |
---|---|
[PS] 인프런 강의 - Sorting and Searching 1. 선택 정렬 (0) | 2022.11.12 |
[PS] 인프런 강의 - Stack & Queue 8. 응급실 (0) | 2022.11.09 |
[PS] 인프런 강의 - Stack & Queue 7. 교육과정 설계 (0) | 2022.11.09 |
[PS] 인프런 강의 - Stack & Queue 6. 공주 구하기 (0) | 2022.11.09 |