/*==============================================================================
  Лабораторна робота №6. Завдання 2. Варіант 19.
  Тема: алгоритми сортування та пошуку.

  Умова (таблиця 6.1, завдання 19.2): створити одновимірний масив, кількість
  елементів якого ввести з клавіатури. Передбачити меню вибору способу
  створення масиву: введення з клавіатури або генерація псевдовипадкових
  чисел. Відсортувати масив за алгоритмом пірамідального сортування
  (Heapsort) [1.8] та здійснити пошук у масиві за алгоритмом блочного
  пошуку [2.10]. Передбачити виведення проміжних результатів у процесі
  виконання ітерацій сортування масиву.

  Додаткові вимоги завдання 2:
    - визначити ефективність методу сортування: кількість порівнянь та обмінів;
    - визначити ефективність методу пошуку: кількість порівнянь;
    - передбачити вибір режиму виведення результатів: або тільки відсортований
      масив, або з проміжними ітераціями.

  ОБМЕЖЕННЯ УМОВИ: забороняється використовувати STL, std::vector, а також
  бібліотечні методи сортування та пошуку.

  Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11.

  Компілятор: gcc -std=c17
==============================================================================*/

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

const int MAX_SIZE = 1000;

/* Лічильники ефективності. Оголошені глобально, щоб не захаращувати
   заголовки функцій сортування службовими параметрами. */
unsigned long long g_comparisons = 0; /* порівнянь під час сортування */
unsigned long long g_swaps = 0;       /* обмінів під час сортування   */

/*------------------------------------------------------------------------------
  readInt — прочитати ціле число із заданого діапазону з контролем введення.

  Параметри: prompt [вхідний], value [вихідний], low, high [вхідні].
  Повертає : true — число прочитано; false — вхідні дані вичерпано.
------------------------------------------------------------------------------*/
bool readInt(const char *prompt, int *value, int low, int high)
{
    for (;;) {
        printf("%s", prompt);
        const int scanned = scanf("%d", value);

        if (scanned == EOF)
            return false;
        if (scanned == 1 && *value >= low && *value <= high)
            return true;

        if (scanned != 1) {
            int c;
            /* очищення буфера */
            while ((c = getchar()) != '\n' && c != EOF) {
            }
        }
        printf("Помилка: потрібне ціле число від %d до %d.\n", low, high);
    }
}

/*------------------------------------------------------------------------------
  integerSqrt — цілий квадратний корінь: найбільше ціле k, для якого k*k <= n.

  Обчислюється послідовним нарощуванням, без бібліотечної функції sqrt()
  і заголовного файла math.h. Для допустимих розмірів масиву (до 1000
  елементів) цикл виконує не більше 32 кроків.

  Параметри: n [вхідний] — невід'ємне ціле число.
  Повертає : цілу частину квадратного кореня з n.

  Локальні змінні:
      root — поточний кандидат на значення кореня.
------------------------------------------------------------------------------*/
int integerSqrt(int n)
{
    int root = 0;

    while ((root + 1) * (root + 1) <= n)
        ++root;

    return root;
}

/*------------------------------------------------------------------------------
  printArray — вивести масив у рядок із заголовком.

  Параметри: title [вхідний], a [вхідний], n [вхідний].
------------------------------------------------------------------------------*/
void printArray(const char *title, const int a[], int n)
{
    printf("%s", title);
    for (int i = 0; i < n; ++i)
        printf(" %d", a[i]);
    printf("\n");
}

/*------------------------------------------------------------------------------
  swapItems — обміняти значення двох елементів масиву з підрахунком обмінів.

  Параметри:
      a    [вхідний/вихідний] — масив;
      i, j [вхідні]           — індекси елементів, що обмінюються.
------------------------------------------------------------------------------*/
void swapItems(int a[], int i, int j)
{
    const int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    ++g_swaps;
}

