데이터를 특정한 기준에 따라 순서대로 나열하는 것
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
선택 정렬은 N번 만큼 가장 작은 수를 맨 앞으로 보내야 한다.
N + (N-1) + (N-2) + ... + 2
이는 (N^2 + N - 2)/2 로 표현할 수 있는데, 빅오 표기법에 따라 O(N^2)가 된다.
처리되지 않은 데이터를 하나씩 골라 매번 적절한 위치를 계산하여 삽입한다.
선택 정렬에 비해 구현 난이도가 높은 편이지만, 더 빠르게 동작한다.