Selection : Find Kth Smallest ( K=N/2, median )
　 　
　
Recursive No recursive k:global
Select( l, r ,k )　　

if r > l then {　　

i := partition( l, r );　　

if i > l+k-1 then　　

Select( l, i-1, k );　　

if i < l+k-1 then　　

Select( i+1, r, k-i );　　

}

 Select(k) l := 1; r := N;　　

while r > l do {　　

i := partition( l, r );　　

if i >= k then　　

r := i-1;　　

if i <= k then　　

l := i+1;　　

}
　
　
　 　 　 　 　
k↓
 　
　 　 　
l↑
k↑
 　
i↑
 　 　
r↑
　

Example:
　
　
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 　
　
A
S
O
R
T
I
N
G
E
X
A
M
P
L
E
 　
　
A
A
E
E
T
I
N
G
O
X
S
M
P
L
R
 　
　 　 　 　 　
L
I
N
G
O
P
M
R
X
T
S
 　
　 　 　 　 　
L
I
G
M
O
P
N
 　 　 　 　 　
　 　 　 　 　 　 　 　
M
 　 　 　 　 　 　 　 　
　

T = N2　　　　　 worst

N+klog(N/k)　　　 average