선택 정렬(selection sort)>

<선택 정렬(selection sort)>

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 

 

[수행 방법]
1. 전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다.
2. 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환한다.
3. 그 다음에는 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환한다.
4. 이 과정을 반복하면서 정렬을 완성한다.

 

ex) 정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 선택 정렬 방법으로 정렬하는 과정을 보여라.

 

① 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69와 자리 교환

② 두 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 10과 자리 교환

③ 이런식으로 반복한다.

 

④ 일곱 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 31을 선택하여 기준 위치에 있는 원소 31과 자리 교환. (제자리)

선택 정렬을 분석해보자.

1. 메모리 사용공간 - n개의 원소에 대하여 n개의 메모리 사용
2. 비교횟수
1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교
2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교
i 단계 : i 번째 원소를 기준으로 n-i개의 원소 비교

전체 비교횟수는 n(n-1)/2이다. 

 

즉, 어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n2)이 된다.

 

[선택 정렬 코드]

Copyrightⓒ2014 By 한빛아카데미(주)