AISD - Lab2.3

using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            float[] arr= { 1, 300, 2, 200, 1 };
            int k = 0, n;
            n = arr.Length;
            median(arr, n, ref k);
            Console.WriteLine(arr[k]);
            Console.ReadKey();
        }

        private static void split(float[] a, int n, float x, ref int i, ref int j)
        {
            do
            {
                while (a[i] < x) i++;
                while (x < a[j]) j--;

                if (i <= j)
                {
                    float t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                    i++; j--;
                }
            } while (i <= j);
        }
    // O(2n)?
        private static void median(float[] a, int n, ref int k)
        {
            int L = 0;
            int R = n - 1;
            k = n / 2;
            int i; int j;
            while (L < R)
            {
                float x = a[k];
                i = L; j = R;
                split(a, n, x, ref i, ref j);
                if (j < k) L = i;
                if (k < i) R = j;
            }
        }
    }
}