import java.util.Arrays;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
  
        int size = 100000;
        int[] originalArray = new int[size];
        Random random = new Random();

        for (int i = 0; i < size; i++) {
            originalArray[i] = random.nextInt(100000);
        }
        int[] array1 = Arrays.copyOf(originalArray, size);
        long start1 = System.currentTimeMillis();
        Arrays.sort(array1);
        long time1 = System.currentTimeMillis() - start1;

        int[] array2 = Arrays.copyOf(originalArray, size);
        long start2 = System.currentTimeMillis();
        selectionSort(array2);
        long time2 = System.currentTimeMillis() - start2;

   
        int[] array3 = Arrays.copyOf(originalArray, size);
        long start3 = System.currentTimeMillis();
        insertionSort(array3);
        long time3 = System.currentTimeMillis() - start3;

        System.out.println("Results for sorting " + size + " numbers:");
        System.out.println("Quick Sort Time: " + time1 + " ms");
        System.out.println("Selection Sort Time: " + time2 + " ms");
        System.out.println("Insertion Sort Time: " + time3 + " ms");

        if (time1 < time2 && time1 < time3) {
            System.out.println("\nFaster Algorithm: Quick Sort");
        } else if (time2 < time1 && time2 < time3) {
            System.out.println("\nFaster Algorithm: Selection Sort");
        } else {
            System.out.println("\nFaster Algorithm: Insertion Sort");
        }
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
    
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}