7장은 정렬과 그리디, 결정 알고리즘에 관련된 챕터다.
문제
N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 선택정렬입니다.
[입력설명]
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
[출력설명]
오름차순으로 정렬된 수열을 출력합니다.
입력예제 1
6
13 5 11 7 23 15
출력예제 1
5 7 11 13 15 23
문제 풀이
예습 이론
- 선택정렬은 깔끔한 알고리즘이지만, 빠르지 않다. 시간복잡도가 O(n2)이다.
선택정렬의 성능은 좋지 않지만 코드가 간단하고, 작은 수(보통 30 이하)에서는 효과적이기 때문에 필요한 정렬이다.
성능이 좋다고 표현되는 정렬들은 오히려 30 이하의 작은 수에서는 성능이 안 좋은 경우가 많기 때문이다.
선택 정렬은 배열을 처음부터 훑어서 가작 작은 수를 제일 앞에 가져다 놓는다. 그 다음, 다시 배열을 훑어서 두 번째로 작은 수를 두 번째 칸에 가져다 놓습니다. 계속 반복해서 끝까지 정렬합니다. 성능이 안 좋을 수밖에 없는 게, 배열을 한 번 훑었을때 숫자 하나밖에 정렬을 못 한다. 하지만 사람이 정렬을 하는 방법과 상당히 유사하다.
[arr[i], arr[idx]]=[arr[idx], arr[i]]: arr[i]와 arr[idx]의 위치를 바꾼다.
코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(arr){
let answer=arr; //얕은 복사(같음)
for(let i=0; i<arr.length-1; i++){
let idx=i;
for(let j=i+1; j<arr.length; j++){
if(arr[j]<arr[idx]) idx=j; //배열에서 가장 작은 값의 인덱스를 idx에 넣음
}
[arr[i], arr[idx]]=[arr[idx], arr[i]]; //arr[i], arr[idx]를 서로 교환(js 최신버전)
}
return answer;
}
let arr=[13, 5, 11, 7, 23, 15];
console.log(solution(arr));
</script>
</body>
</html>참고
https://www.zerocho.com/category/Algorithm/post/57f728c85141fc5fe4f4ca89
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/14