Блог

Главная - Вопросы по программированию - Что это за тип сортировки?

Что это за тип сортировки?

#arrays #algorithm #sorting #perl #mapping

Вопрос:

Я написал простой алгоритм сортировки и хотел бы знать, какой это тип? Он просто отображает элементы исходного массива в пустой массив с индексами значений исходных элементов.

 my @arg = (5, 14, 12, 9, 1, 17, 3, 19, 20, 4, 6, 15, 8, 18, 7, 2, 10, 13, 11, 16);
my @out;
map { $out[$_] = $_ } @arg;
print join " ", @out;

Конечно, в выходной массив можно добавить сжатие, так как в реальном мире в индексах могут быть дыры.
Кроме того, этот пример может быть расширен для работы с двойниками. Для этого я бы предложил использовать другие структуры данных (например, деревья или связанные списки)

Обновить

Контрольные показатели:

                    Rate uniqsort   bubble  mapping perlsort
    uniqsort  82274/s       --     -29%     -87%     -90%
    bubble   115925/s      41%       --     -81%     -86%
    mapping  614399/s     647%     430%       --     -25%
    perlsort 814352/s     890%     602%      33%       --
  • amp;uniqsort — использование List::MoreUtils через uniq sort @arr ;
  • amp;пузырь — базовая сортировка пузырьков
  • amp;отображение — это
  • amp;perlsort — использование sort {$a<=>$b} @arr

Комментарии:

1. Это похоже на сортировку по подсчету, которая подсчитывает количество вхождений каждого целого числа, а затем просто перечисляет эти целые числа.

2. похоже, это своего рода pgeonhole, за исключением того, что вы, похоже, не предполагаете дублирования в @arg

3. Это не похоже на сортировку, вы используете функцию массива, помещая элемент в массив, используя число в качестве индекса. Упорядоченная структура массива на основе индекса, в вашем случае вы создаете массив с отверстиями вместо отсутствующих чисел, и в качестве побочного эффекта этого подхода будет происходить дедупликация.

4. @Arsenii — если вы удалите undef элементы, то получите упорядоченный список. В случае с цифрами вы могли бы просто использовать sort для достижения того же результата. В чем тогда смысл вашего кода? Почему вы используете map вместо for этого ? В данном конкретном случае for подходит гораздо лучше- map предназначен для хранения результата в структуре данных. print join(' ', uniq sort @args);

5. @Arsenii «Я только что обновил сообщение с эталоном для вас» Пожалуйста, включите или предоставьте ссылку на код, который вы использовали для создания эталона, чтобы мы могли попробовать воспроизвести

Ответ №1:

Во-первых, это не сортирует значения, потому что это приводит к следующему:

 undef, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Обратите внимание на дополнительный элемент. Это частично сломанная (без фильтрации пустых элементов), частично специализированная (дубликаты не допускаются) версия сортировки по ячейкам.

Между прочим,

 @out[@arg] = @arg;

должно быть быстрее, чем

 map { $out[$_] = $_ } @arg;

Комментарии:

1. Спасибо, @ikegami. Хороший момент о @out[@arg] = @arg; Я не видел элемент undef в своем выводе, потому что я не сбрасывал его, используя классический модуль. Я должен был. Да. 🙂

2. Предупреждения сказали бы вам. Всегда пользуйся use strict; use warnings; . Кроме того, там было бы ведущее место.

Метки: