[알고리즘] 선택정렬 Selection Sort

[알고리즘] 선택정렬 Selection Sort

선택정렬의 종류

① 최소값 선택 정렬 (오름차순)

② 최대값 선택 정렬 (내림차순)

최소값 선택 정렬 (오름차순)

1. 정렬되지 않은 숫자 중에 가장 작은 숫자를 선택한다.

2. 선택한 가장 작은 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다.

3. 모든 숫자를 옮길 때까지 반복한다.

최소값 선택정렬

최대값 선택 정렬(내림차순)

1. 정렬되지 않은 숫자 중 가장 큰 숫자를 선택한다.

2. 선택한 가장 큰 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다.

3. 모든 숫자를 옮길 때까지 반복한다.

최대값 선택정렬

정확성 증명

i번째 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명

성능분석

n개가 있을 때 가장 큰/작은 수를 구하기 위해서 n-1 번의 비교가 일어남. => n(n-1) / 2

O(n²)

내가 구현한 소스 (JAVA)

public int[] solution(int n, int[] arr) { for(int i = 0; iarr[j]) { min = arr[j]; minIndex = j; } } //2.자리바꾸기 int tmp = arr[i]; arr[i] = min; arr[minIndex] = tmp; } return arr; }

반응형

from http://hodubab.tistory.com/350 by ccl(S) rewrite - 2021-09-06 06:01:37