Selection Sort [선택 정렬]
선택 정렬은 제자리 정렬 알고리즘의 하나로 입력 배열외의 다른 추가 메모리를 요구하지 않는 정렬방법이며 선택정렬은불안정 정렬이다. 배열에 앞에서부터 최솟값 또는 최댓값을 찾아 교환하는 방식의 알고리즘으로 선택 정렬의 과정은 이렇다.
- 주어진 리스트 중에 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

public class 선택정렬 {
public static void main(String[] args) {
int[] arr = {7, 5, 2, 4, 3, 1, 9, 6, 0, 8};
selectionSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
// 선택정렬 알고리즘
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
}
- 장점
- 추가적인 메모리 소비가 거의 없다.
- 단점
- 시간 복잡도가 O(n^2)이다.
- 같은 값이 있는 경우에 위치가 변경될 수 있다.
- 시간복잡도
(n-1) + (n-2) + … + 2 + 1의 시간 복잡도를 갖지만 N^2의 이하로 나오므로 최악의 시간 복잡도는 O(n2)이다.
Bubble Sort와 같은 시간 복잡도를 갖지만 상태적으로 적기 때문에 조금 더 빠르긴 하나 좋은 정렬 알고리즘으로는 보기 힘들다.
- 불안정 정렬이란
{3,3,1,4}의 값이 있다고 하면 선택 정렬 시에 첫 반복에 {1,3,3,4}이 될 것이다. 이렇게 되면 처음 두 개의 3의 위치가 바뀌는데 이 이유 때문에 불안정한 정렬이라고 한다.
- 선택 정렬은 정렬 중에 기본이 되는 정렬방법이지만 성능상 좋지는 못하더라도 알아둬야 할 정렬방법이다.
예제로 풀어보면 될 문제이다.
https://www.acmicpc.net/problem/2752
https://www.acmicpc.net/problem/2750
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
참조
'알고리즘' 카테고리의 다른 글
| [Java]삽입정렬(Insertion Sort) (0) | 2022.05.09 |
|---|---|
| [알고리즘] 유클리드 호제법 (0) | 2022.04.28 |