강의: 구름에듀 "안경잡이개발자가 알려주는 실전 알고리즘 강좌"
링크: 안경잡이개발자가 알려주는 실전 알고리즘 강좌
(강의는 알고리즘 풀이를 C/C++ 언어로 진행합니다.)
정렬 알고리즘
대체로 알고리즘을 공부할 때 가장 먼저 나오는 개념이 정렬 알고리즘인 이유는 효율성의 차이를 가장 극명하게 보여주기 때문
선택정렬
가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘
의사코드를 작성한다면?
인덱스가 0인 요소와 인덱스가 1 ~ 9인 요소 비교
-> 가장 작은 인덱스 기억해두기
-> 가장 작은 인덱스가 0이 아닐 경우 두 요소의 위치 바꾸기
인덱스가 1인 요소와 인덱스가 2 ~ 9인 요소 비교
-> 이후 반복
코드로 작성한다면?
function swap (i, j, arr) {
const temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
function solution (arr) {
for (let i = 0; i < arr.length; i++) {
let minIdx = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIdx] > arr[j]) {
minIdx = j;
}
}
if (minIdx !== i) {
swap(i, minIdx, arr);
}
}
return arr;
}
console.log(solution(arr1));시간 복잡도
시간 복잡도는 알고리즘 연산을 위해 총 몇 번의 비교 연산을 해야하는지를 의미
선택 정렬은 약 N * (N + 1) / 2번의 연산을 수행
0번째 인덱스와 1 ~ 마지막 인덱스 요소까지 비교 -> N번
1번째 인덱스와 2 ~ 마지막 인덱스 요소까지 비교 -> N - 1번
...
마지막 - 1 인덱스와 마지막 인덱스 요소까지 비교 -> 1번
N + (N - 1) + ... + 1 = N * (N + 1) / 2
컴퓨터에서는 가장 큰 차수인 N^2만 보고 O(N^2)라고 표현
(O는 BigO 표기법)
BigO
- Worst Case(정렬이 하나도 안되어있는 경우): O(N^2)
- Best Case(이미 정렬이 되어있는 경우): O(N^2)
장점
- 선택 정렬도 위의 두 정렬과 같이 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이므로 이해하기도 쉽고 구현하기도 쉬움
- (* in place 알고리즘: 자료 구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘)
단점
- 선택 정렬은 최선의 경우에도, 최악의 경우에도 O(n^2)의 시간이 걸리는 만큼 성능이 매우 떨어짐
- 중복된 위치가 바뀔 수 있는 Unstable한 정렬임
ex) 5, 5, 1 에서 인덱스가 0인 5가 인덱스가 2인 1과 자리가 바뀔 경우 중복 데이터인 5의 순서가 바뀌게 됨
