Сортировка вставкой
Вход:
- Массив чисел (a1, a2, a3, …, an);
Выход:
- Сортированный массив в возростающем порядке
Insertion-Sort(A)
1. Для i = 1 до конца массива
1.1. Установить key = A[i]
1.2. Установить j = i-1
1.3. Пока j > 0 И A[j] > key
1.3.1. Установить A[j+1] = A[j]
1.3.2. Установить j = j - 1
1.4. Установить A[j+1] = key
Пример
my @origin_array = (12, 9, 7, 7, 10, 5, 7);
my @sort_array = MySort::insertion_sort(@origin_array);
warn "\n\n";
warn "result = @sort_array";
sub insertion_sort {
my @array = @_;
for ( my $i = 1; $i < @array; $i++ ) {
my $tmp = $array[$i];
my $j = $i - 1;
while ( $j >= 0 && $array[$j] > $tmp ){
$array[$j + 1] = $array[$j];
$j--;
}
$array[$j + 1] = $tmp;
}
return @array;
}
$ perl script.pl
result = 5 7 7 7 9 10 12 at script.pl line 17.
benchmark
my ( $check, $size) = ( 1, 9999 );
my @origin_array = (0..$size);
my $length = scalar(@origin_array);
timethese(0, {
'insertion' => sub {
my @shuffle_array = shuffle @origin_array;
my @sort_array = MySort::insertion_sort(@shuffle_array);
check_sort(\@sort_array, \@origin_array) if $check;
},
});
sub check_sort {
my ( $origin_array, $sort_array ) = @_;
foreach my $i ( 0..$length - 1 ){
die "Array is different! origin_array = $origin_array->[$i]; sort_array = $sort_array->[$i]; "
if ( $origin_array->[$i] != $sort_array->[$i] );
}
}
$ perl benchmark.pl
Benchmark: running insertion for at least 3 CPU seconds...
insertion: 6 wallclock secs ( 5.89 usr + 0.00 sys = 5.89 CPU) @ 0.34/s (n=2)
(warning: too few iterations for a reliable count)
Сортировка слиянием
Вход:
- Массив целых чисел (a1, a2, a3, …, an);
Выход:
- Сортированный массив в возростающем порядке
Merge-Sort(A)
1. Если кол-во элементов в массиве меньше или равен одному, вернуть его
2. В противном случае:
A. Вычислить середину массива: кол-во эл. / 2
B. Вызвать Merge-Sort( A[0, middle - 1] ) и записать результат в массив left
С. Вызвать Merge-Sort( A[middle, длина массива - 1] ) и записать результат в массив right
D. Вызвать Merge(right, left)
Merge(right, left)
Вход:
- два отсортированных массива
Результат: один отсортированный массив
1. Установить значение i и j равным нулю
3. Обьявить пустой массив tmp
2. Пока i меньше кол-ва эл. массива left и j меньше кол-ва эл. right
A. Если left[$i] < right[j], добавить эл. left[$i] во временный массив tmp и увеличить i на 1
B. В противном случае(left[$i] > right[j]), добавить эл. right[$j] во временный массив tmp и увеличить j на 1
3. Если кол-во эл. в массиве left меньше i, то добавить их в массив tmp
4. Если кол-во эл. в массиве right меньше j, то добавить их в массив tmp
5. Вернуть получившийся массив
Пример
my @origin_array = (12, 9, 7, 7, 10, 5, 7);
my @sort_array = MySort::merge_sort(@origin_array);
warn "result = @sort_array";
sub merge_sort {
my @array = @_;
my $lenght = @array;
return @array if ( $lenght <= 1 );
my $mid = int ( $lenght / 2 );
my @left = merge_sort( @array[0..$mid - 1] );
my @right = merge_sort( @array[$mid..$lenght - 1] );
merge(\@left, \@right);
}
sub merge {
my ($left, $right) = @_;
my @a1 = @{ $left || [] };
my @a2 = @{ $right || [] };
my @tmp;
my ($i, $j) = (0, 0);
while ( $i < @a1 && $j < @a2 ){
push @tmp, ( $a1[$i] < $a2[$j] ? $a1[$i++] : $a2[$j++] );
}
push @tmp, @a1[$i..$#a1] if ( $i < @a1 );
push @tmp, @a2[$j..$#a2] if ( $j < @a2 );
@tmp;
}
$ perl script.pl
result = 5 7 7 7 9 10 12 at script.pl line 20.
Если с debug:
$ perl script.pl
origin array = 12 9 7 7 10 5 7
origin array = 12 9 7
origin array = 12
left = 12
origin array = 9 7
origin array = 9
left = 9
origin array = 7
right = 7
i = 0; j = 0
7 9
right = 7 9
i = 0; j = 0
i = 0; j = 1
7 9 12
left = 7 9 12
origin array = 7 10 5 7
origin array = 7 10
origin array = 7
left = 7
origin array = 10
right = 10
i = 0; j = 0
7 10
left = 7 10
origin array = 5 7
origin array = 5
left = 5
origin array = 7
right = 7
i = 0; j = 0
5 7
right = 5 7
i = 0; j = 0
i = 0; j = 1
5 7 7 10
right = 5 7 7 10
i = 0; j = 0
i = 0; j = 1
i = 0; j = 2
i = 0; j = 3
i = 1; j = 3
i = 2; j = 3
5 7 7 7 9 10 12
result = 5 7 7 7 9 10 12 at script.pl line 20.
Сравнение двух алгоритмов
При достаточно малом кол-ве элементов(здесь перемешанный массив из 100 эл.), оба алгоритма примерно равны. Метод разделения даже немного проигрывает
$ perl benchmark.pl
Benchmark: running insertion, merge_sort for at least 3 CPU seconds...
insertion: 3 wallclock secs ( 3.05 usr + 0.00 sys = 3.05 CPU) @ 2899.67/s (n=8844)
merge_sort: 3 wallclock secs ( 3.23 usr + 0.00 sys = 3.23 CPU) @ 2535.60/s (n=8190)
Но когда элементов становиться больше(в данном случае 10к), разница ощущается
$ perl benchmark.pl
Benchmark: running insertion, merge_sort for at least 3 CPU seconds...
insertion: 3 wallclock secs ( 3.49 usr + 0.00 sys = 3.49 CPU) @ 0.29/s (n=1)
(warning: too few iterations for a reliable count)
merge_sort: 2 wallclock secs ( 3.12 usr + 0.00 sys = 3.12 CPU) @ 12.50/s (n=39)
Упражнения 1
2.1.1
Используя рис. 2.2 в качестве образца, проиллюстрируйте работу процедуры Insertion-Sort по сортировке массива A = (31, 41, 59, 26, 41, 58)
a. (31, 41, 59, 26, 41, 58);
<-
b. (31, 41, 59, 26, 41, 58);
<-
c. (31, 41, 59, 26, 41, 58);
-> -> -> |
|<-----------|
d. (26, 31, 41, 59, 41, 58);
-> |
<----|
e. (26, 31, 41, 41, 59, 58);
e. (26, 31, 41, 41, 59, 58);
-> |
<----|
2.1.2
Перепишите процедуру Insertion-Sort для сортировки в невозрастающем порядке вместо неубывающего
Изменил знак с большего на меньшее, проверил - работает
sub insertion_sort {
my @array = @_;
for ( my $i = 1; $i < @array; $i++ ) {
my $tmp = $array[$i];
my $j = $i - 1;
while ( $j >= 0 && $array[$j] < $tmp ){
$array[$j + 1] = $array[$j];
$j--;
}
$array[$j + 1] = $tmp;
}
return @array;
}
2.1.3
Рассмотрим задачу поиска. Вход: Массив чисел и значение u Выход: индекс i такой что u = A[i], или спец. знач. undef если u в A отсутствует Составьте псевдокод линейного поиска, при работе которого выполняется сканирование массива в поисках значения u. Докажите корректность алгоритма с помощью инварианта цикла. Убедитесь, что выбранный инвариант цикла удовлетворяет трем необходимым условиям.``` 1. Для i до конца массива A. Если A[i] == u, то вернуть i 2. Вернуть undef ```
инвариант не делал
2.1.4 - todo
Рассмотрим задачу сложения двух n-битовых двоичных целых чисел, хранящихся в n-элементных массивах A и B. Сумму этих двух чисел необходимо занести в двоичной форме в (n+1)-элементный массив C. Приведите строгую формулировку задачи и составьте псевдокод для сложения этих двух чисел.
Упражнения 2
2.2.1 - todo
Выразите функцию n^3/1000 — 100n^2 — 100n + 3 в ©-обозначениях.
2.2.2 - todo
Рассмотрим сортировку элементов массива А, которая выполняется следующим образом. Сначала определяется наименьший элемент массива А, который ставится на место элемента А[1]. Затем производится поиск второго наименьшего элемента массива А, который ставится на место элемента А[2]. Этот процесс продолжается для первых n — 1 элементов массива А. Запишите псевдокод этого алгоритма, известного как сортировка выбором (selection sort). Какой инвариант цикла сохраняется для этого алгоритма? Почему его достаточно выполнить для первых п — 1 элементов, а не для всех п элементов? Определите время работы алгоритма в наилучшем и наихудшем случаях и запишите его в ©-обозначениях.
2.2.3 - todo
Вновь обратимся к алгоритму линейного поиска (см. упр. 2.1.3). Для скольких элементов входной последовательности в среднем нужно произвести проверку, если предполагается, что все элементы массива с равной вероятностью могут иметь искомое значение? Что происходит в наихудшем случае? Чему равно время работы алгоритма линейного поиска в среднем и в наихудшем случаях в ©- обозначениях? Обоснуйте свой ответ.
2.2.4 - todo
Каким образом можно модифицировать почти каждый алгоритм, чтобы получить оптимальное время работы в наилучшем случае?