Алгоритмы сортировки данных (Понятие алгоритма)

Содержание:

ВВЕДЕНИЕ

В наше время новые информационные технологии занимают очень важное место не только в специализированных, но и в повседневных сферах жизни. Компьютеры применяются в бизнесе, менеджменте, торговле, учебе и многих других сферах деятельности человека.
Успешное выполнение большинством специалистов своих функциональных обязанностей в настоящее время во многом определяется умелым использованием персональных компьютеров, средств коммуникаций, профессиональных пакетов прикладных программ, различного рода интеллектуальных информационных технологий. Процессы информатизации общества обусловили необходимость формирования у студентов знаний в области информатики и компьютеризации управленческих процессов.

Компьютерные технологии очень удобны для выполнения разнообразных операций, но в разных сферах применения эти операции разные. Потому, каждая отдельная отрасль, которая использует специфические технические средства, нуждается в своих собственных программах, которые обеспечивают работу компьютеров.

Одно из широко используемых понятий информатики определяет ее как науку, изучающую общие свойства информации, а также методы, процессы, технические и программные средства для ее автоматизированной обработки.

Сам термин «информатика» (informatique) возник в 60-х годах во Франции для определения области исследований, связанных с автоматизацией обработки информации с помощью электронных вычислительных машин (ЭВМ). Этот термин был образован слиянием слов information (информация) и automatique (автоматика) для обозначения информационной автоматики или автоматизированной переработки информации.

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

Таким образом, задачами курсовой работы являются:

1. изучить теоретическую основу алгоритмов сортировки;

2. рассмотреть различные виды алгоритмов сортировки данных;

3. произвести анализ работы алгоритмов сортировки.

• 1. Теоретический обзор различных сортировочных алгоритмов

     1. Понятие алгоритма

Алгоритм – это точно определенная последовательность действий, которую необходимо выполнить над исходными данными для достижения решения задачи.

Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, который сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем это слово стало использоваться не только в математике, а фактически любую последовательность действий, приводящих к конечному результату, стали называть алгоритмом, а каждое действие шагом алгоритма. Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.

Формы представления алгоритма:

1. Словесная форма;
2. Словесно-аналитическая форма;
3. В виде блок-схемы (графическое изображение алгоритма);
4. В виде программы на алгоритмическом языке программирования.

Виды алгоритмических структур:

• 1. Линейный алгоритм, в которой все команды выполняются последовательно одна за другой.
  2. Разветвляющийся, в которой в зависимости от условия выполнения либо одна серия команд, либо другая.
  3. Циклический, в которой многократно повторяется некоторый участок алгоритма.

I-ое поколение алгоритмических языков - конец 1950-х начало 1960-х. Совершенствовались ассемблерные языки. В настоящее время они применяются для создания драйверов оборудования ПК.

II-ое поколение - 60е годы. В это время появляются универсальные языки высшего уровня: ФОРТРАН, АЛГОЛ, КОБОЛ, обеспечивающие создание программ для решения задач различного класса.

III-e поколение. С начала 1970-х годов начался переход на создание больших программных комплексов. Они в основном применяются для проектирования приложений баз данных и средств визуального программирования.

В середине 1990-х – 4 поколение языков программирования, назначение которых для образования инструкции текст программ на универсальном языке программирования. Система 4 поколения имеет открытую архитектуру и поддерживает значительное число программных продуктов.

Языки программирования:

1. Бейсик отличается встроенными математическими функциями и простыми языковыми конструкциями.
2. Паскаль предназначен для решения вычислительных и информационно-логических задач.
3. Си + + был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую.
4. Ада ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем.
5. Java (джава) предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети.
6. другим объектно-ориентировочным языком является язык Delphi (дельпхи). Обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети интернет.
7. История разработок алгоритмов сортировки

Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах. У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. При работе с машиной от оператора требовалось вставить перфокарту и опустить рукоятку. Благодаря пробитым на перфокарте отверстиям замыкалась определённая электрическая цепь, и на единицу увеличивалось показание связанного с ней циферблата. Одновременно с этим открывалась одна из 26 крышек сортировального ящика, и в соответствующее отделение перемещалась перфокарта, после чего крышка закрывалась. Данная машина позволила обрабатывать около 50 карт в минуту, что ускорило обработку данных в 3 раза. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт. Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки. В патенте на машину обозначена сортировка «по отдельности для каждого столбца», но не определён порядок. В другой аналогичной машине, запатентованной в 1894 году Джоном Гором, упоминается сортировка со столбца десятков. Метод сортировки, начиная со столбца единиц, впервые появляется в литературе в конце 1930-х годов. К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту.

