CS) 정렬 - 선택정렬과 효율성
선택 정렬은 앞서 살펴보았던 버블 정렬과는 다르게 값을 비교한 뒤 조건에 맞아도 그 값을 곧바로 교환하지 않고 전체 원소를 탐색한 뒤, 원소 중 최소값과 시작점을 교환한다.
선택정렬의 패스 스루는 다음과 같다.
const arr = [3,4,2,8,5]
-
최소값으로 인덱스 0번에 저장된 값을 설정하고 그 다음 인덱스에 저장된 값과 비교한다.
3보다 4는 작으므로 3이 최소값이다. -
최소값 3은 그 다음 인덱스인 2보다 크다.
3은 2보다 크므로 2가 최소값이다.
하지만 버블정렬처럼 바로 자리(index)를 교환하지는 않으며 최소값을 기억하기만 한다. -
최소값 2는 그 다음 인덱스인 8보다 작다.
최소값은 여전히 2이다. -
최소값 2는 그 다음 인덱스인 5보다 작다.
최소값은 여전히 2이다.
배열의 끝까지 순회하였으므로 기억하고 있던 최소값이 저장되어 있는 인덱스를 처음 최소값을 설정한 인덱스와 순서를 바꾸어 준다.
이 예제에서는 인덱스 0과 인덱스 2를 바꾼다.
이제 arr는 [2,4,3,8,5]를 갖는다.
두번째 패스 스루의 시작점은 최소값을 저장한 인덱스의 다음 인덱스이다.
-
최소값으로 인덱스 1번에 저장된 값을 설정하고 그다음 인덱스에 저장된 값과 비교한다.
최소값 4는 3보다 크므로 3이 최소값이다.
최소값을 3으로 설정한다. 자리를 교체하지는 않는다. -
최소값 3은 그 다음 인덱스인 8보다 작다.
최소값은 여전히 3이다. -
최소값 3은 그 다음 인덱스인 5보다 작다.
최소값은 여전히 3이다.
배열의 끝까지 순회하였으므로 기억하고 있던 최소값이 저장되어 있는 인덱스를 처음 최소값을 설정한 인덱스와 순서를 바꾸어준다.
이 예제에서는 인덱스 1과 인덱스 2를 바꾼다.
이제 arr는 [2,3,4,8,5]이다.
이런식으로 패스 스루는 최소값으로 설정한 인덱스의 다음 인덱스가 존재하지 않을 때까지 순회한다.
선택 정렬을 함수로 구현하면 아래와 같다.
자바스크립트로 구현한 선택정렬
const selectionSort = (arr) => {
for(let i = 0; i < arr.length; i++) {
let lowestIndex = i;
for(let j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[lowestIndex]) {
lowestIndex = j;
}
}
if(i !== lowestIndex) {
let temp = arr[i];
arr[i] = arr[lowestIndex];
arr[lowestIndex] = arr[i];
}
}
return arr
}외부 for문은 패스스루의 회수를, 중첩 for문은 배열 내 요소 순회를 담당하고 있다.
선택정렬의 효율성
버블정렬처럼 비교와 교환 두 종류의 단계를 동일하게 포함하는 선택정렬이지만, 교환의 횟수가 버블정렬보다는 적다.
조건에 맞는다고 바로 값을 교환하는게 아닌, 패스 스루가 끝날때까지 기다렸다가 마지막에 교환하기 한 번만 교환하기 때문이다.
배열 내 원소의 크기가 역순으로 되어 있을때 버블 정렬은
(N - 1)+(N - 2)+(N - 3)... + 1 번 비교하고,
(N - 1)+(N - 2)+(N - 3)... + 1번 교환하지만,
선택 정렬은 (N - 1)+(N - 2)+(N - 3) + 1번 비교하고,
(N - 1)번 교환한다.
즉 선택 정렬은, 버블 정렬보다 두 배 더 빠르다.
하지만 재미있게도 Big O 표기법에서는 선택 정렬과 버블 정렬을 정확히 같은 방식으로 설명한다
버블 정렬은 O(N²)이다. 선택 정렬은 교환을 한번만 진행하므로 O(N² / 2)정도일 것이다.
하지만 실제로 선택 정렬을 Big O로 표현하면 버블 정렬과 똑같이 O(N²)이다.
그것은 바로 Big O의 규칙 때문이다.
Big O 표기법은 상수를 무시한다.
Big O 표기법은 지수가 아닌 수는 표함하지 않는다는 것을 단순히 수학적으로 표현한 문장이다.
앞서 선택 정렬의 원소수를 나타내는N의 뒤에 오는 상수 / 2 를 날려버린 것 처럼 몇가지 예가 있다.
N / 2 단계가 필요한 알고리즘은 O(N)으로 표현한다.
N² + 100이 필요한 알고리즘은 100을 버리고 O(N²)이라고 표현한다.
2N단계가 필요한 알고리즘은 O(N)으로 표현한다.
심지어 O(N)보다 100배나 느린 O(100N)도 100은 상수이기 때문에 O(N)으로 표현한다.
Big O는 똑같이 표현한 두 알고리즘에 대해 한쪽이 다른 한쪽보다 100배나 빠를 수 있게 표현한다.
대체 왜 그러는걸까?
