정렬, 선택정렬 알고리즘
Nov 28, 2018 조회수 327
알고리즘설명
<img alt="" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/RYUI62181224235510.PNG" style="width:240px">
전체 배열에서 가장 작은 숫자를 찾아 **"선택"**하여 첫 번째 위치에 둔다.
그후 두번째 부터 마지막까지의 배열에서 두 번째로 작은 숫자를 찾아 **"선택"**하여 두번째 위치에 둔다.
이를 반복한다.
<br/>
<span style="color:#000000">복잡도
<span style="color:#000000">첫번째에는 n번을 순회한다.
<span style="color:#000000">두번째에는 n-1번을 순회한다.
<span style="color:#000000">세번째에는 n-2 번을 순회한다.
<span style="color:#000000">..
<span style="color:#000000">마지막에는 n-(n-1)을 순회한다.
<span style="color:#000000">모든 시간 복잡도는 n+ (n-1) + (n-2) + ..... + (n-(n-1)번이므로 n*(n-1)/2가 된다.
<span style="color:#000000">복잡도는 O(N^2)이다.
<br/>
장단점
데이터 이동이 비교적 적은 것이 장점이다.
단점은 안정성을 만족하지 않는다. 즉 같은 값이 있을 경우 상대적 위치가 변경 될 수 있다.
<br/>
소스코드
public class SelectionSort {
public void sort(int[] arr) {
int n = arr.length;
int min, temp;
for (int i = 0; i < n - 1; i++) {
min = i;
for (int j = i; j < n; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
public static void main(String[] args) {
int arr[] = { 10, 8, 7, 3, 2, 15 };
new SelectionSort().sort(arr);
System.out.print(Arrays.toString(arr));
}
}
<br/>
'정렬, 선택정렬 알고리즘' 관련된 다른글
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.