В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ. Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли, прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчетов, описал методы сортировки простой вставки и бинарных вставок, а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Эккертом компания «Eckert–Mauchly Computer Corporation» выпустила некоторые из самых ранних электронных вычислительных машин BINAC и UNIVAC. Наряду с отмеченными алгоритмами внутренней сортировки, появлялись алгоритмы внешней сортировки, развитию которых способствовал ограниченный объём памяти первых вычислительных машин. В частности, были предложены методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния.

К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо. В октябре 1952 года Даниэль Гольденберг привёл пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой. Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьёй о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложив некоторые новые методы.

После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки. Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям.

Что представляет собой алгоритм сортировки

Сортировка – один из наиболее распространенных процессов современной обработки данных. Задачи на сортировку данных встречаются на компьютере очень часто. Главным образом, это связано с тем, что разбираться в отсортированных данных намного проще, чем в неотсортированных.

Алгоритм сортировки — это порядок действий для упорядочения элементов в списке. Обычно говорят о сортировке записей (содержащих любые данные) по ключам – фрагментам этих записей, допускающих отношение упорядочения. Например, ключи могут быть числами (в этом случае используется естественный математический порядок возрастания или убывания чисел) или строковыми значениями (в этом случае упорядочение производится по алфавиту).

Наверно, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Возможно, нет. Однако, имея приблизительные характеристики исходных данных, можно подобрать метод, работающий оптимальным образом.

Оценка алгоритма сортировки.

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

• Время сортировки. Основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью.

• Память. Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

• Устойчивость. Устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.

• Естественность поведения — эффективность метода при обработке уже

отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), то есть в данный момент мы «видим» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

1. Характеристика основных видов алгоритмов сортировки

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.

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

Практически каждый алгоритм сортировки можно разбить на три части:

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

Подобными свойствами обладают и те алгоритмы сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что, во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь.

Основные виды сортировок:

a)Сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

Сортировка методом пузырька имеет сложность O(n2). Для понимания и реализации это — простейший алгоритм сортировки, но эффективен он лишь для небольших массивов.

Пример реализации алгоритма (язык Pascal):

for i := n - 1 downto 1 do

for j := 1 to i do

if a[j] > a[j+1] then

begin

t := a[j];

a[j] := a[j+1];

a[j+1] := t;

end;

b)Сортировка перемешиванием (шейкер-сортировка) — разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие — к началу.

Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

c)Сортировка методом вставок (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

• прост в реализации
• эффективен на небольших наборах данных
• эффективен на наборах данных, которые уже частично отсортированы
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
• может сортировать список по мере его получения

На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива — произволен, может использоваться практически любой алгоритм выбора.

d)Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

Описание алгоритма:

Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.

e)Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй».

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

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

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

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

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

Сортировку подсчётом применяют редко, потому что её требования редко удовлетворяются, и часто бывает проще применить другие, более гибкие и почти такие же быстрые алгоритмы сортировки. В особенности, блочная сортировка является более практичным вариантом сортировки подсчётом. В некотором роде, быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).

g)Поразрядная сортировка — быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки перфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый алгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для старших букв.

h)Cортировка методом выбора (англ. selection sort) — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n²), предполагая, что сравнения делаются за постоянное время.

Шаги алгоритма:

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

Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных ключа для ускорения нахождения и удаления минимального элемента.

Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения.

i)Сортировка методом Шелла

Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.

Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап — 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Выполняется сортировка в каждой четверке.

Следующий этап — 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.

Анализ алгоритма сортировки Шелла:

Время выполнения сортировки пропорционально n^1.2. Эта зависимость значительно лучше квадратичной зависимости n², которой подчиняется большинство простых алгоритмов сортировки.

Пример реализации (Pascal)

procedure sort_shell (var a:array of word);

var

bis,i,j,k:longint;

h:word;

begin

bis:=high(a);

k:=bis shr 1;

While k>0 do

Begin

For i:=0 To bis-k do

begin

j:=i;

While (j>=0) And (a[j]>a[j+k]) do

begin

h:=a[j];

a[j]:=a[j+k];

a[j+k]:=h;

dec(j,k);

end;

end;

