💎 Crystal Sort

Сортировка данных, основанная на разбиение данных на промежутки.
Работает для целых цисел в диапазоне [0; +∞)
⏳ Среднее время: O(n log n)
💾 Средняя память: O(n)

📖 Languages

🇬🇧 English - README.en.md

📊 Анализ сложности (Big O)

📐 Теоретическая оценка

Эта оценка основана на математическом анализе логики работы алгоритма Crystal Sort.

• Лучшее время: O(n) — массив отсортирован (благодаря начальной проверке).
• Среднее время: O(n log n) — при равномерном распределении данных. Динамический коэффициент k позволяет сбалансировать разброс данных, что ведет к логарифмической глубине рекурсии.
• Худшее аремя: O(n²) — возникает, когда все элементы попадают в одну группу.
• Затраты памяти: O(n) — хранение таблицы разбиения geode.

🌐 Big O Calc

Оценка Big O Notation (https://www.bigocalc.com). Результаты автоматизированных инструментов являются оценочными и могут зависеть от способа тестирования.
Функция crystal_sort выполняет рекурсивный процесс сортировки со следующими характеристиками:

⏳ Сложность по времени:

• Первоначальная проверка того, отсортирован ли массив, занимает O(n).
• Вычисление k требует операций с постоянным временем.
• Построение словаря geode включает в себя однократную итерацию по всем элементам, которая равна O(n).
• Рекурсивные вызовы выполняются для подмассивов (cryst), которые разбивают исходный массив на части на основе значения cryst_idx = x // k.
• В худшем случае, если элементы массива распределены неравномерно, глубина рекурсии может быть пропорциональна количеству элементов, что приведет к наихудшей сложности, подобной O(n²).
• Если массив распределен равномерно, глубина рекурсии уменьшается, и среднее значение стремится к O(n log n).

В целом, временная сложность наихудшего случая составляет приблизительно O(n²), но средние значения могут приближаться к O(n log n).

💾 Пространственная сложность:

• Словарь geode хранит ссылки на подмассивы, которые в совокупности содержат все элементы, поэтому он использует O(n) пробелов.
• Глубина стека рекурсии зависит от того, как разделен массив; в худшем случае она может быть равна O(n).
• Дополнительные переменные (mx_cryst, k и т.д.) используют постоянный пробел.

Таким образом, общая сложность пространства равна O(n), в которой преобладают структуры хранения входных и вспомогательных данных.

🐍 Реализация на языке Python

def crystal_sort(arr):
    # Проверка, отсортирован ли массив O(n)
    for i in range(1, len(arr)):
        if arr[i - 1] > arr[i]:
            break
    # Если отсортирован, возвращаем массив
    else:
        return arr

    # Коэффициент разбиения
    ln = len(arr)
    k = (min(arr) * (ln - 1) + max(arr)) // ln + 1

    # Таблица разбиения
    geode = {}
    mx_cryst = -1

    # Формирование таблицы разбиения O(n). Распределяем числа в зависимости от k
    for x in arr:
        cryst_idx = x // k
        geode[cryst_idx] = geode.get(cryst_idx, []) + [x]
        mx_cryst = max(mx_cryst, cryst_idx)

    # Рекурсивно отсортировываем каждую строку таблицы разбения ("кристаллы")
    pos = 0
    for b in range(mx_cryst + 1):
        if b not in geode:
            continue
        cryst = geode[b]
        for el in crystal_sort(cryst):
            arr[pos] = el
            pos += 1

    return arr

👴 Реализация на языке C++

void crystal_sort(vector<int>& arr) {
    /* Проверка, отсортирован ли массив O(n) */
    bool sorted = true;
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i - 1] > arr[i]) {
            sorted = false;
            break;
        }
    }
    /* Если отсортирован, возвращаем массив */
    if (sorted) return;

    /* Коэффициент разбиения */
    long long min_val = *min_element(arr.begin(), arr.end());
    long long max_val = *max_element(arr.begin(), arr.end());
    size_t n = arr.size();

    long long k = (min_val * (n - 1) + max_val) / n + 1;
    if (k <= 0) k = 1;

    /* Таблица разбиения для, доступ O(1)*/
    unordered_map<int, vector<int>> geode;
    int mx_cryst = -1;

    /* Формирование таблицы разбиения O(n). Распределяем числа в зависимости от k */
    for (int x : arr) {
        int cryst_idx = x / k;
        geode[cryst_idx].push_back(x);
        if (cryst_idx > mx_cryst) mx_cryst = cryst_idx;
    }

    /* Рекурсивно отсортировываем каждую строку таблицы разбения ("кристаллы") */
    size_t pos = 0;
    for (int b = 0; b <= mx_cryst; ++b) {
        auto cryst = geode.find(b);
        if (cryst != geode.end()) {
            crystal_sort(cryst->second);
            for (int val : cryst->second)
                arr[pos++] = val;
        }
    }
}