/*------------------------------------------------------------------------------
  siftDown — просіювання елемента вниз по купі (heap).

  Відновлює властивість незростаючої купи для піддерева з коренем root
  у межах перших size елементів масиву. Властивість купи: значення батька
  не менше за значення кожного з нащадків. Для елемента з індексом i
  нащадками є елементи з індексами 2i+1 та 2i+2.

  Параметри:
      a    [вхідний/вихідний] — масив, що подає купу;
      root [вхідний]          — індекс кореня піддерева;
      size [вхідний]          — кількість елементів, які належать купі.

  Локальні змінні:
      largest — індекс найбільшого з трьох елементів (батько і два нащадки);
      left, right — індекси лівого та правого нащадків.
------------------------------------------------------------------------------*/
void siftDown(int a[], int root, int size)
{
    for (;;) {
        int largest = root;
        const int left = 2 * root + 1;
        const int right = 2 * root + 2;

        if (left < size) {
            ++g_comparisons;
            if (a[left] > a[largest])
                largest = left;
        }

        if (right < size) {
            ++g_comparisons;
            if (a[right] > a[largest])
                largest = right;
        }

        if (largest == root)
            break; /* властивість купи відновлено */

        swapItems(a, root, largest);
        root = largest; /* просіювання триває нижче */
    }
}

/*------------------------------------------------------------------------------
  heapSort — пірамідальне сортування (Heapsort) за неспаданням.

  Алгоритм складається з двох фаз:
    1) побудова купи: просіювання вниз усіх внутрішніх вузлів, починаючи
       з останнього (індекс n/2 - 1) і до кореня;
    2) власне сортування: корінь купи (найбільший елемент) переставляється
       в кінець невідсортованої частини, розмір купи зменшується на одиницю,
       новий корінь просіюється вниз.

  Параметри:
      a       [вхідний/вихідний] — масив, що сортується;
      n       [вхідний]          — кількість елементів;
      verbose [вхідний]          — виводити проміжні ітерації.

  Трудомісткість алгоритму — O(n·log n) у найгіршому випадку, на відміну
  від O(n²) у простих методів (бульбашка, вибір, вставки).
------------------------------------------------------------------------------*/
void heapSort(int a[], int n, bool verbose)
{
    if (verbose)
        printf("\n--- Фаза 1: побудова купи ---\n");

    for (int root = n / 2 - 1; root >= 0; --root) {
        siftDown(a, root, n);
        if (verbose) {
            printf("  просіяно вузол %d:", root);
            printArray("", a, n);
        }
    }

    if (verbose) {
        printArray("  Купу побудовано:", a, n);
        printf("\n--- Фаза 2: вилучення максимумів ---\n");
    }

    for (int size = n - 1; size > 0; --size) {
        swapItems(a, 0, size); /* максимум — у кінець масиву */
        siftDown(a, 0, size);

        if (verbose) {
            printf("  ітерація %d (відсортовано %d):", n - size, n - size);
            printArray("", a, n);
        }
    }
}

/*------------------------------------------------------------------------------
  blockSearch — блочний (стрибковий) пошук у впорядкованому масиві.

  Алгоритм [2.10]. Масив умовно поділяється на блоки завдовжки step.
  Спочатку переглядаються лише останні елементи блоків: індекс збільшується
  кроком step, доки не буде знайдено блок, останній елемент якого не менший
  за ключ. Далі всередині цього блоку виконується послідовний пошук.

  Оптимальна довжина блоку — цілий корінь з n: тоді сумарна кількість
  порівнянь найменша і становить приблизно 2*sqrt(n), що краще за O(n),
  але гірше за двійковий O(log n). Перевага блочного пошуку — рух лише
  вперед, що корисно для носіїв з повільним поверненням назад.

  Передумова: масив упорядкований за неспаданням.

  Параметри:
      a           [вхідний]  — упорядкований масив;
      n           [вхідний]  — кількість елементів;
      key         [вхідний]  — шуканий ключ;
      comparisons [вихідний] — адреса лічильника порівнянь;
      blocks      [вихідний] — адреса лічильника переглянутих блоків.

  Повертає: індекс знайденого елемента або -1, якщо ключа немає.

  Локальні змінні:
      step    — довжина блоку;
      current — межа поточного блоку;
      prev    — початок поточного блоку.
------------------------------------------------------------------------------*/
int blockSearch(const int a[], int n, int key, unsigned long long *comparisons,
                int *blocks)
{
    *comparisons = 0;
    *blocks = 0;

    if (n <= 0)
        return -1;

    int step = integerSqrt(n);
    if (step < 1)
        step = 1;

    /* Крок 1: стрибками знайти блок, у якому може міститися ключ. */
    int prev = 0;
    int current = step - 1;
    if (current >= n)
        current = n - 1;

    for (;;) {
        ++(*comparisons);
        ++(*blocks);

        if (a[current] >= key)
            break; /* потрібний блок знайдено */

        if (current == n - 1)
            return -1; /* ключ більший за всі елементи */

        prev = current + 1;
        current += step;
        if (current >= n)
            current = n - 1;
    }

    /* Крок 2: послідовний пошук усередині знайденого блоку. */
    for (int i = prev; i <= current; ++i) {
        ++(*comparisons);
        if (a[i] == key)
            return i;
    }

    return -1;
}

