using System;

public class Program

{

    public static void Main()

    {

        Random random = new Random();

        int length = 0;

        bool kiemtra = false;

        while(kiemtra == false){

            Console.WriteLine("Nhap phan tu mang gioi han (2,20)");

            length = Int32.Parse(Console.ReadLine());

                if(length >= 2 && length <=20){

                    kiemtra = true;

            }

        }

        double[] arr = new double[length];

        double[] arr2 = new double[length];

        for(int i = 0 ; i < length ; i++){

        double randomNumber = random.Next(1,100) + random.NextDouble();

            arr[i] = randomNumber;

            arr2[i] = randomNumber;

        }

        selectionsort(arr);

        heapSort(arr2);

    }

    public static void hoanvi(double[] arr, int a , int b){

        double tam = arr[a];

        arr[a] = arr[b];

        arr[b] = tam;

    }

    public static void selectionsort(double[] arr){

        int length = arr.Length;

        int DemHoanVi = 0;

        int solandem = 0;

        for(int i = 0 ; i < length ; i++){

            int nhonhat = i;

            for(int j = i + 1; j < length; j++){

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

                nhonhat = j;

                }

                solandem++;

            }

            if(i != nhonhat){

            hoanvi(arr, i ,nhonhat);

            DemHoanVi++;

            }

        }

                    for(int i = 0; i < length; i++){

            Console.Write(arr[i]+" ");

        }

            Console.WriteLine("\nso lan hoan vi cua Selectionsort: "+DemHoanVi);

            Console.WriteLine("so lan dem so sanh cua Selectionsort: "+DemHoanVi);

            Console.WriteLine("----------------------------------------------");

    }

    public static void heapSort(double[] arr2){

        int length = arr2.Length;

        int hoanViDem = 0;

        int soLanChay = 0;

        for(int i = length/2 - 1; i >= 0; i--){

            hoanViDem = heapify(arr2,i,length,hoanViDem);

            soLanChay++;

        }

        for(int i = length - 1; i >=0; i--){

            soLanChay++;

            hoanvi(arr2,0,i);

            hoanViDem++;

            hoanViDem = heapify(arr2,0,i,hoanViDem);

        }

        for(int i = 0; i < length ;i++){

            Console.Write(arr2[i]+" ");

        }

        Console.WriteLine("\nso lan hoan vi cua heap Sort: "+ hoanViDem);

        Console.WriteLine("so lan dem so sanh cua heap Sort: "+ soLanChay);

    }

    public static int heapify(double[] arr2,int i,int length,int hoanViDem){

        int largest = i;

        int left = i*2+1;

        int right = i*2+2;

        if(left < length && arr2[left] > arr2[largest]){

            largest = left;

        }

        if(right < length && arr2[right] > arr2[largest]){

            largest = right;

        }

        if(i != largest){

            hoanvi(arr2,i,largest);

            hoanViDem++;

heapify(arr2,largest,length,hoanViDem);

        }

        return hoanViDem;

    }

}