[자료구조] 선택정렬 알고리즘 ( Selection_Sort Algorithm )

일상에서 우리는 정렬 문제를 굉장히 많이 접합니다. 마구 섞여 있는 카드를 번호 순서로 오름차순으로 정렬을 하고자 하는 문제를 해결 한다고 해봅시다. 가장 보편적인 방법은 가장 작은 숫자의 카드를 찾은 후 옆에 차례대로 배열을 하기 시작하는 겁니다. A 카드를 찾아서 옆에 놓고 2 카드를 찾아서 그 옆에 놓고 그 다음엔 3.. 그다음엔 4.. 이런식으로 하나씩 작은 숫자를 찾아서 정렬된 배열을 만들어 나가는 방법입니다. 이런 방법을 선택 정렬이라고 합니다. 


1. 선택 정렬 알고리즘 
 선택 정렬 알고리즘을 서술하면 다음과 같습니다. 우선 int 형의 배열을 정렬하는 것으로 하고 정렬할 대상의 갯수는 n개로 하겠습니다.

* Selection Sort Algorithm
1. i = 0
2. i가 n - 2가 되면 종료
3. 배열의 i항부터 n - 1항까지 조사를 하여 최소값을 저장
4. 저장한 최솟값과 i항과 교환
5. i 를 1 증가시키고 2단계로 돌아간다.

거의 본능적인 알고리즘과 같다고 보시면 됩니다. 그럼 직접 정렬되는 과정을 보면서 설명을 해드리겠습니다. 먼저 정렬될 대상이 되는 문자열은 HACKINDATASTRUCTSTRUCTSTUDY 라는 문자열을 정렬한다고 하겠습니다.

 그러면 선택정렬 알고리즘은 다음과 같은 순서로 정렬을 하기 시작 할 것입니다.

 21글자를 정렬하는데 21한 단계가 필요함을 볼 수 있습니다.

* 선택정렬의 분석
 알고리즘의 분석은 두가지를 주로 분석합니다. 비교 횟수와 교환 횟수가 그것입니다. 선택정렬은 대다수의 시간이 비교 시간에 소요됩니다. i 번째 단계 ( 0 번째 단계에서 n - 1단계 까지 ) 에서는 비교 횟수가 n - 1 번입니다. 풀어서 말하면 n개의 요소를 정렬하는데에 첫번째 단계에는 n - 1 번, 그 다음에는 n - 2 번 ... 뒤에서 2번째에는 2번, 마지막은 1번 비교를 합니다. 1,2,3 ... n-1 을 더하는 공식은 n(n-1)/2이므로 선택정렬은 n(n-1)/2 번의 비교횟수를 갖게 됩니다.
 다음으로 교환 횟수인데, 최악의 경우 n 번의 교환을 하게 됩니다 .( 각 단계에서 한번의 교환만 일어나기 때문이죠. ) 최선의 경우는 0번의 교환을 하게 됩니다.

 이 처럼 선택정렬의 가장 큰 장점은 최악의 경우와 최선의 경우의 차이가 그리 크지 않다는 점입니다. 시간 복잡도는 O(N * N)을 갖게 됩니다. 또 한 교환 횟수가 적기 때문에 레코드의 크기가 큰 데이터를 정렬 할 때 힘을 발휘 할 수 있습니다.

* 선택정렬의 개선
 알고리즘 자체가 굉장히 단순하기 때문에, 개선의 여지는 없지만 For 문으로 이루어진 반복문의 내부를 기계어나 어셈블리어로 작성을 한다면 조금더 빨라 질 수 있습니다.