반응형
요즘 다시 알고리즘 공부를 시작하려고 하여
백준에서 문제를 풀어나가며 알고리즘을 따로 정리, 기술하는 방향으로 계획하고 있다.
그 중 정렬 알고리즘을 먼저 살펴보려고 하며,
오늘은 기본 중 하나인 선택 정렬를 알아보고자 한다.
선택 정렬 ( Selection Sort )
선택 정렬은 간단하지만 비효율적인 정렬 알고리즘 중 하나로, 배열에서 가장 큰 or 가장 작은 값을 찾아 현재 위치에 배치하는 과정을 반복하여 정렬된다.
순서는 다음과 같다.
1. 정렬되지 않은 부분에서 최솟값 or 최댓값 찾기
2. 현재 위치와 최솟 값 or 최대 값 교환
3. 다음 위치로 이동하며 반복
다음 그림과 같이 예시로 알아보자
5개의 정수 값을 가진 배열 Array가 존재한다.
이를 오름차순으로 왼쪽부터 최솟값을 찾아 정렬하고자 한다.
기본 형태
| 4 | 5 | 3 | 1 | 2 |
1회차
첫번 째 위치인 4를 기준
| 4 | 5 | 3 | 1 | 2 |
차례로 5, 3, 1, 2 와 비교
| 4 | 5 | 3 | 1 | 2 |
최솟값을 찾아 위치를 교환
| 4 | 5 | 3 | 1 | 2 |
1회차 완료
| 1 | 5 | 3 | 4 | 2 |
2회차
두번 째 위치인 5를 기준
| 1 | 5 | 3 | 4 | 2 |
차례로 3, 4, 2 와 비교
| 1 | 5 | 3 | 4 | 2 |
최솟값을 찾아 위치를 교환
| 1 | 5 | 3 | 4 | 2 |
2회차 완료
| 1 | 2 | 3 | 4 | 5 |
2회차만에 정렬되어 정렬된 배열은 다음과 같다.
| 1 | 2 | 3 | 4 | 5 |
전체 코드
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int [] arr = {6,4,2,1,3,5};
selectionSort(arr);
Arrays.stream(arr).forEach(System.out::println);
}
private static void selectionSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
int minIndex;
for(int i = 0; i < arr.length - 1; i++) {
minIndex = i;
for(int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
}
구현은 쉽고 직관적이긴 하나, 선택 정렬은 앞서 말했듯 입력 배열에 관계없이(2회차에 정렬이 되었더라도)
외부 반복문에서 n -1 회, 내부 루프에서 n - 1, n - 2, ..., 1번 비교함으로
시간복잡도는 항상 O(n^2) 으로 비효율적이다.
반응형
'알고리즘' 카테고리의 다른 글
| 플라비우스 요세푸스 순열 (2) | 2025.02.28 |
|---|---|
| [ 자료구조 ] 큐 ( Queue ) - JAVA (0) | 2025.02.26 |
| 스택 ( 자료구조 ) - JAVA (0) | 2025.02.04 |
| 소수 찾기 ( 에라토스테네스의 체 ) - JAVA (3) | 2024.09.04 |
