Алгоритм и алгоритмы сортировки

11. Гномья сортировка – алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.
12. Блочная сортировка – алгоритм сортировки, в которой сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив.
13. Поразрядная сортировка — быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки перфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый алгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для старших букв.
14. Цифровая сортировка.

   Цифровая  сортировка обладает линейной вычислительной сложностью, что является лучшей возможной производительностью для алгоритма сортировки, так как в любом таком алгоритме каждый сортируемый элемент необходимо просмотреть хотя бы однажды. Однако, применение алгоритма цифровой сортировки целесообразно лишь тогда, когда сортируемые предметы имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда несколько различных элементов попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Так что, для простоты и с целью отличить «классическую» цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт должен быть обратимым: если два элемента попадают в одну ячейку, то они должны иметь одинаковое значение. Несколько элементов с одним значением в одной ячейке не портят картину — их можно просто вставить в отсортированный список рядом, один за другим (это позволяет применять цифровую сортировку в качестве устойчивой).

   Алгоритм  цифровой сортировки действует следующим  образом:

1. Создаём массив изначально пустых «ячеек», по одной для каждой величины из диапазона ключей.
2. Просматриваем изначальный массив, помещая каждый его элемент в свою ячейку.
3. Проходим по массиву ячеек в нужном порядке и переносим элементы из непустых ячеек обратно в первоначальный массив.

   Эффективность этого алгоритма сильно зависит  от плотности элементов в массиве  ячеек. Если элементов этого массива  намного больше, чем сортируемых  предметов, то шаги 1 и 3 будут относительно медленными. 
 
 
 
 
 

2. Практическая  часть

Вариант №7.

1. Общая характеристика задачи

Используя ППП (пакет прикладных программ) необходимо подвести итоги о результатах расчета стоимости по полученному заказу фирмы ООО «Стройдизайн» по каждому виду работ.

Текст задачи:

Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением  по ремонту помещений. Прайс-лист на выполняемые работы приведены на рис. 7.1. Данные о заказанных работах  указаны на рис. 7.2.

1. Построить таблицы по приведенным ниже данным.
2. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (рис. 7.2).
3. Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
4. Сформировать и заполнить счет на оплату (рис. 7.3).
5. Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде.

Прайс-лист

Рис. 7.1. Прайс-лист на выполняемые работы 
 

Расчет  стоимости выполняемых  работ

Рис. 7.2. Данные о поступившем заказе

СЧЕТ

Рис. 7.3. Форма счета на оплату выполненных работ 
 

2. Описание  алгоритма решения задачи
1. Запустить табличный процессор MS Excel.
2. Создать книгу с именем «Стройдизайн».
3. Лист 1 переименовать в лист с названием Работы.
4. На рабочем листе Работы MS Excel создать таблицу базового прайс-листа.
5. Заполнить таблицу базового прайс-листа исходными данными (рис. 1).

Рис 1. Прайс-лист на выполняемые работы

6. Лист 2 переименовать в лист с названием Расчет.
7. На рабочем листе Расчет MS Excel создать таблицу, в которой будут содержаться данные о поступившем заказе (рис.2).

Рис 2. Данные о поступившем заказе.

8. Заполнить таблицу с данными о поступившем заказе. Заполнить графы Цена за ед. изм., руб., Стоимость работ, руб., находящейся на листе Расчет (рис. 3).

Заполнить ячейку Цена за ед. изм., руб. следующим образом:

• Занести в ячейку D3 формулу:

• Размножить  введенную в ячейку Е3 формулу  для остальных ячеек (с D3 по D6) данной графы.

Таким образом, будет выполняться цикл, управляющим параметром которого является Цена за ед. изм., руб. 

• Заполнить графу Стоимость работ, руб., таблицы «Данные о поступившем заказе», находящейся на листе Расчет следующим образом:
• Занести в ячейку E3 формулу:

• Размножить  введенную в ячейку E3 формулу для остальных ячеек (с E3 по E6) данные графы.

Таким образом, будет выполняться цикл, управляющим параметром которого является Стоимость работ, руб.

Рис 3. Данные о поступившем заказе

9. Лист 3 переименовать с названием Формы счета.
10. Заполнить таблицу Форма счета на оплату выполненных работ.
11. На рабочем листе Форма счета MS Excel создать форму заказа.
12. Путем создания межтабличных связей заполнить созданную форму полученными данными из таблицы «Данные о поступившем заказе».
13. Заполнить графу Цена за ед. изм., руб., таблицы «Форма счета на оплату выполненных услуг», находящейся на листе Форма счета следующим образом:

• Занести в ячейку Е7 формулу:

• Размножить  введенную в ячейку Е7 формулу  для остальных ячеек (с Е7 по Е10) данной графы.

14. Заполнить графу Объем выполняемых работ, таблицы «Форма счета на оплату выполненных услуг», находящейся на листе Форма счета следующим образом:

• Занести в ячейку D7 формулу:

• Размножить  введенную в ячейку D7 формулу для остальных ячеек (с D7 по D10) данной графы.

15. Заполнить графу Стоимость работ, руб., таблицы «Форма счета на оплату выполненных услуг», находящейся на листе Форма счета следующим образом:

• Занести в ячейку Е7 формулу: 

• Размножить  введенную в ячейку Е7 формулу  для остальных ячеек (с Е7 по Е10) данной графы.

16. В ячейку F11 занести формулы суммы значений ячеек с F7 по F10:

=СУММ(F7:F10)

17. В ячейку F12 занести значение НДС 18%, для этого выбрать формат ячейки "процентный".
18. В ячейку F13 вводим формулу:

=F11-(F11*F12) 

Рис 4. Форма счета на оплату выполняемых работ 

19.  Лист 4 переименовать в лист с названием График.
20. На рабочем листе График MS Excel создать сводную таблицу. Путем создания межтабличных связей автоматически заполнить графы Наименование работы и Стоимость работ, руб.
21. Заполнить графу Стоимость работ, руб., сводной таблицы, находящейся на листе График следующим образом:

• В ячейку B4 вводим формулу:

= ЕСЛИ(A4="";"";ПРОСМОТР(A4;Расчет!$A$3:$A$6;Расчет!$E$3:$E$6)).

• Размножить введенную в ячейку B4 формулу для остальных ячеек (с B4 по B7) данной графы.
• В ячейку B9 занести формулы суммы значений ячеек с B4 по B7: