선택정렬(Selection Sort) 알고리즘

선택정렬 알고리즘의 개념

제자리(in-place sorting) 알고리즘의 한 종류이며, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고 어떤 원소를 넣을지 선택하는 알고리즘이다.

선택정렬 알고리즘의 과정

1. 주어진 배열 원소들 중 최솟값을 찾는다.
2. 최솟값을 배열의 맨 앞에 있는 원소와 교체한다.
3. 맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체한다.

선택정렬 알고리즘 Java 코드

선택정렬 알고리즘의 시간 복잡도

데이터의 개수가 n개일 때,
1 pass에서의 비교횟수: 1 ~ (n-1) --> n-1
2 pass에서의 비교횟수: 2 ~ (n-1) --> n-2
.
.
.
(n-1)+(n-2)+ ... +2+1 = n(n-1)/2

최선, 평균, 최악의 경우 시간복잡도는 O(n^2)로 동일하다.

선택정렬의 장점

› 알고리즘이 단순하다.
› 정렬을 위한 비교횟수는 많지만, 버블정렬에 비해 교환횟수가 적기 때문에 많은 교환이 일어나야 하는 자료에서 비교적 효율적이다.
› 제자리 정렬 방식이므로 다른 메모리 공간을 필요로 하지 않는다.

선택정렬의 단점

› 시간복잡도가 O(n^2)으로, 비효율적이다.
› 불안정 정렬(Unstable Sort)이다.

출처

https://devuna.tistory.com/28
https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC