Автор работы: Пользователь скрыл имя, 29 Января 2011 в 01:09, курсовая работа
При выполнении теоретической части курсовой работы я отвечу на следующие вопросы, которые раскрывают подробно свойства каждого алгоритма, а именно:
- какое сравнение, определяет упорядоченность пары элементов?
- какая перестановка меняет местами пару элементов?
- каков собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены?
Оглавление:
21
В настоящее время новые информационные технологии занимают важнейшее место не только в специализированных, но и в повседневных сферах жизни. Компьютеры применяются в бизнесе, менеджменте, торговле, учебе и многих других сферах деятельности человека.
Компьютерные технологии очень удобны для выполнения разнообразных операций, но в разных сферах применения эти операции разные. Потому, каждая отдельная отрасль, которая использует специфические технические средства, нуждается в своих собственных программах, которые обеспечивают работу компьютеров.
Разработкой программного обеспечения занимается такая отрасль науки, как программирование. Она приобретает все большее и большее значение в последнее время, ведь с каждым днем компьютер становится все более необходимым, все более повседневным явлением нашей жизни. Ведь вычислительная техника прошлых лет уже почти полностью исчерпала себя и не удовлетворяет тем потребностям, которые появляются перед человечеством.
Таким образом, новые информационные технологии очень актуальны в наше время и нуждаются в большем внимании для последующей разработки и совершенствования. Рядом с этим, большое значение имеет также и программирование, которое является одним из фундаментальных разделов информатики и потому не может оставаться в стороне.
Программирование содержит целый ряд важных внутренних задач. Одной из наиболее важных задач для программирования является задача сортировки.
В этой курсовой работе я буду изучать, в теоретической части, алгоритмы сортировки применяемые в информатике, а в практической части, закреплю имеющиеся знания решением экономической задачи при помощи использования Microsoft Excel – программы для работы с электронными таблицами.
Так же в данной курсовой будет подробно исследована проблема упорядочивания данных с практической точки зрения: достоинства и недостатки восьми различных методов сортировки.
При выполнении теоретической части курсовой работы я отвечу на следующие вопросы, которые раскрывают подробно свойства каждого алгоритма, а именно:
- какое сравнение, определяет
упорядоченность пары
- какая перестановка меняет местами пару элементов?
- каков собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены?
Подобными свойствами обладают и восемь алгоритмов сортировки, которые
рассмотрены ниже. Они отобраны из множества алгоритмов, потому что, во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь.
При выполнении курсовой работы я буду использовать следующие прикладные программы: это Microsoft Word и Microsoft Excel.
Microsoft Word - это представляет собой текстовый редактор, предназначенный для создания, редактирования, вывода на экран и печать, а также сохранения в виде файлов различного рода документов и данных. Microsoft Word представляет собой пакет прикладных программ, который наряду с перечисленными выше операциями позволит производить форматирование текста (по всему документу и его части), формировать различные стили оформления документов, пользоваться большим количеством шрифтов, выделять (курсивом, подчеркиванием, жирным шрифтом и другими средствами) участки текста, набирать текст в виде колонок, включать в тексты иллюстрации, формировать различного рода указатели и ссылки, вводить верхние и нижние колонтитулы страниц, производить автоматизированный поиск элементов текста и исправление ошибок, копировать и переносить в другой документ любые участки текста, а также многое другое.
Microsoft
Excel – это табличный редактор,
наименование прикладной
Microsoft Word я буду использовать
при оформлении курсовой
При выполнении курсовой работы я использовала персональный компьютер со следующими характеристиками:
Алгоритм – это точно определенная последовательность действий, которую необходимо выполнить над исходными данными для достижения решения задачи.
Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, который сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем это слово стало использоваться не только в математике, а фактически любую последовательность действий, приводящих к конечному результату, стали называть алгоритмом, а каждое действие шагом алгоритма. Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.
Сортировка - это процесс упорядочения некоторого множества элементов в некотором определенном порядке. Определенный порядок (например, упорядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик, по классам, типам и т.п.) в последовательности объектов необходимо для удобства работы с этим объектом.
Целью алгоритмов сортировки является упорядочение последовательности элементов данных.
Под поиском подразумевается процесс нахождения в заданном множестве объекта, обладающего свойствами или качествами задаваемого шаблона. Поиск элемента в последовательности отсортированных данных занимает время, пропорциональное логарифму количеству элементов в последовательности, а поиск элемента в последовательности не отсортированных данных занимает время, пропорциональное количеству элементов в последовательности, то есть намного больше. Существует множество различных методов сортировки данных. В курсовой работе я рассмотрю следующие методы сортировки:
Важнейшей характеристикой любого алгоритма сортировки является скорость ее работы, которая определяется функциональной зависимостью среднего времени сортировки последовательностей элементов данных, заданной длинны, от этой длинны. Время сортировки будет пропорционально количеству сравнений и перестановки элементов данных в процессе их сортировки.
Вообще, алгоритмы сортировки - одна из самых хорошо исследованных областей информатики. Тем не менее, не исключены открытия и в этой области, потому что наверняка существуют еще какие-то пока неизвестные методы сортировки, основанные на новых принципах и идеях.
Алгоритмы сортировки имеют большое практическое применение. Их можно встретить почти везде, где речь идет об обработке и хранении больших объемов информации. Некоторые задачи обработки данных решаются проще, если данные упорядочены. Примеры таких задач я рассмотрю в этой курсовой работе.
Пузырьковая сортировка - один из наиболее широко известных алгоритмов сортировки. Сущность алгоритма заключается в следующем. Мы проходим по массиву и берем из него числа парами, вот так – первое число и второе, затем второе и третье, затем третье и четвертое и т.д. и если в очередной паре последнее число меньше первого, то меняем их местами.
Если за полный проход массива не было обнаружено ни одной неправильной пары, то массив, очевидно, упорядочен и работу можно прекратить. Если была обнаружена хотя бы одна неправильная пара, то массив может быть упорядочен, а может быть и нет, но во всяком случае еще один проход не помешает. Таким образом, алгоритм пузырька представляет собой два вложенных цикла, внешний запускает очередной проход, если была обнаружена неправильная пара, а внутренний просматривает пары чисел и выполняет перестановку если это необходимо.
Почему алгоритм называется «ПУЗЫРЕК»
Назовем конец массива дном, а начало поверхностью, числа с меньшим значением назовем легкими, а с большими – тяжелыми. Просчитайте несколько шагов ПУЗЫРЬКА и вы увидите, что легкие числа, как пузырьки всплывают к поверхности, оттого и алгоритм и назван ПУЗЫРЬКОМ.
Запишем алгоритм на языке Паскаль, заметив, что в том случае, когда за очередной проход не было сделано ни одного обмена, массив уже отсортирован и следующие проходы можно пропустить. Для отслеживания такой ситуации введем логическую переменную Flag - признак совершения обмена на очередном проходе:
for i := N-1 downto 1 do
begin
Flag := false;
for j := 1 to i do
if a[j]>a[j+1] then
begin
Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;
Flag := true;
end;
if not Flag then Break;
end;
Этот алгоритм имеет среднюю и максимальную временные сложности T(n2) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти за исключением памяти для фиксированного числа переменных (i, j, Tmp, Flag). Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к T(n).
Пример сортировки методом пузырька в таблице:
| Начальное состояние массива | 8 23 5 65 44 33 1 6 |
| Шаг 1 | 8 23 5 65 44 33 1
6
8 23 5 65 44 1 33 6 8 23 5 65 1 44 33 6 8 23 5 1 65 44 33 6 8 23 1 5 65 44 33 6 8 1 23 5 65 44 33 6 1 8 23 5 65 44 33 6 |
| Шаг 2 | 1 8 23 5 65 44 6 33
1 8 23 5 65 6 44 33 1 8 23 5 6 65 44 33 1 8 23 5 6 65 44 33 1 8 5 23 6 65 44 33 1 5 8 23 6 65 44 33 |
| Шаг 3 | 1 5 8 23 6 65 33 44
1 5 8 23 6 33 65 44 1 5 8 23 6 33 65 44 1 5 8 6 23 33 65 44 1 5 6 8 23 33 65 44 |
| Шаг 4 | 1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 |
| Шаг 5 | 1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 |
| Шаг 6 | 1 5 6 8 23 33 44 65
1 5 6 8 23 33 44 65 |
| Шаг 7 | 1 5 6 8 23 33 44 65 |
Один
из самых простых методов
Этот метод работает очень хорошо для небольших файлов. Его «внутренний цикл» состоит из сравнения a[i]<a[min] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N), что вряд ли можно еще упростить.
Кроме
того, хотя сортировка выбором является
методом «грубой силы», он имеет
очень важное применение: поскольку
каждый элемент передвигается не
более чем раз, то он очень хорош
для больших записей с
Это
изящный и простой для
Таким образом, по очереди вставляем все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после - большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки мы получим упорядоченный исходный массив. Вот как такой алгоритм можно реализовать на языке программирования Pascal:
Program InsertionSort;
Var A,B : array[1..1000] of integer;
N,i,j : integer;
Begin
{Определение размера массива A (N) и его заполнение}
…
{сортировка данных}
for i:=1 to N do
begin
j:=i;
while (j>1) and (B[j-1]>A[i]) do
begin
B[j]:=B[j-1];
j:=j-1;
end;
B[j]:=A[i];
end;
{Вывод массива B}
…
End.
Виды сортировок вставкой:
Такой метод предложен в 1959 г. Дональдом Л. Шеллом.
Метод Шелла является усовершенствованием простого включения, которое основано на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле мы избавлялись от сдвига A[i], сохраняя его в промежуточной переменной, но сути метода это не изменяло, так как передвигалось место, оставленное под сохраненное значение). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом.
Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и так далее, где h - положительная константа. Таким образом формируется массив, в котором «h- серии» элементов, отстоящих друг от друга на h, сортируются отдельно.
Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.
В настоящее время неизвестна последовательность hi, hi-1, hi-2, ..., h1, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что hi+1=3hi+1, а h1=1. Начинается процесс с hm-2, где m - наименьшее целое такое, что hmі n. Другими словами hm-2 первый такой член последовательности, что hm-2і [n/9].
Теперь запишем алгоритм:
Step := 1;
while Step < N div 9 do Step := Step*3 + 1;
Repeat
for k := 1 to Step do
begin
i := Step + k;
while i <= N do
begin
x := A^[i];
j := i - Step;
while (j >= 1) and (A^[j]>x) do
begin
A^[j + Step] := A^[j];
Dec(j);
end;
A^[j + Step] := x;
Inc(i, Step);
end;
end;
Step := Step div 3;
until Step=0;
Как показывают теоретические выкладки, которые мы приводить не будем, сортировке методом Шелла требуется в среднем 1,66n1,25 перемещений.
Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым методом сортировки из тех, что оперируют сравнениями.
Суть этого метода заключается в том, чтобы найти такой элемент сортируемой последовательности, который бы делил последовательность на две части так, что слева от него находились бы элементы не меньшие его, а справа – не большие. Поиск такого элемента можно организовать многими способами.
Установим два индекса на 1-ый (индекс ί) и на последний (индекс ј) элемент последовательности. Затем пока элемент с индексом ј меньше или равен элементу с индексом ί, будем уменьшать ј на 1. Если же элемент с индексом ј больше или равен элементу с индексом ί, то меняем местами элементы с индексами ί и ј. Затем, пока элемент с индексом ј меньше или равен элементу с индексом ί, будем увеличивать ί на 1. Если же элемент с индексом ј больше или равен элементу с индексом ί, то меняем элемент с индексом ί на ј. Этот процесс продолжается до тех пор, пока ј не станет равным ί. Элемент с индексом ί = ј и есть искомый.
Бинарным (двоичным) деревом называют упорядоченную структуру данных, в которой каждому элементу данных поставлены в соответствие до трех других элементов: левый и правый преемник и предшественник. Левый преемник должен быть больше, а правый – меньше или равен предшественнику. Единственный элемент, не имеющий предшественника, называется корнем дерева.
Если по исходной последовательности данных построить бинарное дерево, а затем вывести его элементы по определенным правилам обхода дерева, то полученная в результате последовательность окажется отсортированной.
Правила обхода дерева:
Сортировка бинарным деревом – это нерекрусивная быстрая сортировка. При рекурсивной быстрой сортировке дерево автоматически строится и обходится в сетке.
Сортировка массивом – это самый быстрый метод сортировки, однако существует множество существенных недостатков.
Суть метода заключается в заполнении вспомогательного массива, содержащего элементы несколько больше, чем исходная последовательность. Заполнение этого вспомогательного массива происходит таким образом: вычисляются значения некоторой монотонной функции, называемой хэш-функция, на элементах сортируемой последовательности и эти значения считаются индексами этих элементов в заполняемом массиве. Если же окажется, что подлежащий заполнению элемент вспомогательного массива уже занят, то происходит сдвиг соответствующих элементов этого массива так, чтобы образовалось “окно” для вносимого элемента и сохранялась упорядоченность между элементами. Функция должна выбираться так, чтобы ее значения лежали внутри диапазона индексов вспомогательного массива. Например, если известно, что сортируемая последовательность состоит из натуральных чисел от 1 до N, то в качестве искомой функции можно взять , . В общем случае, в качестве такой функции рекомендуется взять:
где A – это исходная последовательность (массив), Max(A) и Min(A) максимальный и минимальный элемент A,B – это вспомогательный массив, а Size(B) – это его размер. Эта монотонная (почти линейная) функция гарантирует, что ее значение на элементах сортируемого массива будут лежать в диапазоне от 1 до Size(B). Она определена только при Max(A) ≠ Min(A). Если же Max(A) = Min(B), то это означает, что массив состоит из одинаковых элементов, то есть он отсортирован.
Этот метод, совершенно отличен от всех схем сортировки, которые рассматривались прежде; в нем используется двоичное представление ключей, и потому он предназначен исключительно для двоичных машин. Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли 0 или 1 отдельные биты ключа. В других отношениях он обладает характеристиками обменной сортировки и на самом деле очень напоминает быструю сортировку. Так как он зависит от разрядов ключа, представленного в двоичной системе счисления, мы называем его "обменной поразрядной сортировкой". В общих чертах этот алгоритм можно описать следующим образом:
Алгоритм обмена по разрядной сортировки:
Записи R1, . . . , RN переразмещаются на том же месте; после завершения сортировки их ключи будут упорядочены:K1 ≤ . . . ≤ KN. Предполагается, что все ключи—m-разрядные двоичные числа (a1 a2 . . . am)2; i-й по старшинству бит ai называется "бит i" ключа. Требуется вспомогательный стек, вмещающий до m − 1 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями.
Итак, я изучила восемь методов сортировки. Можно сделать вывод, что не существует одного единственного самого оптимального алгоритма сортировки. Найти оптимальный алгоритм, не привязываясь при его выборе к условию задачи невозможно.
Какой алгоритм, из множества известных сейчас самый быстрый?
Ответа
на этот вопрос не существует. Нет самого
оптимального алгоритма в абстрактном
смысле. Выбор его очень сильно
зависит от условия задачи, которую
необходимо решить.
Мне необходимо решить следующую экономическую задачу.
Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен в таблице 1. Данные о заказанных работах указаны в таблице 2. необходимо:
Прайс-лист на выполняемые работы
Таблица 1
| Наименование работы | Единица измерения | Цена за ед. изм., руб. |
| Замена батарей | шт. | 250 |
| Замены ванны | шт. | 210 |
| Замена труб | м | 240 |
| Наклейка обоев | м2 | 50 |
| Настилка паркета | м2 | 75 |
| Побелка потолка | м2 | 15 |
Расчет стоимости выполняемых работ
Таблица 2
| Наименование работы | Единица измерения | Объем выполняемых работ | Цена за ед. изм., руб. | Стоимость работ, руб. |
| Замена батарей | шт. | 4 | ||
| Наклейка обоев | м2 | 20 | ||
| Замена труб | м | 4 | ||
| Настилка паркета | м2 | 15 |
Форта счета на оплату выполненных работ
Таблица 3
СЧЕТ № 1 ФИО клиента _________________
Гл. бухгалтер ____________________ | ||||||||||||||||||||||||||||||||||||||||||||||||
Описание алгоритма решения задачи:
Рис. 1. Расположение
таблицы «Прайс-лист на выполняемые
работы» на рабочем листе Товары
MS Excel
6. Лист 2 переименовываю в лист с названием Расчет стоимости.
7. На
рабочем листе Расчет
8. Заполню
таблицу Расчет стоимости
списком выполняемых работ
исходными данными (рис. 2).
Рис. 2. Расположение
таблицы «Расчет стоимости выполняемых
работ» на рабочем листе Товары
MS Excel
Занесу в ячейку D3 формулу:
=ЕСЛИ(A3=Товары!A3;Товары!C3;
Размножу введенную в ячейку D3 формулу для остальных ячеек (с D3 по D6) данной графы.
Таким образом я выполнила цикл, управляющим параметром которого является номер строки.
Занесу в ячейку Е3 формулу, для расчета стоимости работ:
=C3*D3
Размножу введенную в ячейку Е3 формулу для остальных ячеек (с Е3 по Е6) данной графы.
11.Лист 3 переименовываю в лист с названием Счет 1.
12. На рабочем листе Счет 1 MS Excel создаю таблицу, в которой будет содержаться счет.
13. Заполню таблицу
Счет 1 списком выполняемых работ
исходными данными (рис. 3).
14. Путем межтабличных связей заполню Счет 1 данными полученными в таблице Расчет стоимости выполняемых работ, расположенной на листе Расчет стоимости.
Заполню графу Объем выполняемых работ, находящейся на листе Счет 1 следующим образом:
Занесу в ячейку Е7 следующую формулу:
=ЕСЛИ(C9='Расчет стоимости'!A5;'Расчет стоимости'!C5;ЕСЛИ('Счет 1'!C9='Расчет стоимости'!A6;'Расчет стоимости'!C6;ЕСЛИ('Счет 1'!C9='Расчет стоимости'!A7;'Расчет стоимости'!C7;ЕСЛИ('Счет 1'!C9='Расчет стоимости'!A8;'Расчет стоимости'!C8))))
Размножу введенную в ячейку Е7 формулу для остальных ячеек (с Е7 по Е10 и с F7 по G10) данной графы.
Таким образом я выполнила цикл, управляющим параметром которого является номер строки.
15. Заполню графу ИТОГО, расположенную на листе Счет 1.
Занесу в ячейку G11 следующую формулу:
=СУММ(G7:G10)
16. Заполню графу НДС, расположенную на листе Счет 1.
Занесу в ячейку G12 следующую формулу:
=G11*18/118
17. Заполню
графу СУММА С НДС,
Занесу в ячейку G13 следующую формулу:
=СУММ(G11:G12)
18. Лист 4 переименовываю в лист с названием График.
19. На рабочем листе График MS Excel создаю свободную таблицу стоимости каждого вида работ по полученному заказу. Путем создания межтабличных связей автоматически заполняю графы Наименование работы и Стоимость, руб., полученными данными из таблицы Расчет стоимости выполняемых работ.
20. Результаты вычислений предоставляю графически (рис. 4)
| ООО
«Сиройдизайн»
Стоимости каждого вида работ по полученным заказам.
Наименование работ Замена батарей Наклейка обоев Замена труб Настилка паркета ИТОГО: Гл. бухгалтер _______ |
Рис. 4. Сводная таблица и графическое представление результатов вычислений