// Week 13 – Solutions of the practice exercises
// Run: java Exercises13.java
import java.util.Arrays;
import java.util.Random;

public class Exercises13 {

    // E1. Descending merge sort: only the comparison is reversed
    static void mergeSortDesc(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        mergeSortDesc(a, lo, mid);
        mergeSortDesc(a, mid + 1, hi);
        int[] t = new int[hi - lo + 1];
        int i = lo, j = mid + 1, k = 0;
        while (i <= mid && j <= hi) t[k++] = a[i] >= a[j] ? a[i++] : a[j++];
        while (i <= mid) t[k++] = a[i++];
        while (j <= hi) t[k++] = a[j++];
        System.arraycopy(t, 0, a, lo, t.length);
    }

    // E2. Sorting strings by length, STABLY (with merge sort)
    static void sortByLength(String[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        sortByLength(a, lo, mid);
        sortByLength(a, mid + 1, hi);
        String[] t = new String[hi - lo + 1];
        int i = lo, j = mid + 1, k = 0;
        while (i <= mid && j <= hi) t[k++] = a[i].length() <= a[j].length() ? a[i++] : a[j++];
        while (i <= mid) t[k++] = a[i++];
        while (j <= hi) t[k++] = a[j++];
        System.arraycopy(t, 0, a, lo, t.length);
    }

    // E3. Number of inversions in O(n log n) time: while merging, if the right element comes first,
    // then it is smaller than all remaining elements of the left part
    static long countInversions(int[] a, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = (lo + hi) / 2;
        long c = countInversions(a, lo, mid) + countInversions(a, mid + 1, hi);
        int[] t = new int[hi - lo + 1];
        int i = lo, j = mid + 1, k = 0;
        while (i <= mid && j <= hi) {
            if (a[i] <= a[j]) t[k++] = a[i++];
            else {
                t[k++] = a[j++];
                c += mid - i + 1;
            }
        }
        while (i <= mid) t[k++] = a[i++];
        while (j <= hi) t[k++] = a[j++];
        System.arraycopy(t, 0, a, lo, t.length);
        return c;
    }

    // E4. The k-th smallest element (quickselect): we continue in only one part – O(n) on average
    static int quickSelect(int[] a, int k) {
        int lo = 0, hi = a.length - 1;
        Random rnd = new Random(3);
        while (true) {
            int r = lo + rnd.nextInt(hi - lo + 1);
            int t = a[r]; a[r] = a[hi]; a[hi] = t;
            int pivot = a[hi], i = lo - 1;
            for (int j = lo; j < hi; j++) if (a[j] < pivot) { i++; t = a[i]; a[i] = a[j]; a[j] = t; }
            t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
            int p = i + 1;
            if (p == k) return a[p];
            if (k < p) hi = p - 1;
            else lo = p + 1;
        }
    }

    // E5. Dutch national flag: sorting the values 0, 1, 2 in a single pass (three-way partitioning)
    static void dutchFlag(int[] a) {
        int lo = 0, mid = 0, hi = a.length - 1;
        while (mid <= hi) {
            if (a[mid] == 0) { int t = a[lo]; a[lo++] = a[mid]; a[mid++] = t; }
            else if (a[mid] == 1) mid++;
            else { int t = a[hi]; a[hi--] = a[mid]; a[mid] = t; }
        }
    }

    // E6. Median of two sorted arrays by merging (up to the middle)
    static double medianOfTwo(int[] x, int[] y) {
        int n = x.length + y.length, i = 0, j = 0, prev = 0, cur = 0;
        for (int k = 0; k <= n / 2; k++) {
            prev = cur;
            cur = (j >= y.length || (i < x.length && x[i] <= y[j])) ? x[i++] : y[j++];
        }
        return n % 2 == 1 ? cur : (prev + cur) / 2.0;
    }

    public static void main(String[] args) {
        int[] a = { 5, 2, 8, 1, 9, 3 };
        mergeSortDesc(a, 0, a.length - 1);
        System.out.println("E1. descending: " + Arrays.toString(a));
        String[] w = { "pear", "fig", "apple", "kiwi", "date", "plum" };
        sortByLength(w, 0, w.length - 1);
        System.out.println("E2. by length (stable): " + Arrays.toString(w));
        System.out.println("E3. inversions [5,2,8,1,9,3]: " + countInversions(new int[] { 5, 2, 8, 1, 9, 3 }, 0, 5));
        int[] q = { 7, 2, 9, 4, 3, 8, 6 };
        System.out.println("E4. the 3rd smallest (k=2, from 0): " + quickSelect(q.clone(), 2) + ", median (k=3): " + quickSelect(q.clone(), 3));
        int[] f = { 2, 0, 1, 2, 1, 0, 0, 2, 1 };
        dutchFlag(f);
        System.out.println("E5. Dutch flag: " + Arrays.toString(f));
        System.out.println("E6. median([1,3,8], [2,4,9,10]) = " + medianOfTwo(new int[] { 1, 3, 8 }, new int[] { 2, 4, 9, 10 })
                + ", ([1,2], [3,4]) = " + medianOfTwo(new int[] { 1, 2 }, new int[] { 3, 4 }));
    }
}