Это допустимая форма вставки сортировки?

Question

Представляет ли следующий код допустимую реализацию сортировки вставок ?

use warnings;

@arr = (5, 2, 4, 6, 1, 3);
$size = @arr;
print "\nUnsorted array: @arr\n";

for ( $i = 1; $i < $size; $i++ ) {

    while ( $i > 0 && $arr[$i] < $arr[$i-1] ) {

        ($arr[$i], $arr[$i-1]) = ($arr[$i-1], $arr[$i]);
        $i--;
    }
}

print "Sorted Array:   @arr\n";

Answer 1

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

for my $i (1..#$arr) {
    my $j = $i;
    while ( $j > 0 && $arr[$j] < $arr[$j-1] ) {
        ($arr[$j], $arr[$j-1]) = ($arr[$j-1], $arr[$j]);
        $j--;
    }
}

Я добавил my $j = $i; и переключился с $i на $j во внутреннем цикле. Изменение цикла for не является функциональным изменением; это просто чище и быстрее.

Теперь алгоритм идентичен первому алгоритму, показанному в Wikipedia .

В общем, думайте о @arr как о двух массивах. Ведущие элементы образуют отсортированный массив, а конечные элементы образуют несортированный массив элементов для вставки. $i является индексом первого элемента несортированных элементов, и внутренний цикл вставляет $arr[$i] в нужное место.

Answer 2

Да. Он идентичен первому алгоритму, показанному в Википедии