Компьютер – это сложное устройство, работающее под напряжением, поэтому на него тоже распространяются техника безопасности к электрическим устройствам. Применимо к компьютеру соблюдайте основные правила:
· Не работайте с компьютером при наличии внешних повреждений корпуса или изоляции силовых кабелей. В этом случае требуется замена кабелей или обращение в сервисный центр.
· Не кладите на корпус системного блока и не храните на нем разные предметы, особенно тяжелые, т.к. в этом случае может возникнуть вибрация, которая может вызвать нарушения работы компьютера.
· Не рекомендуется включать компьютер в розетки без заземления. Розетки и вилки должны быть цельными, без повреждений.
· Не включайте компьютер в помещении с высокой влажностью.
· Не оставляйте работающий ПК без присмотра длительное время.
· Провода и силовые кабеля компьютера должны быть расположены так, чтобы исключить возможность наступить на них или поставить что-то тяжелое.
· Нельзя работать с компьютером при открытом корпусе системного блока.
Разработка и реализация алгоритма пирамидальной сортировки.
Метод пирамидальной сортировки, изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева.
Пирамидой (кучей) называется двоичное дерево такое, что
· a[i] ≤ a[2i+1];
· a[i] ≤ a[2i+2].
Подробнее
a[0] — минимальный элемент пирамиды.
Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.
Выполнение алгоритма разбивается на два этапа.
1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.
Например, массив для сортировки
24, 31, 15, 20, 52, 6
Расположим элементы в виде исходной пирамиды; номер элемента правой части (6/2-1)=2 — это элемент 15.
Результат просеивания элемента 15 через пирамиду.
Следующий просеиваемый элемент – 1, равный 31.
Затем – элемент 0, равный 24.
Разумеется, полученный массив еще не упорядочен. Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.
2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.
Продолжим процесс. В итоге массив будет отсортирован по убыванию.
Реализация пирамидальной сортировки на Си
#include <stdio.h>
#include <stdlib.h>
// Функция "просеивания" через кучу - формирование кучи
void siftDown(int *numbers, int root, int bottom)
{
int maxChild; // индекс максимального потомка
int done = 0; // флаг того, что куча сформирована
// Пока не дошли до последнего ряда
while ((root * 2 <= bottom) && (!done))
{
if (root * 2 == bottom) // если мы в последнем ряду,
maxChild = root * 2; // запоминаем левый потомок
// иначе запоминаем больший потомок из двух
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
// если элемент вершины меньше максимального потомка
if (numbers[root] < numbers[maxChild])
{
int temp = numbers[root]; // меняем их местами
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else // иначе
done = 1; // пирамида сформирована
}
}
// Функция сортировки на куче
void heapSort(int *numbers, int array_size)
{
// Формируем нижний ряд пирамиды
for (int i = (array_size / 2) - 1; i >= 0; i--)
siftDown(numbers, i, array_size - 1);
// Просеиваем через пирамиду остальные элементы
for (int i = array_size - 1; i >= 1; i--)
{
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i - 1);
}
}
int main()
{
int a[10];
// Заполнение массива случайными числами
for (int i = 0; i<10; i++)
a[i] = rand() % 20 - 10;
// Вывод элементов массива до сортировки
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
printf("\n");
heapSort(a, 10); // вызов функции сортировки
// Вывод элементов массива после сортировки
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
printf("\n");
getchar();
return 0;
}
Результат выполнения
5.Анализ алгоритма в том числе с применением инструментальных средств.
Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших n. В худшем случае требуется n·log2n шагов, сдвигающих элементы. Среднее число перемещений примерно равно
(n/2)·log2n,
и отклонения от этого значения относительно невелики.