[알고리즘] 선택 정렬 Selection Sort
설명
원소를 넣을 위치를 정하고,어떤 원소를 넣을지 선택한 후 선택한 원소를 지정한 자리에 넣는 알고리즘이다.
과정
(오름차순 정렬인 경우)
1. 배열의 원소 중에서 최소값을 찾는다.
2. 해당 값을 배열의 맨 앞에 위치한 값과 교환한다.
3. 고른 자리(맨 앞)를 제외한 나머지 배열을 같은 방식으로 반복한다.
구현(Java)
public static void sort(int[]arr){
for (int i = 0; i < arr.length-1; i++) { //지정할 원소 위치. 배열의 범위 시작점이기도 함
int minIdx = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[minIdx] > arr[j]){
minIdx= j;
}
}
//지정위치에 있는 원소와 최소값 원소 자리 교환
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}1. i는 선택한 원소의 자리인 동시에 배열의 범위가 시작하는 점이다.
2. i+1자리부터 배열의 마지막 원소까지 최소값을 찾아서, idx를 저장한다.
3. 최소값 탐색이 끝나면 지정자리(i)에 있는 원소와 최소값 원소를 swap한다.
시간복잡도와 공간 복잡도
시간복잡도
첫번째 회전 : 1 ~ n => n-1
두번째 회전 : 2 ~ n => n-2
=> (n-1) + (n-2) + (n-3) + ... + 2 + 1 => n(n-1)/2
이므로 O(n^2)의 시간 복잡도를 갖고, 최악, 평균, 최선 모두 O(n^2)의 시간 복잡도로 동일하다.
공간복잡도
주어진 배열 안에서 교환을 통해 정렬이 수행되기 때문에 O(n)
장점
- 단순하다.
- 정렬을 위한 비교횟수는 많지만, Bubble Sort에비해 실제로 교환하는 횟수는 적기 때문에 비교적 효율적이다.
- 정렬하고자 하는 배열안에서 교환하는 방식으로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place-sorting)
단점
시간 복잡도가 O(n^2)으로 비효율적이다.
불안정 정렬(Unstable Sort)이다.
불안정 정렬이란?
만약 두개의 원소가 동일한 경우 두 원소의 순서가 바뀔 수도 있는 정렬을 말한다.
예시를 들어보면 쌍으로 저장되어있는 데이터가 있는 경우가 있다고 가정해보자. 데이터는 기존에
(2, 'a') , (6, 'd') , (4, 'a') , (6, 'v') 순으로 저장되어있다. 같은 원소를 가지고 있는 경우에 집중해보자.
정렬 알고리즘을 통해서 순서가 만약
(2, 'a') , (4, 'a') , (6, 'v'), (6, 'd') 가 나올 가능성이 있다면 불안정 정렬이라고 한다.
반대로 안정 정렬은 두 원소의 순서가 같은 경우 기존의 순서가 유지됨을 보장한다.
위의 예시에 안정 정렬을 적용한다면 항상 다음과 같은 결과가 나온다.
(2, 'a') , (4, 'a') , (6, 'd'), (6, 'v')
-> Bubble Sort와 유사하지만, 조금 더 빠른 정렬방법이다. 기술 면접이나 시험에 종종 나오는 정렬이므로 알아두는게 좋다.
참조