// 5. hét – A gyakorlati feladatok megoldásai
// Futtatás: java Exercises05.java
import java.util.Arrays;

public class Exercises05 {

    // F1. Rendezett-e a tömb? – O(n)
    static boolean isSorted(int[] a) {
        for (int i = 1; i < a.length; i++) if (a[i - 1] > a[i]) return false;
        return true;
    }

    // F2. Csökkenő sorrendű beszúrásos rendezés: csak a reláció fordul meg
    static void insertionSortDesc(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int x = a[i], j = i - 1;
            while (j >= 0 && a[j] < x) { a[j + 1] = a[j]; j--; }
            a[j + 1] = x;
        }
    }

    // F3. Stringek rendezése kiválasztásos rendezéssel (compareTo)
    static void selectionSortStrings(String[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) if (a[j].compareTo(a[min]) < 0) min = j;
            String t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }

    // F4. Rekordok rendezése pontszám szerint – a beszúrásos rendezés STABIL
    record Student(String name, int score) {
        public String toString() { return name + ":" + score; }
    }

    static void sortByScore(Student[] a) {
        for (int i = 1; i < a.length; i++) {
            Student x = a[i];
            int j = i - 1;
            while (j >= 0 && a[j].score() > x.score()) { a[j + 1] = a[j]; j--; } // > és nem >= : stabil!
            a[j + 1] = x;
        }
    }

    // F5. A k legkisebb elem: a kiválasztásos rendezés első k lépése – O(k·n)
    static int[] kSmallest(int[] a, int k) {
        int[] b = a.clone();
        for (int i = 0; i < k; i++) {
            int min = i;
            for (int j = i + 1; j < b.length; j++) if (b[j] < b[min]) min = j;
            int t = b[i]; b[i] = b[min]; b[min] = t;
        }
        return Arrays.copyOf(b, k);
    }

    // F6. Számláló rendezés (kis értéktartományra, 0..maxValue) – O(n + k), nem összehasonlító
    static void countingSort(int[] a, int maxValue) {
        int[] count = new int[maxValue + 1];
        for (int v : a) count[v]++;
        int k = 0;
        for (int v = 0; v <= maxValue; v++)
            while (count[v]-- > 0) a[k++] = v;
    }

    // F7. Hány csere kell a buborékrendezésnek? (= az inverziók száma)
    static int inversions(int[] a) {
        int c = 0;
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] > a[j]) c++;
        return c;
    }

    public static void main(String[] args) {
        System.out.println("F1. isSorted([1,2,2,5]) = " + isSorted(new int[] { 1, 2, 2, 5 }) + ", isSorted([3,1]) = " + isSorted(new int[] { 3, 1 }));
        int[] d = { 5, 2, 8, 1, 9, 3 };
        insertionSortDesc(d);
        System.out.println("F2. csökkenő: " + Arrays.toString(d));
        String[] cities = { "Wuhan", "Beijing", "Shanghai", "Chengdu", "Eger" };
        selectionSortStrings(cities);
        System.out.println("F3. városok: " + Arrays.toString(cities));
        Student[] st = { new Student("Li", 85), new Student("Wang", 90), new Student("Zhang", 85), new Student("Chen", 70) };
        sortByScore(st);
        System.out.println("F4. pontszám szerint (stabil): " + Arrays.toString(st));
        System.out.println("F5. 3 legkisebb: " + Arrays.toString(kSmallest(new int[] { 7, 2, 9, 4, 1, 8 }, 3)));
        int[] grades = { 3, 5, 1, 4, 5, 2, 3, 5, 4, 1 };
        countingSort(grades, 5);
        System.out.println("F6. számláló rendezés (jegyek): " + Arrays.toString(grades));
        System.out.println("F7. inverziók [5,2,8,1,9,3]: " + inversions(new int[] { 5, 2, 8, 1, 9, 3 }));
    }
}