[알고리즘] 선택(Selection) 알고리즘

선택 알고리즘 이란

입력 값들 가운데 k 번째로 작은 원소를 찾는 알고리즘이다.

 

입력된 배열 중, k번째로 작은 원소의 값을 구하려면,

퀵 정렬 알고리즘의 partition()함수를 호출한다. 이 함수의 리턴값을 통해, 찾으려는 k 의 인덱스가 

피봇의 왼쪽에 있는지 오른쪽에 있는지 판별할 수 있다.

pivot < k ) 찾는 원소는 오른쪽 부분 배열에 있는 것이다.

pivot > k ) 찾는 원소는 왼쪽 부분 배열에 있는 것이다.

pivot == k ) 찾는 원소가 곧 pivot이다.

k가 어디있는지 알게 되면, 해당 부분 배열에 대해 selection 알고리즘을 recursive하게 수행한다.

 

pseudo code

patition(list[], p, r){
x <- list[r];
i <- p-1;
for(j<-p) to r-1
	if(list[j] <= x) then list[++i] <-> list[j];
list[i+1] <-> list[r];
return i+1;
}

selection(list[], p, r, i){
// 배열 list[p...r]에서
// i번째 작은 원소를 찾는다.

if(p == r) then return list[p]; // 배열 list의 원소가 하나 뿐인 경우

q <- partition(list,p,r); //퀵 정렬 알고리즘의 partition 함수 호출
k <- q - p +1; //기준이 되는 피봇 k가 ???

if(i < k) then return select(list, p, q-1, i); //찾는 원소가 왼쪽 배열에 있는 경우
else if(i == k)
else return select(list, q+1, r, i-k);
}