728x90
➡️Selection_Sort(선택 정렬)이란
- Selection_Sort(선택 정렬)은 현재 위치에 들어갈 데이터를 찾아서 선택하는 알고리즘이다.
- 데이터를 비교하면서 찾기때문에 비교정렬이고 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬이기도 하다.
➡️Selection_Sort(선택 정렬)의 과정
- 주어진 배열에서 최솟값을 찾는다.
- 최소값을 맨 앞자리의 값과 교환한다.
- 맨 앞 자리는 이미 최솟값이 있기때문에 맨 앞 자리를 제외하고 나머지 값들 중 최솟값을 찾아 위과정을 반복한다.
➡️Selection_Sort(선택 정렬) 장단점
장점
- 선택정렬 또한 버블정렬과 마찬가지로 구현이 쉬운편에 속하는 정렬법이다.
- 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 효율적으로 사용될 수 있다.
- 거품 정렬과 비교 했을 때, 똑같이 시간복잡도는 O(N^2)이지만, 구현해보면 버블 정렬보다는 빠른 편이다.
단점
- 시간 복잡도가 O(N^2)이기 때문에 시간이 오래 소요된다.
- 안정 정렬이 아니다.
➡️Selection_Sort(선택 정렬) 구현코드
|
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
32
|
public class SelectionSort {
public static void selectionSort(int []arr){
selection_sort(arr,arr.length);
}
private static void selection_sort(int [] arr,int size){
for(int i =0; i< size-1; i++){
int min_index = i;
for(int j = i +1; j<size ; j++){
if(arr[j] < arr[min_index]){
min_index = j;
}
}
swap(arr,min_index,i);
}
}
private static void swap(int []arr, int i ,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
|
cs |
아래는 위와는 살짝 다른 코드이다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
public class Selectionsort2 {
public void selectionSort(int []arr){
int size = arr.length;
int temp;
int min;
for(int i=0; i<size -1; i++){
min =i;
for (int j = i+1; j<size; j++){
if(arr[min]>arr[j]){
min = j;
}
}
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
Selectionsort2 s = new Selection_sort2();
int arr[] = {4,7,8,9,1,4,2,5};
s.selectionSort(arr);
for (int i = 0; i<arr.length; i++){
System.out.print(" " +arr[i]);
}
}
}
|
cs |
REFERENCE
728x90
'Dev > 알고리즘 ,자료구조' 카테고리의 다른 글
| [Algorithm]BeakJoon_1330 (0) | 2021.07.18 |
|---|---|
| Insertion_Sort(삽입 정렬) (0) | 2021.06.30 |
| Bubble_Sort(거품 정렬)+JAVA로 구현 (0) | 2021.06.28 |
| 스택(Stack) JAVA로 구현 (0) | 2021.04.24 |
| 자료구조_배열(Array) (0) | 2021.03.11 |