CodeKata 5-1. Selection Sort(선택정렬)

서동이·2021년 4월 26일
0
post-thumbnail

문제> 선택정렬은 정렬되지 않은 데이터 중 가장 작은 데이터를 선택해서
맨 앞에서부터 순서대로 정렬해 나가는 알고리즘입니다.

예제를 통해 보겠습니다.

정렬을 해야하는 배열은 [7,5,4,2] 입니다.

첫 번째 loop에서는 index 0부터 3까지 확인하며 가장 작은 수를 찾습니다.
2 이므로 index 0의 7과 교체합니다. -> [2,5,4,7]

두 번째는 index 1부터 3까지 확인하며 가장 작은 수를 찾습니다.
4이므로 index 1의 5와 교체합니다 -> [2,4,5,7]

세 번째는 index 2부터 3까지.. 이런식으로 가장 작은 수를 선택해서 순서대로 교체하는 것을 선택정렬이라고 합니다.

내가생각한 답안.

제일 작은수부터 차례대로 나열하라니까

const selectionSort = (nums) => {
 let result = nums.sort(function(a, b){
	return a - b ;
}) ;
}

일단 sort()로 답은 제출해봤지만 응,,,아냐;;;

배운개념


선택 정렬(selection sort)

  • 제자리 정렬(in-place sorting) 알고리즘의 하나
  • 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
  • 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.

<과정 설명>
주어진 배열 중에서 최솟값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
선택 정렬(selection sort) 알고리즘의 구체적인 개념
선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

선택 정렬(selection sort) 알고리즘의 특징

-장점: 자료 이동 횟수가 미리 결정된다.
-단점: 안정성을 만족하지 않는다.
즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

선택 정렬(selection sort)의 시간복잡도

시간복잡도를 계산한다면

비교 횟수
두 개의 for 루프의 실행 횟수
외부 루프: (n-1)번
내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번
교환 횟수
외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번
T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)
정렬 알고리즘 시간복잡도 비교

  • 단순(구현 간단)하지만 비효율적인 방법
    :삽입 정렬, 선택 정렬, 버블 정렬
  • 복잡하지만 효율적인 방법
    : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
function selectionSort (array) {
for (let i = 0; i < array.length; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[minIndex] > array[j]) {
minIndex = j;
}
}
if (minIndex !== i) {
let swap = array[minIndex];
array[minIndex] = array[i];
array[i] = swap;
}
console.log(`${i}회전: ${array}`);
}
return array;
}
console.log(selectionSort([5, 4, 3, 2, 1]));


출처: https://im-developer.tistory.com/133 [Code Playground]

자료출처
https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

profile
오늘도 여전히 사고친걸 해결해본당,,

0개의 댓글