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

    Сортировка  слиянием

    Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную. Время работы сортировки слиянием намного меньше, чем у пузырьковой сортировки. [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]

 

Прайс-лист

 

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

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

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

 

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

    Решение:

    1. Запустим табличный процессор  MS Excel. Для этого выполним команду  Пуск / Программы / Microsoft Office / Microsoft Office Excel.

    2. Создадим на рабочем столе  книгу с именем «Стройдизайн».  Для этого выполним команду  Файл / Создать / Чистая книга. Далее выполним Файл / Сохранить как. В окне «Сохранение файла» выберем папку «Рабочий стол», а в поле «Имя файла» введем название «Стройдизайн».

    3. Лист 1 переименуем в лист с  названием «Услуги». Для этого  дважды  щелкнем мышью по ярлыку  Листа 1 и наберем имя «Услуги».

    4. На рабочем листе «Услуги»  MS Excel создадим таблицу базового прайс-листа.

    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. Расположение таблицы «Базовый прайс-лист» на рабочем листе «Услуги» MS Excel

    6. Лист 2 переименуем в лист с  названием «Расчет стоимости» (порядок  действий представлен в пункте 3.).