일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- 백준 1105번
- java
- 조합
- 삼성전자DX알고리즘
- 삼성 b형
- 정렬
- 백준 1010번
- 백준 2589번
- 백준 1011번
- 분할정복
- Greedy
- 다리 놓기
- Inversion Counting
- mergesort
- BOJ
- 버블정렬
- 자바
- 백준 10090번
- 삽입 정렬
- 구현 알고리즘
- 알고리즘 특강
- 다이나믹 프로그래밍
- 선택 정렬
- 삼성전자 역량테스트
- brute-Force
- 백준 14499번
- 알고리즘
- 백준
- 주사위 굴리기
- C/C++
Archives
- Today
- Total
Lavine's Dev Site
[알고리즘 개념] 정렬 알고리즘 - 선택 정렬 (Selection Sort) 본문
반응형
선택 정렬 (Selection Sort)
정렬 순서 (오름차순 정렬 기준)
- 주어진 리스트에서 최소 값을 찾는다.
- 최소 값을 유효 범위 내에서 맨 앞의 값과 swap한다.
- swap된 위치를 제외 한 나머지 공간이 1개가 될때까지 1 ~ 2를 반복한다.
예시
장점
- 구현이 쉽고 이해하기 쉽다.
- In-place Sorting Algorithm
- 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n)
단점
- O(n2)의 시간복잡도
- 불안정 정렬 (Unstable sorting)
- 중복 값 순서 보장 못함
시간 복잡도
- 외부 루프: (n-1)번 반복
- 최솟값 탐색: n-1, n-2, n-3, ... ,2, 1
- T(n) = 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2 ∈ O(n2)
Code (C/C++)
#include <stdio.h>
#define LENGTH 5
// Selection Sort
void selectionSort(int* arr){
// 맨 마지막 원소는 알아서 정렬이 되기 때문에 l-2까지 반복
for(int cur = 0; cur < LENGTH -1 ; cur++) {
int min = cur;
// 최소값 찾기
for(int j = cur + 1; j < LENGTH; j++) {
if(arr[min] > arr[j])
min = j;
}
// 최소값이 자기 자신인 경우 swap이 필요없다.
if(min == cur)
continue;
int tmp = arr[min];
arr[min] = arr[cur];
arr[cur] = tmp;
}
}
int main() {
int arr[LENGTH] = {7,4,2,9,5};
printf("Before Sorting: ");
for(int i = 0; i<LENGTH; i++) {
printf("%d ", arr[i]);
}
printf("\n");
selectionSort(arr);
printf("After Sorting: ");
for(int i = 0; i<LENGTH; i++) {
printf("%d ", arr[i]);
}
}
Code (Java)
public class sorting {
public static void main(String[] args) {
int[] arr = {7,4,2,9,5};
System.out.print("Before Sorting: ");
printArr(arr);
selectionSort(arr);
System.out.print("After Sorting: ");
printArr(arr);
}
// Print Array
static void printArr(int[] arr) {
int l = arr.length;
for(int i = 0; i<l; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// Selection Sort
static void selectionSort(int[] arr) {
int l = arr.length;
// 맨 마지막 원소는 알아서 정렬이 되기 때문에 l-2까지 반복
for(int cur = 0; cur < l-1; cur++) {
int min = cur;
// 최소값 찾기
for(int j = cur + 1; j < l; j++) {
if(arr[min] > arr[j])
min = j;
}
// 최소값이 자기 자신인 경우 swap이 필요없다.
if(min == cur)
continue;
// swap
int tmp = arr[min];
arr[min] = arr[cur];
arr[cur] = tmp;
}
}
}
'Algorithm > 알고리즘 개념' 카테고리의 다른 글
[알고리즘 개념] 정렬 알고리즘 - 버블 정렬 (Bubble Sort) (0) | 2022.09.30 |
---|---|
[알고리즘 개념] 정렬 알고리즘 - 삽입 정렬 (Insertion Sort) (1) | 2022.09.25 |
Comments