Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 자바스크립트
- 데이터베이스
- Spring Security
- javascript
- baekjoon
- 플러터
- Oracle
- 스프링 부트 쇼핑몰 프로젝트 with JPA
- spring
- DB
- 리눅스
- Java
- python
- CS
- springboot
- 파이썬
- 시큐리티
- backjoon
- JPA
- postgresql
- CS지식
- 자료구조
- 백준
- 네트워크
- 데이터
- 스프링
- 스프링부트
- 프로그래머스
- Flutter
- 자바
Archives
- Today
- Total
Jin's Dev Story
[알고리즘] 선택 정렬(Selection Sort) 본문
선택 정렬
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
- 최소값을 찾아 정렬하는 방식
- 평균과 최악 모두 수행 시간 복잡도는 O(n2)
Process (Ascending)
- 주어진 배열 중에 최소값을 찾음
- 그 값을 맨 앞에 위치한 값과 교체 (pass)
- 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체
void selectionSort(int[] arr) {
int indexMin, temp;
for (int i = 0; i < arr.length-1; i++) { // 1.
indexMin = i;
for (int j = i + 1; j < arr.length; j++) { // 2.
if (arr[j] < arr[indexMin]) { // 3.
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-1) => n-1
- 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
- (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
최선, 평균, 최악의 경우 시간복잡도는 O(n^2)
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)
장점
- Bubble sort와 마찬가지로 알고리즘이 단순
- 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적
- Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 => 제자리 정렬(in-place sorting)
단점
- 시간복잡도가 O(n^2)으로, 비효율적
- 불안정 정렬(Unstable Sort)
'CS 지식 > [알고리즘]' 카테고리의 다른 글
[알고리즘] 브루트포스 (0) | 2023.10.20 |
---|---|
[알고리즘]합병 정렬(병합 정렬(Merge Sort)) (0) | 2023.07.18 |
[알고리즘] 버블 정렬(Bubble Sort) (0) | 2023.07.18 |
[알고리즘]퀵 정렬(Quick Sort) (0) | 2023.07.18 |
[알고리즘]힙 정렬(Heap Sort) (0) | 2023.07.18 |