문제
N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 삽입정렬입니다.
[입력설명]
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
[출력설명]
오름차순으로 정렬된 수열을 출력합니다.
입력예제 1
6
11 7 5 6 10 9
출력예제 1
5 6 7 9 10 11
문제 풀이
예습 이론
삽입 정렬은 첫 숫자는 놔두고, 두 번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는다.
삽입 정렬은 성능이 뛰어난 정렬은 아니다. 시간복잡도가 O(N^2) 이기 때문이다. O(N^2)가 안 좋다고 했지만 사용하는 이유는 알고리즘 자체가 간단하기 때문이다. 그리고 30개 이하의 숫자의 경우에는 괜찮은 성능을 보인다. (대신 그 이상일 경우에는 다른 정렬 알고리즘을 사용해야 한다.)
작은 수에서만 효과적인 경우가 많다. 첫 번째로 배우는 이유는 간단하기 때문이다. 또한 이미 정렬되어 있는 배열에 새로운 원소를 집어넣어 다시 정렬할 때는 매우 효과적이다. (새 원소를 처음부터 한번씩만 기존의 원소들과 비교하면 되기 때문!)
삽입정렬 참고 영상
코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(arr){
let answer=arr; //얕은 복사
for(let i=1; i<arr.length; i++){
let tmp=arr[i], j; //scope문제로 인해 j 여기 선언
for(j=i-1; j>=0; j--){
if(arr[j]>tmp) arr[j+1]=arr[j];
else break;
}
arr[j+1]=tmp; //(j=0까지 반복문 돌았을 때)j=-1이 됨. 즉, arr[-1+1]=arr[0]
}
return answer;
}
let arr=[11, 7, 5, 6, 10, 9];
console.log(solution(arr));
</script>
</body>
</html>참고
삽입 정렬: https://www.zerocho.com/category/Algorithm/post/57e39fca76a7850015e6944a
시간복잡도: https://www.zerocho.com/category/Algorithm/post/57ea2987fdea850015313534
9/14
그림그려서 원리이해하고, 코드 짜보기