[자료구조] 선택정렬

선택정렬이란?

제자리 알고리즘의 하나로 제일 작은 값을 "선택"해서 앞으로 보내는 정렬

1. 주어진 리스트 중에 최소값을 찾음
2. 그 값을 맨 앞에 위치한 값과 교체
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체

• 가장 작은 것을 선택하는데 N번, 앞으로 보내는데 N번의 연산으로 O(N²)의 시간 복잡도를 가짐
• 가장 작은 수를 앞으로 보내줄 때, 선택된 수가 현재 있는 위치와 맞바꿈 이중포문을 이용해 정렬
• 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있음

 

이미지 출처: wikipedia

 

 

 

참고 | Wikipedia, Fast Campus 컴퓨터 공학 전공 필수