Есть ли название для такого рода?

Question

Какое название для сортировки используется в этом ответе ? Я гуглил за "идеальный вид вставки", но ничего не нашел. Вот код из этого ответа:

#this is O(n) instead of O(n log n) or worse
sub perfect_insert_sort {
    my $h = shift;
    my @k;
    for my $k (keys %$h) {
        $k[$h->{$k}{order}] = $k;
    }
    return @k;
}

Answer 1

Думаю, мне следовало бы назвать это perfect_bucket_sort вместо perfect_insertion_sort.

Answer 2

Это не сортировка с вставкой, на самом деле это даже не сортировка сравнения, потому что теоретическая нижняя граница для них - O (nlogn).

Так что это, вероятно, сортировка по сегментам;также обратите внимание, что нет никаких сравнений:)

Answer 3

На самом деле это совсем не так. на самом деле это, прежде всего, карта или преобразование. Вот пример структуры данных, которую они имеют:

my $hash = {
   foo => { order => 3 },
   bar => { order => 20 },
   baz => { order => 66 }, 
};

Это просто перевод 'order' на элементы в массиве. Например, если вы передадите этот $ hash в perfect_insert_sort, он вернет массив из 67 элементов, с тремя элементами (один с индексом 3, один с 20 и один с 66), а остальные с неопределенным значением и полностью в несортированном заказ.

Ничего в этой функции не сортирует. Если в этом другом ответе есть какая-либо сортировка, то это происходит за до вызова функции.

@ downvoter:

И, глядя на другой ответ, сортировка происходит во время вставки. Этот компонент может рассматриваться как своего рода. Эта подпрограмма, однако, не создает этот порядок - она ​​просто восстанавливает его.

Взгляните на классическое определение для сортировки:

1. Выходные данные находятся в неубывающем порядке (каждый элемент не меньше предыдущего элемента в соответствии с желаемым общим порядком)
2. Выход представляет собой перестановку или переупорядочение входа.

Часть 2, безусловно, выполняется: происходит преобразование структуры хеша в список. Однако часть 1 не выполняется. Там нет определения порядка происходит. Порядок был предопределен во время вставки. Если бы это было «сортировка», то следующее также будет сортировка:

my @data = ... ;
my $index = -1;
my %stored = map { ++$index; $_ => { order => $index } } @data;
my @remade_data;
@remade_data[(map { $stored{$_}{order} } keys %stored)] = keys %stored;

Как вы можете видеть, в этом куске кода сортировка не происходит, просто преобразование.

Answer 4

Я думаю, что это не что иное, как вставка.