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

선택 정렬(Selection Sort)이란?

제자리 정렬(in-place sorting) 알고리즘의 하나이다.
👉 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

데이터 하나를 기준으로 다른 데이터와 비교하여 가장 작거나 큰 데이터와 자리를 바꾸는 식으로 반복 비교하는 정렬.
데이터의 갯수가 N개라면 N-1회 반복문을 돌게 된다.

시간 복잡도는 O(n^2)가 된다.

n개 원소에 대해 n개 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이다.

선택 정렬(Selection Sort)의 용도

👍 선택 정렬이 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여준다.

👎 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점도 있다.

Reference

• 코딩팩토리
• heejeong Kwon (tistory)