Алгоритмы сортировки 2 (стр. 2 из 3)
Следующий этап — 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов. [5, стр. 202-213]
Сортировка слиянием
Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную. Время работы сортировки слиянием намного меньше, чем у пузырьковой сортировки. [6]
Пирамидальная сортировка
Этот метод является значительно более сложным, но при этом и более быстрым (особенно на больших массивах информации) алгоритмом. Здесь используется промежуточное преобразование данных к специальному представлению, которое позволяет производить дальнейшую сортировку быстрее. В результате, общее число сравнений и обменов записей местами существенно уменьшается, что особенно важно в случае больших массивов данных.
После первого этапа работы алгоритма массив данных преобразуется таким образом, что максимальный элемент (временно) размещается в самой первой записи и для всех элементов верны неравенства: a (j) > a (2*j) и a(j) > a (2*j+1), если соответствующие элементы все еще лежат внутри массива. Пари этом a – элемент массива; j – его порядковый номер. Последующие этапы работы алгоритма приводят к тому, что максимальный в данный момент элемент отправляется на правильное место в отсортированном массиве, а для всех остальных элементов сохраняются такие же неравенства. [5, стр. 214-215]
Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево – это такое двоичное дерево, у которого выполнены условия:
· Каждый лист имеет определенную глубину;
· Значение в любой вершине больше, чем значения ее потомков.
И первоначальное преобразование, и последующий этап работы требует относительно небольшого числа операций, так что на больших массивах получается значительный выигрыш. Особенность этого алгоритма состоит в том, что он хорошо работает при любом начальном порядке данных в массиве, в то время как некоторые более быстрые (в среднем) методы могут очень неудачно обрабатывать определенные, специально подобранные наборы данных. [8]
Линейная сортировка (сортировка отбором)
Идея линейной сортировки по невозрастанию заключается в том, что
последовательно просматривая весь массив, отыскать наибольшее число и поместить его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива, и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и первого в рассматриваемой части и т.д.
Метод быстрой сортировки с разделением
Значительно эффективнее работает алгоритм сортировки К. Хора, который также называют сортировкой с разделением или «быстрой сортировкой». В основу алгоритма положен метод последовательного дробления массива на части. Для начала, определяется элемент, стоящий в середине массива, после чего массив делится на две части. При просмотре левой части массива слева направо выполняется поиск такого элемента массива, что M[I] > X, затем при просмотре правой части справа налево отыскивается такой элемент, что M[I] < X (при этом: М – имя массива; I – номер элемента в массиве; X – элемент, оказавшийся в середине массива). Выполняется обмен местами данных элементов, пока все элементы слева от середины, удовлетворяющие условию M[I] > X, не будут обменены с элементами, расположенными справа от середины и удовлетворяющими условию M[I] < X . В результате этого получается массив из двух частей. Далее левая часть в свою очередь дробится на две части и сортируется описанным выше способом. Этот процесс происходит до тех пор, пока в каждой из частей не останется по одному элементу. Затем аналогично сортируется правая часть первоначального массива.
Алгоритм быстрой сортировки дает лучшие результаты, чем пузырьковый метод, однако следует учесть, что в некоторых случаях это преимущество снижается. Например, если применить эту сортировку к массиву, содержащему несколько одинаковых элементов. [4, стр.195-197; 199-201]
II. ПРАКТИЧЕСКАЯ ЧАСТЬ
Вариант 7
Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен на рис. 1. Данные о заказанных работах указаны на рис.2.
1. Построить таблицы по приведенным ниже данным.
2. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (рис. 2).
3. Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
4. Сформировать и заполнить счет на оплату (рис. 3).
5. Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде. [1, стр. 30-31]
Прайс-лист
| Наименование работы | Единица измерения | Цена за ед. изм., руб. |
| Замена батарей | шт. | 250 |
| Замена ванны | шт. | 210 |
| Замена труб | м | 240 |
| Наклейка обоев | м² | 50 |
| Настилка паркета | м² | 75 |
| Побелка потолка | м² | 15 |
Рис. 1. Прайс-лист на выполняемые работы
Расчет стоимости выполняемых работ
| Наименование работы | Единица измерения | Объем выполняемых работ | Цена за ед. изм., руб. | Стоимость работ, руб. |
| Замена батарей | шт. | 4 | 250 | |
| Наклейка обоев | м² | 20 | 50 | |
| Замена труб | м | 4 | 240 | |
| Настилка паркета | м² | 15 | 75 |
Рис. 2. Данные о поступившем заказе
ООО "Стройдизайн" | ||||||
| Счет № 1 | ||||||
| Дата | __.__.20__ | |||||
| ФИО клиента | ______________________ | |||||
| № п/п | Наименование работы | Единица измерения | Объем выполняемых работ | Цена за ед. изм., руб. | Стоимость работ, руб. | |
| 1 | Замена батарей | шт. | ||||
| 2 | Наклейка обоев | м² | ||||
| 3 | Замена труб | м | ||||
| 4 | Настил паркета | м² | ||||
| ИТОГО: | ||||||
| НДС: | ||||||
| СУММА С НДС: | ||||||
| Гл. бухгалтер ________________________ | ||||||
Рис. 3. Форма счета на оплату выполненных работ
Решение:
1. Запустим табличный процессор MSExcel. Для этого выполним команду Пуск / Программы / MicrosoftOffice / MicrosoftOfficeExcel.
2. Создадим на рабочем столе книгу с именем «Стройдизайн». Для этого выполним команду Файл / Создать / Чистая книга. Далее выполним Файл / Сохранить как. В окне «Сохранение файла» выберем папку «Рабочий стол», а в поле «Имя файла» введем название «Стройдизайн».
3. Лист 1 переименуем в лист с названием «Услуги». Для этого дважды щелкнем мышью по ярлыку Листа 1 и наберем имя «Услуги».
4. На рабочем листе «Услуги» MSExcel создадим таблицу базового прайс-листа.
5. Заполним таблицу базового прайс-листа исходными данными (рис. 4).
5.1. На первой строке для ячеек А, В и С выполним объединение. Для
этого, выделив интересующий нас диапазон, на панели инструментов
нажмем на кнопку «Объединить и поместить в центре»
5.2. Для расширения ширины столбцов в диапазоне ячеек А2:С2, наведем курсор на правую границу столбца А (далее и других столбцов поочередно), так чтобы курсор превратился в черный крестик со стрелками. Далее щелкнув один раз левой кнопкой мыши, и удерживая ее в этом положении, «потянем» границу вправо до нужного нам размера. Для расширения строки выполняются те же действия, что и для столбца, а курсор необходимо будет подвести к нижней границе строки 2.
5.3. Выделим диапазон А2:С2, и щелкнув нем правой кнопкой мыши выберем меню «Формат ячеек». В нем на вкладке «Число» выберем текстовый формат, на вкладке «Выравнивание» установим значение «по центру», и выберем в пункте отображения – «Переносить по словам».
5.4. Следует заметить, что в графе «Единица измерения» присутствует значение «м²». Для указания степени «²» следует установить курсор за «м» и выполнить действия Вставка / Символ . В поле «Набор» выберем «Латиница-1», найдем интересующий нас символ, выберем его и нажмем ОК.
5.5. В заключении, подкорректируем ширину строки 2 и столбцов А, В и С, для диапазона ячеек В3:В8 и С3:С8 установим выравнивание «по центру», а для А3:А8 – «по левому краю» (порядок действий представлен в пунктах 5.2 и 5.3.).
Рис. 4. Расположение таблицы «Базовый прайс-лист» на рабочем листе «Услуги» MSExcel
6. Лист 2 переименуем в лист с названием «Расчет стоимости» (порядок действий представлен в пункте 3.).
7. На рабочем листе «Расчет стоимости» создадим таблицу, в которой будет содержаться данные о поступившем заказе.