C# 配列の要素からk番目の値を求めるアルゴリズム

配列の要素からk番目の値（k番目に小さい値）を求める。
k番目の「k」はもちろんゼロ起源である。

using System;

public class Program
{
    private static void Swap(ref Int32 x, ref Int32 y)
    {
        Int32 tmp = x;
        x = y;
        y = tmp;
    }

    private static Int32 Partition(Int32[] a, Int32 l, Int32 r)
    {
        Int32 i = l - 1;
        Int32 j = r;
        Int32 v = a[r];

        for (; ; )
        {
            while (a[++i].CompareTo(v) < 0)
            {
            }
            while (v.CompareTo(a[--j]) < 0)
            {
                if (i == j)
                {
                    break;
                }
            }
            if (i >= j)
            {
                break;
            }
            Swap(ref a[i], ref a[j]);
        }
        Swap(ref a[i], ref a[r]);
        return i;
    }

    public static void Select(Int32[] a, Int32 l, Int32 r, Int32 k)
    {
        while (r > l)
        {
            Int32 i = Partition(a, l, r);
            if (i >= k)
            {
                r = i - 1;
            }
            if (i <= k)
            {
                l = i + 1;
            }
        }
    }

    public static void Main()
    {
        Int32[] a = { 9, 6, 7, 5, 3, 2, 1, 4, 8, 0 };//要素0〜9をシャッフルした配列
        Int32 index;

        //配列aから0番目（0番目に小さい）の値を求める
        index = 0;
        Select(a, 0, a.Length - 1, index);
        Console.WriteLine("{0}番目の値は, {1}", index, a[index]);


        //配列aから3番目（1番目に小さい）の値を求める
        index = 3;
        Select(a, 0, a.Length - 1, index);
        Console.WriteLine("{0}番目の値は, {1}", index, a[index]);


        //配列aから9番目（9番目に小さい）の値を求める
        index = 9;
        Select(a, 0, a.Length - 1, index);
        Console.WriteLine("{0}番目の値は, {1}", index, a[index]);
    }
}

実行結果

0番目の値は, 0
3番目の値は, 3
9番目の値は, 9

※実行後に、配列aの順序が変わります。