Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями
Содержимое удалено Содержимое добавлено
м →Python |
Добавлены примеры на Rust; исправлено форматирование в Python |
||
Строка 627:
==[[w:Python|Python]]==
Приведённые алгоритмы упорядочивают принимаемую последовательность ''sequence'' (список, символьную строку) по неубыванию (''sequence[i] ≤ sequence[i + 1]''). Для упорядочения по невозрастанию (''sequence[i] ≥ sequence[i + 1]'') необходимо заменить '''все''' знаки
Для большей эффективности вычислений умножение
Проверить работу любой из функций можно добавив, например, следующий код (
<source lang="python">
count = 30 # Количество значений в последовательности
Строка 655:
if child >= limit:
break
if child + 1 < limit and sequence[child] < sequence[child + 1]:
child += 1
if item < sequence[child]: # !
Строка 701:
swap_items(index, 0)
sift_down(0, index)
</source>
==Rust==
Приведённые алгоритмы упорядочивают принимаемую последовательность ''sequence'' (в её качестве могут выступать массив (array), вектор (Vec), срез (slice)) по неубыванию (''sequence[i] ≤ sequence[i + 1]''). Для упорядочения по невозрастанию (''sequence[i] ≥ sequence[i + 1]'') необходимо заменить '''все''' знаки <code><</code> на <code>></code> в строках, помеченных <code>// !</code>
Для большей эффективности вычислений умножение и деление нацело на 2 производятся операторами побитового сдвига влево (<code><<</code>) и вправо (<code>>></code>) соответственно. Например <code>parent << 1</code> вместо <code>parent * 2</code>, <code>length >> 1</code> вместо <code>length / 2</code> и т. п.
Проверить работу любой из функций можно добавив, например, следующий код (следует учитывать, что в Rust массивы до 32 элементов могут выводиться макросами <code>print!</code> и <code>println!</code>; для более длинных придётся писать собственную функцию вывода):
<source lang="rust">
fn main () {
let mut sequence = [0i32; 30]; // Массив из 30 элементов
let mut value = sequence.len() as i32;
// Заполнение последовательности убывающими значениями
for i in 0..sequence.len() {
sequence[i] = value;
value -= 1;
// Для заполнения возрастающими значениями закомментируйте две предыдущие строки и раскомментируйте следующую:
sequence[i] = i as i32 + 1;
}
// Вывод исходной последовательности
println!("Исходная последовательность:\n{:?}", sequence);
// Упорядочение последовательности
heap_sort(&mut sequence);
// Вывод упорядоченной последовательности
println!("Упорядоченная последовательность:\n{:?}", sequence);
}
</source>
===Вариант № 1===
<source lang="rust">
fn heap_sort <T: PartialOrd> (sequence: &mut[T]) {
let length = sequence.len();
let mut offset = 0usize;
let mut flag = false;
while {
for index in 0..length {
let left = (index << 1) + 1 + offset; // Индекс левого ребёнка
let right = left + 1; // Индекс правого ребёнка
if right < length { // Если существуют оба ребёнка
if sequence[left] < sequence[index + offset] || sequence[right] < sequence[index + offset] { // !
if sequence[left] < sequence[right] { // !
sequence.swap(index + offset, left);
flag = true;
} else if sequence[right] < sequence[left] { // !
sequence.swap(index + offset, right);
flag = true;
}
}
// Дополнительная проверка для последних двух элементов;
// с её помощью можно отсортировать пирамиду состоящую всего лишь из трёх элементов
if sequence[right] < sequence[left] { // !
sequence.swap(left, right);
flag = true;
}
} else if left < length { // Если существует только один ребёнок
if sequence[left] < sequence[index + offset] { // !
sequence.swap(index + offset, left);
flag = true;
}
}
}
if flag {
flag = false;
} else {
offset += 1; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
}
offset + 2 < length // Условие повторения цикла while
} { }
}
</source>
===Вариант № 2===
По сравнению с предыдущим вариантом элементы последовательности также должны быть ''копируемыми'' (реализовывать типаж <code>Copy</code>).
<source lang="rust">
fn heap_sort <T: PartialOrd + Copy> (sequence: &mut[T]) {
fn sift_down <T: PartialOrd + Copy> (sequence: &mut[T], root: usize, limit: usize) {
let mut parent = root;
let mut child: usize;
let item = sequence[root]; // Элемент, для которого ищется место в последовательности
while {
child = (parent << 1) + 1;
child < limit // Условие повторения № 1: у sequence[parent] есть хоть один ребёнок
} && {
// Выбор большего из детей sequence[parent]
if child + 1 < limit && sequence[child] < sequence[child + 1] {
child += 1;
};
item < sequence[child] // Условие повторения № 2: item меньше наибольшего из детей sequence[parent]
} { // Тело цикла
sequence[parent] = sequence[child]; // Сдвигаем ребёнка на место его родителя
parent = child;
}
if parent > root { // Если в ходе предыдущей отработки цикла делались сдвиги
sequence[parent] = item; // Перемещаем item на найденное для него место
}
};
// Формирование первичной пирамиды
let length = sequence.len();
let mut index = length >> 1; // Индекс родителя последнего элемента последовательности
while index > 0 {
index -= 1;
sift_down(sequence, index, length);
}
// Окончательное упорядочение
index = length;
while index > 1 {
index -= 1;
sequence.swap(0, index); // Обмен крайних элементов неупорядоченной части последовательности
sift_down(sequence, 0, index); // Восстановление свойства пирамиды в неупорядоченной части последовательности
}
}
</source>
| |||