개발박사가 되고싶은 척척학사
[알고리즘]정렬-선택정렬(Selection Sort) 본문
선택 정렬 : 해당 순서에 원소를 넣을 위치를 먼저 정한 후, 어떤 원소를 넣을지 선택하는 알고리즘
예시) 선생님이 학생들을 작은 키부터 큰 키 순서대로 세운다고 가정해보자. 1열로 서있는 학생들 중 가장 작은 학생을 뽑아 맨 앞으로 보내고, 남은 학생들 중 가장 작은 학생을 두번째로 보낸다. 이런 식으로 자리를 먼저 정하고 그 자리에 어떤 원소를 넣을지를 정하는 것이 선택 정렬이다.
과정
- 주어진 배열의 최소값을 찾는다.
- 그 값을 맨앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
Java Code - 오름차순 기준
void selectionSort(int[] arr) {
int indexMin, temp;
// 1. 원소를 넣을 위치(index) 선택
for (int i = 0; i < arr.length-1; i++) {
indexMin = i; // 배열의 첫번째 값을 최소값으로 설정
// 2. i+1번째 원소부터 index 의 값과 비교
for (int j = i + 1; j < arr.length; j++) {
// 3. 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, index를 갱신
if (arr[j] < arr[indexMin]) {
indexMin = j;
}
}
// 4. swap(arr[indexMin], arr[i])
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
시간복잡도와 공간복잡도
시간복잡도
데이터의 개수를 n개라고 했을 때,
- 첫 번째 회전에서의 비교 횟수 : 1~n → n-1회
- 두 번째 회전에서의 비교 횟수 : 2~n → n-2회
- ....
- (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
이와 같이 비교가 이루어지므로 시간 복잡도는 O(n^2) 이다.
공간 복잡도
선택 정렬은 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 공간 복잡도가 O(n) 이다.
🔈 시간복잡도, 공간복잡도가 뭔지 모르겠다면 글 확인하기!
2020/02/11 - [기술면접] - [알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도
장점과 단점
장점
- 거품정렬(Bubble Sort)와 마찬가지로 알고리즘이 단순하다.
- 비교횟수는 많지만 거품정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.
- 거품정렬과 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식으로, 다른 메모리 공간을 필요로 하지 않는다. 이런 정렬을 제자리 정렬(in-place sorting)이라고 한다.
단점
- 시간 복잡도가 O(n^2) 으로 비효율적이다.
- 불안정 정렬(Unstable sort)이다.
자료출처 및 참고 사이트
https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.htmlhttps://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
'Algorithm' 카테고리의 다른 글
[알고리즘]정렬-삽입정렬(Insertion Sort) (0) | 2020.04.17 |
---|---|
[알고리즘]정렬-거품정렬(Bubble Sort) (0) | 2020.02.12 |
[알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도 (0) | 2020.02.11 |