💎 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

defcrystal_sort(arr):
# Проверка, отсортирован ли массив O(n)foriinrange(1, len(arr)):
ifarr[i-1] >arr[i]:
break# Если отсортирован, возвращаем массивelse:
returnarr# Коэффициент разбиенияln=len(arr)
k= (min(arr) * (ln-1) +max(arr)) //ln+1# Таблица разбиенияgeode= {}
mx_cryst=-1# Формирование таблицы разбиения O(n). Распределяем числа в зависимости от kforxinarr:
cryst_idx=x//kgeode[cryst_idx] =geode.get(cryst_idx, []) + [x]
mx_cryst=max(mx_cryst, cryst_idx)
# Рекурсивно отсортировываем каждую строку таблицы разбения ("кристаллы")pos=0forbinrange(mx_cryst+1):
ifbnotingeode:
continuecryst=geode[b]
forelincrystal_sort(cryst):
arr[pos] =elpos+=1returnarr

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

voidcrystal_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;
/* Коэффициент разбиения */longlong min_val = *min_element(arr.begin(), arr.end());
longlong max_val = *max_element(arr.begin(), arr.end());
size_t n = arr.size();
longlong 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;
}
}
}