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

 선택 정렬 알고리즘은 주변에서 손쉽게 접할 수 있는 정렬 알고리즘 중의 하나입니다.

 선택 정렬 알고리즘은 데이터의 처음부터 끝까지 훑어 가장 작은 값을 기존의 첫 번째 데이터와 바꾸는 식으로 정렬하는 알고리즘입니다.

다음은 선택 정렬 알고리즘의 코드와 출력 결과입니다.

 선택 정렬 알고리즘의 시간복잡도는 O(N^2)으로 표현할 수 있습니다. SelectionSort 함수에서 이중 for문을 사용하여 정렬하였습니다.

 위 코드를 말로 풀어쓰면 이렇게 됩니다.

"N개의 데이터가 있는 선택 정렬 알고리즘은 2개의 반복문을 사용해 N^2 / 2회의 비교를 한다. 그런데 데이터가 정렬되지 않은 부분에서 정렬된 쪽으로 이동하는 횟수는 N번이다. 왜냐하면 일단 정렬되지 않은 부분에서 가장 작은 값을 갖는 데이터를 찾은 후에 데이터를 교환하기 때문이다."

이렇게 보았을 때, 우리는 이 알고리즘의 이름이 왜 '선택'인지 알 수 있습니다. SelectionSort 함수에서 i를 이용한 for문에서 정렬될 데이터의 위치를 선정해 줍니다. 그러면 그 안에 j를 이용한 for문이 최솟값을 '선택'해서 기존의 데이터와 교환시킵니다. 그래서 이름이 선택 정렬입니다.

 선택 정렬 알고리즘은 정렬할 데이터 하나 하나의 크기가 큰 경우에 유용합니다. 비교 횟수는 큰 편이지만 데이터 교환 횟수는 N번이면 충분합니다. 즉, 교환 횟수가 상대적으로 적기 때문에 다른 알고리즘에 비해 많이 유용하다고 볼 수 있습니다.