import java.util.Arrays;

public class SortingDasar {

    static long perbandingan;
    static long tukar;

    public static void main(String[] args) {
        int[] asli = {5, 2, 9, 1, 7, 3, 8, 6};
        System.out.println("Data awal: " + Arrays.toString(asli));
        System.out.println();

        System.out.println("=== Bubble sort ===");
        int[] a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutBubble(a);
        laporan(a, "Tukar posisi ");

        System.out.println("=== Selection sort ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutSelection(a);
        laporan(a, "Tukar posisi ");

        System.out.println("=== Insertion sort ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        tukar = 0;
        urutInsertion(a);
        laporan(a, "Geser elemen ");
    }

    // Bubble sort: elemen terbesar menggelembung ke kanan tiap putaran.
    static void urutBubble(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean adaTukar = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                perbandingan++;
                if (a[j] > a[j + 1]) {
                    tukarPosisi(a, j, j + 1);
                    adaTukar = true;
                }
            }
            if (!adaTukar) {
                break;   // satu putaran tanpa tukar: data sudah terurut
            }
        }
    }

    // Selection sort: cari nilai terkecil, tukar ke posisi depan.
    static void urutSelection(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < a.length; j++) {
                perbandingan++;
                if (a[j] < a[minIdx]) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                tukarPosisi(a, i, minIdx);
            }
        }
    }

    // Insertion sort: sisipkan elemen ke posisi tepat di bagian kiri.
    static void urutInsertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int kunci = a[i];
            int j = i - 1;
            while (j >= 0) {
                perbandingan++;
                if (a[j] > kunci) {
                    a[j + 1] = a[j];   // geser elemen besar ke kanan
                    tukar++;
                    j--;
                } else {
                    break;
                }
            }
            a[j + 1] = kunci;          // kunci jatuh di lubang yang tersisa
            tukar++;
        }
    }

    static void tukarPosisi(int[] a, int i, int j) {
        tukar++;
        int sementara = a[i];
        a[i] = a[j];
        a[j] = sementara;
    }

    static void laporan(int[] hasil, String metrik) {
        System.out.println("Hasil        : " + Arrays.toString(hasil));
        System.out.println("Perbandingan : " + perbandingan);
        System.out.println(metrik + ": " + tukar);
        System.out.println();
    }
}