k:=k shr 1;

End;

j)Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (т.е. гарантированно) за О(n log n) операций при сортировке n элементов.

Алгоритм:

Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево – это такое двоичное дерево, у которого выполнены условия:

1. Каждый лист имеет глубину либо d либо d-1
2. Значение в любой вершине больше, чем значения ее потомков.

Удобная структура данных для сортирующего дерева – такой массив Array, что Array[1] – элемент в корне, а потомки элемента Array[i] - Array[2i] и Array[2i+1].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева:

при 

Этот шаг требует О(n) операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. Т.е. на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], ... , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], ... , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], ... , Array[n] - упорядоченная последовательность.

Этот шаг требует О(n log n) операций.

k)Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n²) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если отсортировать все слова в тексте, их переводы можно получить за один прогон ленты.

Алгоритм:

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
3. Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.

Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место.

Улучшения

При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(n log n).

II. Практическое описание алгоритмов сортировки

Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен на рис. 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. Запустим табличный процессор 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.).

7. На рабочем листе «Расчет стоимости» создадим таблицу, в которой будет содержаться данные о поступившем заказе.

8. Заполним таблицу данными о поступившем заказе (рис. 5).

8.1. Заполним таблицу исходными данными о заказе по графам «Наименование работы», «Единица измерения», «Объем выполняемых работ».

8.2. Для заполнения графы «Цена за единицу измерения, руб.» используем исходные данные базового прайс-листа. Заполним соответственно наименованию работы ее цену за единицу измерения в рублях.

8.3. Для расчета стоимости работ вычислим произведение объема работ на цену за единицу измерения.

8.3.1. Установим курсор на ячейке Е3 и выполним действия: Вставка / Функция. В окне «Мастер функций - шаг 1 из 2» выберем в категории «Полный алфавитный перечень» функцию ПРОИЗВЕД, и кнопкой ОК откроем следующее окно под названием «Аргументы функции». В нем в поле «Число 1» выберем ячейку С3, а в поле «Число 2» - ячейку D3. После нажатия кнопки ОК в ячейке Е3 будет рассчитана стоимость работ по замене батарей.

8.3.2. Для расчета стоимости работ по наклейке обоев, замене труб и настилке паркета копируем формулу, введенную в ячейке Е3. Для этого поднесем указатель мыши в правый нижний угол ячейки Е3. Когда указатель примет вид черного крестика, нажав левую кнопку мыши, выделим ячейки Е4, Е5, Е6. В результате будет рассчитана стоимость каждого из видов работ.

Рис. 5. Расположение таблицы «Расчет стоимости выполняемых работ» на рабочем листе «Расчет стоимости»

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

10. На рабочем листе «Счет» создадим таблицу для формирования счета, выставляемого клиенту для оплаты выполняемых работ.

11. На основе исходной таблицы, представленной на рис. 3, заполним форму данными из таблицы «Расчет стоимости». Заполненный счет на оплату работ представлен на рис. 6.

11.1. Следует заметить, что шапка таблицы расположена под углом 90° к основному тексту. Для достижения такого результата следует выделить диапазон ячеек А7:F7 путем удерживания левой кнопки мыши. Далее щелчком правой кнопки по выделенному диапазону выбрать из контекстного меню пункт «Формат ячеек». В открывшемся окне на вкладке «Выравнивание» в поле «Ориентация» установить 90°.

11.2. Для диапазонов ячеек А12:Е12, А13:Е13 и А14:Е14 следует выполнить объединение построчно. Для этого, выделив первый указанный диапазон, через контекстное меню «Формат ячеек» следует установить на вкладке «Выравнивание» значение «Объединение ячеек». В поле «Выравнивание» выберем значение «По правому краю» Таким же образом следует поступить с каждым из оставшихся двух диапазонов.

11.3. Для расчета итоговой стоимости выполняемых работ в ячейке F12 следует установить курсор и ввести функцию. Для этого выполним действия Вставка / Функция, в категории «Математические» выберем функцию «СУММ». Далее в открывшемся окне «Аргументы функции» в качестве первого числа через кнопку «Просмотр» выделим диапазон F8:F11 и нажмем ОК.

11.4. Для расчета НДС в ячейку F13 введем формулу самостоятельно. Для этого в ячейке поставим знак равенства «=», щелкнем мышью ячейку F12, далее поставим знак произведения «*», и наконец, введем с клавиатуры «18%». После нажатия «Enter» сумма НДС будет вычислена. Таким образом, НДС составил 18% от общей стоимости работ.

