#arrays #sorting #adhoc
#массивы #сортировка #adhoc
Вопрос:
Предположим, что массив задается a1, a2, …, ak, _ , a(k 1), …, an . Здесь символ подчеркивания (_) представляет пустое пространство. Мы можем переместить любой элемент массива в это пространство. Мы можем повторить эту операцию любое количество раз. Возможно ли отсортировать каждый массив с одним таким пробелом?
Ответ №1:
Да, это возможно.
Отсортированный массив — это просто определенная перестановка этого массива.
Любая перестановка может быть достигнута с помощью последовательности отдельных обменов.
И обмен может быть реализован с одним временным элементом.
(На самом деле можно отсортировать массив целых типов без временного, используя операции XOR).
Комментарии:
1. Спасибо. Я даже не знаю, что у without-temporary-swap есть версия, использующая XOR. a = a ^ b; b = a ^ b; a = a ^ b; или через плюс / минус: a = a b; b = a — b; a = a — b;
Ответ №2:
Существует несколько алгоритмов сортировки на месте. Наиболее заметной является нерекурсивная версия quick-sort (поскольку рекурсивная версия будет занимать место в стеке пропорционально количеству рекурсивных вызовов), что в среднем предоставит вам сложность O (n log n).
Другая возможность заключается в использовании менее эффективных алгоритмов, таких как сортировка по вставке и пузырьковая сортировка, сложность которых равна O (n ^ 2).
Что касается вашего конкретного вопроса, то есть использования этого конкретного пространства, вы можете использовать его для замены, как сказал Вирсавия, но я бы не стал терять время на выполнение такого рода операций.
Учтите также тот факт, что если у вас есть явное понятие «неиспользуемого пространства» в середине вашего массива, вы должны попытаться понять его семантику, то есть, каково было бы его правильное размещение с точки зрения упорядочения. Если вы этого не сделаете и оставите его там, где он есть, вы окажетесь со «сломанным» инвариантом, и у вас возникнут трудности с реализацией алгоритмов, таких как двоичный поиск, в вашей коллекции.
Ответ №3:
Я еще не видел таких контейнеров в реальном коде, но самый простой алгоритм для реализации (не самый эффективный!) — поменять местами пустой с первым элементом, затем поменять наименьший с пустым на первом месте, затем предположим, что контейнер начинается со второй позиции и повторяется до последней позиции, которая будетпустое пространство. В этом случае swap просто означает заполнить пустое пространство и пометить другую позицию как пустую.