using System;

namespace Sorts
{
    public class Class1
    {
        public static void BubbleSort(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                for (int j = 0; j < array.Length - i - 1; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        int t = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = t;
                    }
                }
            }
        }

        public static void Quicksort(int[] array, int lo, int hi)
        {
            if (lo != hi)
            {
                int l = lo;
                int h = hi;
                while (l < h)
                {
                    while (array[l] < array[(l + h) / 2])
                        l++;
                    while (array[h] > array[(l + h) / 2])
                        h--;
                    if (l <= h)
                    {
                        int t = array[h];
                        array[h] = array[l];
                        array[l] = t;
                    }
                }

                Quicksort(array, lo, (l + h) / 2);
                Quicksort(array, (l + h) / 2 + 1, hi);
            }
            else
            {
                return;
            }
        }

        public static void SelectionSort(int[] array)
        {
            for (int j = 0; j < array.Length; j++)
            {
                int min = array[j];
                int minindex = j;
                for (int i = j; i < array.Length; i++)
                {
                    if (array[i] < min)
                        minindex = i;
                }

                int t = array[j];
                array[j] = array[minindex];
                array[minindex] = t;
            }
        }


        public static void InsetionSort(int[] array)
        {
            int key;
            for (int j = 1; j < array.Length; j++)
            {
                key = array[j];
                int i = j - 1;
                while (i >= 0 && array[i] > key)
                {
                    array[i + 1] = array[i];
                    i--;
                }

                array[i + 1] = key;
            }
        }

        public static void Heapify(int[] a, int l)
        {
            for (int i = (int) (Math.Log(2, a.Length) - 1); i > 1; i--)
            {
                if (2 * i < a.Length)
                {
                    if ((a[2 * i] > a[i]) || ((a[2 * i] > a[2 * i + 1])))
                    {
                        int t = a[2 * i];
                        a[2 * i] = a[i];
                        a[i] = t;
                    }
                }

                if (2 * i + 1 < a.Length)
                {
                    if ((a[2 * i + 1] > a[i]) || ((a[2 * i + 1] > a[2 * i])))
                    {
                        int t = a[2 * i + 1];
                        a[2 * i + 1] = a[i];
                        a[i] = t;
                    }
                }
            }

            int k = a[a.Length - 1];
            a[a.Length - 1] = a[0];
            a[0] = k;
            if (l > 0)
            {
                Heapify(a, l - 1);
            }
        }

        public static void PiramideSort(int[] a)
        {
            Heapify(a, a.Length);
        }
    }
}