11.5. В ячейке F14 следует вычислить в рублях сумму, подлежащую оплате клиентом, включая НДС. Для этого, используя функцию «СУММ» сложим итоговую стоимость работ и начисленную сумму НДС (ячейки F12 и F13).

	А	В	С	D	E	F
1	ООО "Стройдизайн"
2	Счет № 1
3
4	Дата			01.04.2010
5	ФИО клиента			Петрова Татьяна Николаевна
6
7	№ п/п	Наименование работы	Единица измерения	Объем выполняемых работ	Цена за ед. изм., руб.	Стоимость работ, руб.
8	1	Замена батарей	шт.	4	250	1000
9	2	Наклейка обоев	м²	20	50	1000
10	3	Замена труб	м	4	240	960
11	4	Настил паркета	м²	15	75	1125
12	ИТОГО:					4085
13	НДС:					735,3
14	СУММА С НДС:					4820,3
15	Гл. бухгалтер Абокумова А.А./_________
16
17
18
19

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

12. Лист 4 переименуем в лист с названием «График» (порядок действий представлен в пункте 3).

13.Для представления результатов расчета стоимости каждого вида работ в графическом виде построим диаграмму (рис. 7).

13.1. Выполним действия Вставка / Диаграмма. В открывшемся окне на первом шаге построения диаграммы выберем на вкладке «Стандартные» гистограмму обычного вида, и нажмем кнопку «Далее».

13.2. В новом открывшемся окне на вкладке «Диапазон данных» с помощью кнопки «Просмотр» выделим диапазон F8:F11. В поле «Ряды в» установим значение «столбцах».

На вкладке «Ряд» в поле «Подписи оси Х» выберем через кнопку просмотра диапазон ячеек В8:В11, и нажмем кнопку «Далее».

13.3. На следующем этапе построения диаграммы, на вкладке «Заголовки» ось Х обозначим как «Виды работ», ось У – «Сумма (руб.)»

На вкладке «Линии сетки» в поле «Ось У (значений)» выберем только один пункт – «Основные линии».

На вкладке «Легенда», для того чтобы ее вовсе не включать в нашу диаграмму, уберем галочку напротив пункта «Добавить легенду», и нажмем кнопку «Далее».

13.4. На последнем этапе построения диаграммы в поле размещения ее на листе выберем пункт на листе «имеющемся», и через кнопку «Просмотр» укажем лист под названием «График».

13.5. Нажав кнопку «Готово» создание диаграммы будет завершено. При необходимости ее можно, щелкнув левой кнопкой мыши и удерживая в таком положении, «перетащить» в подходящее место на листе. Также с помощью контекстного меню (которое вызывается щелчком правой кнопки мыши) можно отредактировать любую область диаграммы.

Рис. 7. Результаты расчета стоимости каждого вида работ по полученному заказу.

Рис. 8.

ЗАКЛЮЧЕНИЕ

Современную жизнь представить без современной техники просто невозможно. Ни одна фирма не обходится без помощи компьютеров. Хранение данных, написание документов, составление графиков, таблиц, расписаний, создание презентаций - во всем в этом нам помогает компьютер, и помогает успешно.

Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. Алгоритмы сортировки представляют собой пошаговое упорядочение элементов в определенном массиве данных, независимо от его размеров.

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

- собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

Выбор метода сортировки в значительной мере зависит от объема и характеристики исходных данных. Но, в целом, основными параметрами, которыми руководствуется пользователь при выборе метода сортировки, являются время действия алгоритма, память, устойчивость сортировки и эффективность поведения алгоритма.

Наиболее известными и, одновременно, базовыми алгоритмами сортировки являются обменная, блочная, пирамидальная, линейная, быстрая сортировки, а также сортировки подсчетом, слиянием, перемешиванием и методом вставок. Каждый из этих методов имеет свои достоинства и недостатки.

Термин «алгоритм» применяют весьма широко. Алгоритм – это организованная последовательность действий, допустимых в определенных случаях. Умение разбить задачу на подзадачи, распределение решений этих задач, определение выходных параметров способствуют легкому восприятию любой ситуации.

