선택 정렬 (Selection Sort)

a[] = ( 3, 2, 5, 1, 4 )

void Selectionsort::sorting()

{

int i, j, min;

for(i=1;i<=ARRSIZE;i++)

{

min=i;

for(j=i+1;j<=ARRSIZE;j++)

if(buf[j]<buf[min]) min=j;

swap(min,i);

}

SelectionSort(a[], n)

for (i ← 1; i < n; i ← i + 1) do {

배열 a[i], … , a[n] 중에서 가장 작은 원소 a[k]를 선택;

a[k]를 a[i]와 교환;

}

end SelectionSort()

u N 개의 원소 각각에 대해 N-1 번의 비교

u 전체 비교 횟수 N(N-1)/2

u 전체 시간 복잡도 O(N 2)

u 큰 레코드와 작은 키를 가지는 화일의 경우 효율적임

제이콥케이