노승현
선택 정렬 개념 정리 본문
Selection Sort [선택정렬]
선택 정렬은 말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.
데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며, 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다.
정렬 방법
선택 정렬의 전체적인 과정이다.
1. 주어진 리스트에서 최소값을 찾는다.
2. 최소값을 맨 앞 자리의 값과 교환한다.
3. 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다.
그림으로 보면 다음과 같다.
마지막 round9 를 안하는 이유는 앞 인덱스부터 순차적으로 정렬해나가기 때문에 N개의 데이터 중 N-1개가 정렬 되어있다는 것은 결국 마지막 원소가 최댓값이라는 말이고, 이는 정렬이 되어있다는 상태이므로 굳이 참조를 해줄 필요 없다.
선택 정렬의 장점 및 단점
[장점]
1. 추가적인 메모리 소비가 적다.
[단점]
1. 시간 복잡도가 높다.
2. 불안정 정렬이다.
불안정 정렬이란?
불안정 정렬은 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘이다.
대표적으로 선택정렬, 계수정렬, 퀵정렬이 있다.