// Counts the comparisons each algorithm performs at several sizes.

record SearchResult(int index, int comparisons) {}

/// Returns the index and the comparison count of a linear search.
SearchResult linearSearchCounted(int[] items, int target) {
    int comparisons = 0;
    for (int i = 0; i < items.length; i++) {
        comparisons++;
        if (items[i] == target) {
            return new SearchResult(i, comparisons);
        }
    }
    return new SearchResult(-1, comparisons);
}

/// Returns the index and the comparison count of a binary search.
SearchResult binarySearchCounted(int[] items, int target) {
    int low = 0;
    int high = items.length - 1;
    int comparisons = 0;

    while (low <= high) {
        comparisons++;
        int middle = (low + high) / 2;
        if (items[middle] == target) {
            return new SearchResult(middle, comparisons);
        } else if (items[middle] < target) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }

    return new SearchResult(-1, comparisons);
}

/// Sorts items in place with selection sort; returns the comparisons made.
int selectionSortCounted(int[] items) {
    int comparisons = 0;

    for (int i = 0; i < items.length; i++) {
        int smallest = i;
        for (int j = i + 1; j < items.length; j++) {
            comparisons++;
            if (items[j] < items[smallest]) {
                smallest = j;
            }
        }
        int temp = items[i];
        items[i] = items[smallest];
        items[smallest] = temp;
    }

    return comparisons;
}

/// Returns the numbers from 0 to size - 1, in order.
int[] upTo(int size) {
    int[] numbers = new int[size];
    for (int i = 0; i < size; i++) {
        numbers[i] = i;
    }
    return numbers;
}

/// Returns the numbers from 0 to size - 1, in a random order.
int[] shuffled(int size, Random random) {
    ArrayList<Integer> numbers = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        numbers.add(i);
    }
    Collections.shuffle(numbers, random);

    int[] result = new int[size];
    for (int i = 0; i < size; i++) {
        result[i] = numbers.get(i);
    }
    return result;
}

/// Prints worst-case comparison counts for both searches.
void compareSearches(int[] sizes) {
    IO.println("SEARCHING for a missing value");
    IO.println(String.format("%8s%8s%8s%8s", "Size", "Linear", "Binary", "Ratio"));
    IO.println("-".repeat(32));

    for (int size : sizes) {
        int[] data = upTo(size);
        int missing = size + 1;
        int linear = linearSearchCounted(data, missing).comparisons();
        int binary = binarySearchCounted(data, missing).comparisons();
        IO.println(String.format("%8d%8d%8d%7.0fx",
                size, linear, binary, (double) linear / binary));
    }
}

/// Prints selection sort's comparison counts at several sizes.
void compareSorts(int[] sizes) {
    IO.println();
    IO.println("SORTING a shuffled array");
    IO.println(String.format("%8s%13s%14s", "Size", "Comparisons", "Size squared"));
    IO.println("-".repeat(35));

    Random random = new Random();
    for (int size : sizes) {
        int comparisons = selectionSortCounted(shuffled(size, random));
        IO.println(String.format("%8d%13d%14d", size, comparisons, size * size));
    }
}

void main() {
    compareSearches(new int[] {10, 100, 1000, 10000});
    compareSorts(new int[] {10, 50, 100, 200});
}

// From Groundwork, chapter 11 (ch11-searching-and-sorting), box 15.
// This example is from Groundwork, licensed CC BY-NC-SA 4.0.
// Run with: java ch11_15.java