선택정렬을 시작하기 전에 얼마나 다양한 정렬 방법과 각 정렬방법의 장단점을 알고 싶으면 아래 사이트를 확인해보자. 시각적으로 표현되어 흐름을 이해하기 쉽다.
https://www.toptal.com/developers/sorting-algorithms
선택 정렬(selection Sort)
선택정렬은 간단히 얘기해서 배열에서 두개 씩 값을 비교하여 가장 큰 작은 값을 제일 첫번째 값에 보내는 방법이라 보면 된다.
한 번 반복문을 돌면 이렇게 현재 제일 작은 값을 배열에 앞쪽에 위치시킨다.
그럼 1를 제외하고 다시 반복문으로 비교를 진행하고 나머지 중에 가장 작은 값인 2가 1에 다음으로 오게 된다.
이렇게 반복하면,
[1, 3, 4, 5, 2]
[1, 2, 4, 5, 3]
[1, 2, 3, 5, 4]
[1, 2, 3, 4, 5]
네번의 반복문으로 오름차순 정렬이 된다.
이미 정렬된 위치를 제외하고 최소값을 찾아 정렬 시키는 방식이다.
아래는 실제 코드를 작성한 부분이다.
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let lowest = i; // 초기 값 세팅
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) { // 최소값 비교 구문
lowest = j;
}
}
console.log(arr);
[arr[i], arr[lowest]] = [arr[lowest], arr[i]]; //swap 구문
}
return arr;
}
selectionSort([34, 22, 0, 10, 19, 17]);첫번째 반복문은 이미 정렬된 값은 비교하지 않고 이후 값부터 비교하게 해주는 구문이라 보면 된다.
위 코드는 허점이 하나 있다.
마지막 비교할때에는 i가 lowest일 수 밖에 없다. j가 arr.length보다 커지므로 반복문을 스킵하기 때문이다.
이때 교환할 이유가 없지만 자기자신과 교환하게 된다.
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let lowest = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j;
}
}
if (i !== lowest) {
[arr[i], arr[lowest]] = [arr[lowest], arr[i]];
}
}
return arr;
}위에 처럼 조건문 하나를 추가해주면 동작을 막을 수 있다.
여기서 선택정렬의 시간복잡도는 n²이다. 모든 항목에 대해 이중 반복문을 실시하기 때문이다.
따라서 가능한 최고 경우는 이미 정렬된 배열은 O(n)이고 최악은 O(n²)이다.
선택 정렬이 버블보다 낫다고 생각하는데에는 교환하는 횟수때문이다.
버블 정렬은 매번 교환을 진행하며 큰 수를 움직인다.
그러나 선택정렬은 반복문이 다 돌고나서 한번 교환을 하기 때문에 버블보다 수행하는 로직이 더 적다.
여기까지 선택정렬 대해서 알아보았다.
아직까진 시간복잡도를 줄이는 정렬을 만나지 못했다.
그래도 알고리즘에 대해 이해하기에는 좋은시간이었다고 생각한다.
다음시간에는 삽입정렬에 대해 알아보자.
