선택 정렬이란?
최솟값을 찾아서 가장 왼쪽 자리부터 스왑하며 정렬
그림 설명
유튜브 설명
https://www.youtube.com/watch?v=yXE9kFLHSOs
문제
N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 선택정렬입니다.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
▣ 출력설명
오름차순으로 정렬된 수열을 출력합니다.
▣ 입력예제 1
6
13 5 11 7 23 15
▣ 출력예제 1
5 7 11 13 15 23
코드
function solution(arr) {
const answer = arr;
for (let i = 0; i < arr.length; i++) {
let minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
}
return answer;
}
const arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));
버블 정렬이란?
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
왼쪽부터 두 숫자를 비교하면서 큰 숫자를 오른쪽으로 스왑하며 정렬
그림 설명
유튜브 설명
https://www.youtube.com/watch?v=fxuhgRRqYsY
문제
N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 버블정렬입니다.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
▣ 출력설명
오름차순으로 정렬된 수열을 출력합니다.
▣ 입력예제 1
6
13 5 11 7 23 15
▣ 출력예제 1
5 7 11 13 15 23
코드
function solution(arr) {
const answer = arr;
for (let i = 0; i < arr.length - 1; i++) {
// arr.length - 1 한 이유는 어짜피 마지막에 제일 큰 수를 집어 넣을거라서 마지막은 제외
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
console.log(i);
}
}
return answer;
}
const arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr));
이진 탐색이란?
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
그림 설명
유튜브 설명
https://www.youtube.com/watch?v=IfIuG95RH0o
문제
임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.
▣ 입력설명
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
▣ 출력설명
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
▣ 입력예제 1
8 32
23 87 65 12 57 32 99 81
▣ 출력예제 1
3
코드
function solution(target, arr) {
let answer;
arr.sort((a, b) => a - b);
let lt = 0,
rt = arr.length - 1;
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (arr[mid] === target) {
answer = mid + 1;
break;
} else if (arr[mid] > target) rt = mid - 1;
else lt = mid + 1;
}
return answer;
}
const arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));