using System;

using System.Linq;

public class Program

{

    public static void Main()

    {

        int[] arr = Enumerable.Range(1,10000).ToArray();

        // Console.WriteLine(InterpolSearch(arr, 9345));

        // Console.WriteLine(BinarySearch(arr, 300));

        var uArr = new int[]{ 1, 9, 10, 3, 8, 6, 4, 5, 2, 7};

        // BubbleSort(uArr);

        SelectionSort(uArr);

        foreach(var e in uArr) Console.Write($"{e}, "); 

    }

    static void SelectionSort(int[] arr){

        var n = arr.Length - 1;

        for(var i = 0; i < n; i++){

            var min = i;

            for(var j = i + 1; j <= n; j++){

                if(arr[j] < arr[min]) min = j;

            }

            if(i != min)

                (arr[i], arr[min]) = (arr[min], arr[i]);

        }

    }

    static void BubbleSort(int[] arr){

        var n = arr.Length - 1;

        for(var i = 0; i < n; i++){

            for(var j = i + 1; j <= n; j ++){

                if(arr[i] >  arr[j]){

                    (arr[i], arr[j]) = (arr[j], arr[i]);

                    // var temp = arr[j];

                    // arr[j] = arr[i];

                    // arr[i] = temp;

                }

            }

        }

    }

    public static int InterpolSearch(int[] arr, int value)

    {

        var low = 0;

        var high = arr.Length - 1;

​

        while (value >= arr[low] && value <= arr[high] && low <= high)

        {

            var mid = low + (high - low) / (arr[high] - arr[low]) * (value - arr[low]);

            // var mid = low + (high - low) * (value - arr[low]) / (arr[high] - arr[low]);

​

            Console.WriteLine($"prob: {mid}");

            if (arr[mid] == value) return mid;

​

            if (value > mid) low = mid + 1;

            else high = mid - 1;

        }

        return -1;

    }

    static int BinarySearch(int[] arr, int search){

        var low = 0;

        var high = arr.Length - 1;

        while(low <= high){

            int mid = (low + high) / 2;

            Console.WriteLine($"Mid: {mid}");

            var midValue = arr[mid];

            if(midValue == search) return mid;

            if(midValue < search){

                low = mid + 1;

            }else{

                high = mid - 1; 

            }

            // Console.WriteLine($"low: {low}");

            // Console.WriteLine($"High: {high}");

        }

        return -1;

    }

}