Гадалка сортировка: адаптивный алгоритм с бинарным поиском позиции вставки

Сегодня 08:48:33 () мы погрузимся в необычную тему – алгоритм, получивший название «Гадалка сортировка». Несмотря на своё загадочное имя, этот метод построен на строгих математических принципах и может стать интересным дополнением к классическим сортировкам, о которых часто говорят на собеседованиях (см. фрагмент из сети: «Великая тройка: алгоритмы сортировки, которые точно пригодятся на собеседовании…»).

Что такое Гадалка сортировка?

Гадалка сортировка – это адаптивный алгоритм сортировки, который использует идею «предсказания» будущего положения элемента на основе уже обработанной части массива. Алгоритм делит входной массив на две зоны:

• Известная зона – уже отсортированный префикс, в котором элементы находятся на своих окончательных местах;
• Зона предсказаний – оставшаяся часть, где каждый элемент «гадает», насколько далеко он должен сдвинуться, чтобы занять правильное положение относительно известной зоны.

На каждом шаге алгоритм берёт первый элемент из зоны предсказаний, сравнивает его с элементами известной зоны (обычно с конца к началу) и определяет позицию, где он должен быть вставлен. После вставки известная зона увеличивается на один элемент, а зона предсказаний уменьшается. Этот процесс напоминает работу сортировки вставками, но с добавлением heuristics‑подсказки, которая ускоряет поиск места вставки.

Как работает Гадалка сортировка?

1. Инициализировать известную зону как пустую (индекс sorted_end = 0).
2. Пока sorted_end < n:
   1. Взять элемент key = arr[sorted_end] (первый необработанный).
   2. Установить j = sorted_end ⎯ 1.
   3. Mientras j ≥ 0 и arr[j] > key:
      • Сдвинуть arr[j+1] = arr[j] (как в обычной вставке).
      • Уменьшить j--.
   4. Вставить ключ: arr[j+1] = key.
   5. Увеличить sorted_end++.

Отличие от классической сортировки вставками заключается в том, что перед началом внутреннего цикла мы можем выполнить «предсказание» позиции вставки, используя, например, бинарный поиск по уже отсортированному префиксу. Это снижает количество сравнений с O(n) до O(log n) на каждом шаге, сохраняя при этом O(1) дополнительной памяти.

Псевдокод

function gaidalkaSort(arr):
 n = length(arr)
 for i from 1 to n-1:
 key = arr[i]
 // бинарный поиск позиции для key в arr[0..i-1]
 left = 0
 right = i-1
 while left <= right:
 mid = (left + right) // 2
 if arr[mid] < key:
 left = mid + 1
 else:
 right = mid ⸺ 1
 // left – позиция вставки
 for j from i-1 down to left:
 arr[j+1] = arr[j]
 arr[left] = key
 return arr

Анализ сложности

• Время в худшем случае: O(n²) (из-за сдвига элементов, как в сортировке вставками).
• Время в лучшем случае: массив уже отсортирован → бинарный поиск дает позицию сразу, сдвигов не требуется → O(n log n) (из-за поиска).
• Среднее время: O(n log n) при случайных данных, так как количество сдвигов в среднем пропорционально числу инверсий, которое уменьшается благодаря более точному предсказанию позиции.
• Память: O(1) дополнительной памяти (сортировка на месте).

Таким образом, Гадалка сортировка сочетает преимущества сортировки вставками (минимальная память, простота реализации) и бинарного поиска (уменьшение числа сравнений).

Примеры кода

Python

def gaidalka_sort(arr):
 n = len(arr)
 for i in range(1, n):
 key = arr[i]
 # бинарный поиск позиции вставки
 left, right = 0, i-1
 while left <= right:
 mid = (left + right) // 2
 if arr[mid] < key:
 left = mid + 1
 else:
 right = mid ⎯ 1
 # сдвигаем элементы вправо
 for j in range(i-1, left-1, -1):
 arr[j+1] = arr[j]
 arr[left] = key
 return arr

Java

public static void gaidalkaSort(int[] arr) {
 int n = arr.length;
 for (int i = 1; i < n; i++) {
 int key = arr[i];
 int left = 0, right = i-1;
 while (left <= right) {
 int mid = (left + right) / 2;
 if (arr[mid] < key) {
 left = mid + 1;
 } else {
 right = mid ⸺ 1;
 }
 }
 for (int j = i-1; j >= left; j--) {
 arr[j+1] = arr[j];
 }
 arr[left] = key;
 }
}

C++

void gaidalkaSort(std::vector& arr) {
 size_t n = arr.size;
 for (size_t i = 1; i < n; ++i) {
 int key = arr[i];
 size_t left = 0, right = i-1;
 while (left <= right) {
 size_t mid = (left + right) / 2;
 if (arr[mid] < key)
 left = mid + 1;
 else
 right = mid ⎯ 1;
 }
 for (size_t j = i; j > left; --j)
 arr[j] = arr[j-1];
 arr[left] = key;
 }
}

Сравнение с другими алгоритмами

Как видно из таблицы, Гадалка сортировка занимает промежуточное положение: в лучшем и среднем случаях она конкурирует с Merge Sort и Quick Sort, но в худшем случае может деградировать до квадратичной сложности, как и обычная вставка. Однако её главное преимущество – минимальное потребление памяти и простота реализации.

Когда стоит использовать Гадалку сортировку?

• Когда объём данных умеренный (до нескольких десятков тысяч элементов) и критична экономия памяти.
• Когда данные почти отсортированы (мало инверсий) – алгоритм будет работать близко к O(n log n) благодаря эффективному бинарному поиску.
• В учебных целях: демонстрирует, как можно улучшить классическую сортировку вставками с помощью дополнительногоheuristics‑подхода.
• В средах с ограниченной динамической памятью (встроенные системы, микроконтроллеры), где выделение дополнительного массива невозможно.

Гадалка сортировка – это интересный гибрид простой сортировки вставками и бинарного поиска, позволяющий сократить количество сравнений при сохранении O(1) дополнительной памяти. Хотя в худшем случае её сложность остаётся квадратичной, на почти отсортированных или небольших массивах она показывает конкурентоспособные результаты и может стать полезным инструментом в арсенале программиста.

Надеемся, эта статья помогла вам лучше понять природу «гадательного» подхода к сортировке и вдохновила на эксперименты с собственными адаптивными алгоритмами. Удачной сортировки!