- Today
- Total
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 동적할당
- Java
- C++
- 연결리스트
- 배열
- 파이썬
- 정렬
- 자바
- 공유대학
- 알고리즘
- til
- 구글 로그인
- python
- 로그인
- sql
- 안드로이드
- 프로그래머스
- oauth
- 컴퓨터공학과
- 자료구조
- 안드로이드 스튜디오
- 코딩테스트
- C언어
- Firebase
- 프로그래밍 입문
- 비주얼 베이직
- firebase google
- 백준
- android studio
Archives
코딩하는 해달이
[정렬] 선택 정렬 본문
선택 정렬이란?
선택 정렬은 제자리 정렬(In- place sorting) 알고리즘의 하나로 원소를 넣을 위치는 이미 정해져있으며, 어떤 원소를 넣을지 선택하는 알고리즘입니다.
선택 정렬 과정
작업 순서
- 리스트를 순회하며 가장 작은 요소 찾기
- 가장 작은 요소와 첫 번째 요소 교환
- 리스트의 다음 위치로 이동
- 반복
시간 복잡도
최악, 평균, 최선 모든 경우에 O(n^2)의 시간 복잡도를 가집니다.
공간 복잡도
O(1): 제자리 정렬 알고리즘으로 추가적인 메모리 사용이 거의 없습니다.
장점
구현이 간단하고 이해하기 쉽습니다.
단점
시간 복잡도가 O(n^2)이기 때문에, 데이터의 크기가 큰 경우 비효율적입니다.
코드
public void selectionSort(int[] array) {
int n = array.length;
// 배열을 순회하면서 정렬
for (int i = 0; i < n - 1; i++) {
// 현재 범위에서 가장 작은 원소의 인덱스를 찾습니다.
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
private void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
반응형
'개인 공부 > 알고리즘&자료구조' 카테고리의 다른 글
[정렬] 삽입 정렬 (0) | 2024.10.30 |
---|---|
[정렬] 버블 정렬 (0) | 2024.10.28 |
[알고리즘] 위상 정렬 (0) | 2024.09.20 |
[알고리즘] 임의의 좌표가 원을 기준으로 어디에 위치하고 있는지 확인 (0) | 2023.02.24 |
[자료구조] 자료구조 수업 과제 2 (0) | 2022.11.19 |
Comments