/*------------------------------------------------------------------------------
  Головна функція. Створює масив, сортує його пірамідальним сортуванням,
  виводить показники ефективності та виконує блочний пошук.

  Локальні змінні:
      a, n        — масив та кількість його елементів;
      choice      — спосіб створення масиву;
      verbose     — режим виведення проміжних ітерацій;
      key         — шуканий ключ;
      found       — індекс знайденого елемента;
      searchComparisons — кількість порівнянь під час пошуку;
      blocks      — кількість переглянутих блоків.
------------------------------------------------------------------------------*/
int main()
{
    printf("Лабораторна робота №6, завдання 2 (варіант 19)\n");
    printf("Виконав: студент групи ІПЗ-11 Одарчук Олексій\n");
    printf("Пірамідальне сортування (Heapsort) та блочний пошук\n\n");

    int n = 0;
    if (!readInt("Уведіть кількість елементів масиву (1..1000): ", &n, 1, MAX_SIZE))
        return 1;

    int a[MAX_SIZE];

    printf("\nСпосіб створення масиву:\n"
           "  1 - введення з клавіатури\n"
           "  2 - генерація псевдовипадкових чисел\n");

    int choice = 0;
    if (!readInt("Оберіть спосіб (1..2): ", &choice, 1, 2))
        return 1;

    if (choice == 1) {
        printf("Уведіть цілі числа (усього %d):\n", n);
        for (int i = 0; i < n; ++i) {
            char prompt[32];
            snprintf(prompt, sizeof prompt, "  a[%d] = ", i);
            if (!readInt(prompt, &a[i], -1000000, 1000000))
                return 1;
        }
    } else {
        int low = 0, high = 0;
        if (!readInt("Уведіть нижню межу діапазону: ", &low, -1000000, 1000000))
            return 1;
        if (!readInt("Уведіть верхню межу діапазону: ", &high, low, 1000000))
            return 1;
        srand((unsigned)time(NULL));
        /* Масштабування rand() на діапазон замість rand() % range: стандарт гарантує
           лише RAND_MAX >= 32767, і для ширшого діапазону остача не охопила б
           усіх значень. */
        for (int i = 0; i < n; ++i)
            a[i] = low +
                   (int)((double)rand() / ((double)RAND_MAX + 1.0) * (high - low + 1));
    }

    printf("\nРежим виведення результатів:\n"
           "  1 - тільки відсортований масив\n"
           "  2 - з проміжними ітераціями сортування\n");

    int mode = 0;
    if (!readInt("Оберіть режим (1..2): ", &mode, 1, 2))
        return 1;

    const bool verbose = (mode == 2);

    printArray("\nВхідний масив:", a, n);

    g_comparisons = 0;
    g_swaps = 0;
    heapSort(a, n, verbose);

    printArray("\nВідсортований масив:", a, n);

    printf("\nЕфективність пірамідального сортування\n");
    printf("  Елементів у масиві: %d\n", n);
    printf("  Порівнянь:          %llu\n", g_comparisons);
    printf("  Обмінів:            %llu\n", g_swaps);

    /* Пошук у вже впорядкованому масиві. */
    int key = 0;
    if (!readInt("\nУведіть ключ для блочного пошуку: ", &key, -1000000, 1000000))
        return 1;

    unsigned long long searchComparisons = 0;
    int blocks = 0;
    const int found = blockSearch(a, n, key, &searchComparisons, &blocks);

    printf("\nРезультат блочного пошуку\n");
    if (found >= 0)
        printf("  Ключ %d знайдено, індекс у відсортованому масиві: %d\n", key, found);
    else
        printf("  Ключ %d у масиві відсутній\n", key);

    printf("  Довжина блоку (цілий корінь з n): %d\n", integerSqrt(n));
    printf("  Переглянуто блоків:       %d\n", blocks);
    printf("  Порівнянь під час пошуку: %llu\n", searchComparisons);

    return 0;
}