7. Quicksort — Order Statistics Index   <<   >>
 

S1←{⍵⌷⍨⍺⌷⍋⍵}

S←{
  s←⍵ ⍺⍺ p←⍵⌷⍨?≢⍵
  ⍺<  +/b←0>s:⍺ ∇ b⌿⍵
  ⍺<m←+/b←0≥s:p
  (⍺-m) ∇ (~b)⌿⍵
}
 

Sn←{
  p←⍵⌷⍨?≢⍵
  ⍺<  +/b←⍵<p:⍺ ∇ b⌿⍵
  ⍺<m←+/b←⍵≤p:p
  (⍺-m) ∇ (~b)⌿⍵
}

   x←?1e6⍴1e9

   cmpx '4e5 S1 x' '4e5 -S x' '4e5 Sn x'
  4e5 S1 x → 6.19E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  4e5 -S x → 1.27E¯2 | -80% ⎕⎕⎕⎕⎕⎕                        
  4e5 Sn x → 9.38E¯3 | -85% ⎕⎕⎕⎕⎕