読者です 読者をやめる 読者になる 読者になる

ソートせずに小さい方から n 番目を見つけ出す

stackoverflow から 「ソートをせずに、配列要素の値の小さい方から n番目を見つけ出す」 C Program to search n-th smallest element in array without sorting? - Stack Overflow Programming Pearls にこの種の話があったと思う。答えを見る前にちょっと考えてみてちょんまげ。

ときどきの雑記帖 i戦士篇 2009年6月(下旬) 問題

アルゴリズムを考えるのはだるいから、欲しいものを記述する。それが SQL

DECLARE @n AS int;
SET @n = 3;

WITH
  Input(n) AS (
    SELECT 40
    UNION ALL SELECT 10
    UNION ALL SELECT 60
    UNION ALL SELECT 20
    UNION ALL SELECT 30
    UNION ALL SELECT 50
  )
SELECT
    L.n
FROM
    Input L
      INNER JOIN Input R ON L.n >= R.n
GROUP BY
    L.n
HAVING
    COUNT(*) = @n

素直に書くとこんな感じかなー。
効率?なにそれおいしいの?