선택 정렬 (Selection Sort)

Jace·2023년 1월 9일

선택 정렬은 제자리 정렬 중 하나이다. 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 성능 상의 이점이 있다.

매 반복 pass 마다 가장 크거나 작은 자료를 선택하고, 해당 반복 패스가 끝날 때 선택한 자료를 맨 앞이나 맨 뒤로 옮기는 과정을 수행한다. 전체 자료에 대해 이러한 과정을 반복적으로 수행.

데이터의 개수가 n개라고 했을 때,

n개의 주어진 배열을 정렬하는데 최선/평균/최악 O(n^2) 만큼의 시간이 걸린다.

제자리 정렬 알고리즘이므로, O(n)

알고리즘이 단순하다.

데이터량이 적을때는, 비교적 좋은 성능을 보임

배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

시간복잡도가 O(n^2)으로, 비효율적이다.

안정적이지 못한 정렬 (nonstable sort) - 정렬 전 입력 자료 순서가 유지되지 못함

당신이 인생의 주인공이기 때문이다 . 그사실을 잊지마라 . 지금까지 당신이 만들어온 의식적 그리고 무의식적 선택으로 인해 지금의 당신이 있는것이다 . – 바바라 홀

오늘한줄.