시간을 기록하다

by 기록자

선택 정렬(Selection Sort)

초보의 알고리즘 2008/07/21 11:40

선택 정렬이란 데이터를 정렬하기 위한 방법 중 가장 단순한 방법이라 할 수 있다.
선택 정렬에서는 비교 대상이 되는 위치와 그 이후에 나타난 데이터들의 값을 비교하여 더 작은 데이터와 교체함으로써 정렬을 수행하게 된다.
이해를 돕기 위해 아래 그림을 보도록하자.

그림에서 보면 우선 [0] 번 데이터는 [1]~[n-1]까지의 데이터와 비교해 가면서 [0]번 데이터보다 작은 값이 있을 경우 스왑한다. 그렇게 [n-1]까지의 비교가 끝나면 [0]번에는 [0]~[n-1]의 데이터 중에서 가장 작은 값이 들어가 있게된다. 이후에는 [1] 번 데이터를 [2]~[n-1]까지 같은 방식으로 비교 및 스왑 과정을 거치게 된다.
이와같이 선택 정렬의 경우 비교 횟수가 항상 n(n-1)/2 이므로 상당히 비효율적인 방법이라 할 수 있지만 데이터를 정렬하는 방법에 있어서 가장 기본적인 방법이므로 기본적으로 알고 있어야 하는 방법이다.
아래는 선택정렬의 소스코드이다.

Sort_selection.c