선택 정렬(Selection Sort)

선택 정렬이란?

선택 정렬(Selection Sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식입니다.

제자리 정렬 알고리즘 중의 하나로, 나열된 것 중에 가장 작은 혹은 큰 것을 선택해 앞 또는 끝으로 보내는 작업을 반복하면 크기 순서대로 정렬이 됩니다.

쉽게 다음 과정을 기억하면 될 것 같습니다!

1. 앞 (처음 인덱스) 부터 값을 하나 선택합니다.

2. 선택한 값의 이후에 있는 원소들 중 가장 작은 값을 찾습니다.

3. 찾은 인덱스와 1번에서 선택한 인덱스를 바꿔줍니다.

이제 시간복잡도를 구해보겠습니다. (빅오 표기법을 사용합니다.)

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

첫 루프에서의 비교횟수는 1 ~ n - 1 => n-1이 될 것 이고,

두번째 루프에서의 비교횟수는 2 ~ n - 1 => n-2가 될 것 입니다.

이런 식으로  작업이 반복되다 보면 

(n - 1) + (n - 2) + (n - 3) + ..... + 2 + 1 => n(n - 1) / 2

즉, O(n^2)의 시간복잡도를 가지게 됩니다.

자 이제, 코드로 표현해보도록 하겠습니다. (언어는 JS 입니다.)

지금까지 선택정렬(Selection Sort)를 알아보았습니다.

혹시 궁금한 점이나 수정사항이 있으면 바로 말씀해주세요.

감사합니다!