В практической части данной курсовой работы решение экономической задачи производилось поэтапно, согласно разработанному алгоритму. Это позволило понять, насколько эффективно использовать программу MS Excel, если в работе часто используются различного рода таблицы, бланки, при заполнении которых производятся вычисления по формулам. Более того, на основе имеющихся в MS Excel шаблонов диаграмм, была получена наглядная картина данных таблицы. Причем, ограничений в выборе диаграммы не существует, помимо гистограммы данные могли быть представлены в виде обычного графика, объемной круговой, пузырьковой, и даже экзотической лепестковой или цилиндрической диаграмм.

Возможность алгоритмизировать свою деятельность всегда была привилегией профессионалов в любой области человеческой деятельности. Современные программные продукты, в том числе и фирмы Microsoft, подразумевают использование языков программирования и программных сред. Именно поэтому, отдельные вопросы программирования, в частности, использование существующих и разработка новых, более эффективных алгоритмов сортировки данных, играют немаловажную роль в развитии современных информационных технологий.

Для молодого специалиста, выпускника института, это весьма важная работа. В работе подробно описывается проектирование таблиц для автоматизации обработки экономических данных. Полученные знания будут способствовать наиболее эффективной работе пользователя с ПК.

Для себя могу сделать следующие выводы:

1. Сортировка является одной из фундаментальных алгоритмических задач программирования.
2. Практически каждый алгоритм сортировки можно разбить на 3 части: сравнение, определяющее упорядоченность пары элементов; перестановку, меняющую местами пару элементов; собственно сортирующий алгоритм, который осуществляет сравнение и перестановкуэлементов до тех пор, пока все элементы множества не будут упорядочены.
3. Для оценки трудоемкости алгоритмов сортировки используются параметры: время сортировки, дополнительная память, устойчивость и естественность поведения
4. По сфере применения алгоритмы сортировок классифицируются на алгоритмы внутренних и внешних сортировок.
5. Бинарная пирамидальная сортировка является алгоритмом внутренней сортировки, основанном на построении пирамиды и просеивании элементов из ее вершины методом спуска вниз в соответствии с ключом сортировки
6. Пирамидальная сортировка не использует дополнительной памяти. Метод не является устойчивым. Поведение неестественно. Данная сортировка на почти отсортированных массивах работает также долго, выигрыш ее получается только на больших n.
7. Сортировка Шелла является алгоритмом внутренней сортировки, основанном на сравнении и перемещении пар значений, расположенных сначала достаточно далеко друг от друга в упорядочиваемом наборе данных, с дальнейшим сокращением расстояний между ними.
8. Сортировка Шелла является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места.
9. Сортировка Хоара является одной из разновидностей быстрых сортировок, основанная на упорядочивании подмножеств массива относительно опорных элементов.
10. Эффективность быстрой сортировки в значительной степени определяется правильностью выбора опорных элементов при формировании блоков.
11. Сортировка слиянием является одним из самых простых алгоритмов сортировки среди быстрых алгоритмов, который может быть эффективно использован для сортировки связанных списков.
12. Недостаток алгоритма сортировки слиянием заключается в том, что он требует дополнительную память размером порядка n, не гарантирует сохранение порядка элементов с одинаковыми значениями. Его временная сложность всегда пропорциональна O(n log n).
13. Быстрая сортировка является наиболее эффективным алгоритмом из всех известных методов сортировки, но все усовершенствованные методы имеют один общий недостаток – невысокую скорость работы при малых значениях n.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Информатика: Учебник / Под ред. Н. В. Макаровой. – М.: Финансы и статистика, 2005. – 436 с.
2. Информационные системы в экономике: Учеб. Пособие / Под ред. проф. А. Н. Романова, про. Б. Е. Одинцова – М.: Вузовский учебник, 2008. – 411 с.
3. Леонтьев В. П. Новейшая энциклопедия персонального компьютера 2005. – М.: ОЛМА-ПРЕСС Образование, 2005. – 800 с.
4. Информатика: Методические указания по выполнению курсовой работы для самостоятельной работы студентов II курса (первое высшее образование). – М.: Вузовский учебник, 2006. – 60 с.
5. Информатика: Лабораторный практикум для студентов II курса всех специальностей. – М.: Вузовский учебник, 2006. – 94 с.

Интернет-ресурсы:

• 1. https://tproger.ru/translations/sorting-for-beginners/
  2. https://habr.com/post/335920/
  3. https://studfiles.net/preview/4652654/
  4. https://ru.wikipedia.org/wiki/Алгоритм_сортировки
  5. https://botanim.ru/