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

Оглавление

Введение…………………………………………………………….2 стр.

1. Теоретическая часть…………………………………………4 стр.

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

2. Алгоритмы сортировки………………………………………7 стр.

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

1. Общая характеристика задачи………………………………12 стр.
2. Описание алгоритма решения задачи………………………14 стр.

Заключение…………………………………………………………..19 стр.

Список  используемой литературы………………………………….20 стр. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

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

Данная  курсовая работа состоит из двух частей: теоретической и практической.

В теоретической  части будут изложены следующие  вопросы:

• Понятие алгоритма.
• Алгоритмы сортировки.

В практической части курсовой работы решается экономическая задача предприятия ООО «Стройдизайн», с использованием Microsoft Office Excel (программа для работы с электронными таблицами). В которой нужно будет:

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

Данная  курсовая работа выполнена и оформлена  с использованием ПК с характеристиками:

1. Процессор: AMD Athlon 64 X2 4200+ Socket AM2 Energy Efficient BOX 2.21 ГГц.
2. Оперативная память: 2,00 ГБ.
3. Жесткий диск: 250 ГБ.
4. Видеокарта: Gigabyte GeForce 8600 GT.
5. Клавиатура: Logitech Internet 350.
6. Мышь: Microsoft Retail Basic Optical Mouse.
7. Монитор: LG Flatron 1953 TR-BF.

Программные средства:

1. Операционная система Microsoft Windows XP Professional Service Pack 3 версия 2002.
2. Пакет прикладных программ: Microsoft Office 2007.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Теоретическая часть

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

Алгоритм –это формальное описание способа решения задачи путем разбиения ее на последовательность элементарных операций. Под словом «формальное» надо понимать, что описание должно быть абсолютно полным и учитывать все возможные ситуации, которые могут возникать по ходу решения [2, С. 660.]. Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм - есть результат европейского произношения слов аль-Хорезми. [1, С. 292]. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

Любой алгоритм обладает следующими свойствами: детерминированностью, массовостью, результативностью, формальность, дискретностью[3, С. 329].

1. Детерминированность (определенность, однозначность) означает, что набор указаний алгоритма должен быть однозначно и точно понят любым исполнителем. Это свойство определяет однозначность результата работы алгоритма при одних и тех же исходных данных.
2. Массовость алгоритма предполагает возможность варьирования исходных данных в определенных пределах. Это свойство определяет пригодность использования алгоритма для решения множества задач данного класса. Свойство массовости алгоритма является определяющим фактором, обеспечивающим экономическую эффективность решение задач на ЭВМ (электронная вычислительная машина), так как для задач, решение которых осуществляется один раз, целесообразность использования ЭВМ, как правило, диктуется внеэкономическими категориями.
3. Результативность алгоритма означает, что для любых допустимых исходных данных он должен через конечное число шагов (или итераций) завершить работу.
4. Дискретность алгоритма – это возможность разбиения алгоритмического процесса на отдельные элементарные действия, возможность реализации которых человеком или ЭВМ не вызывает сомнения, а результат их выполнения вполне определен или понятен.
5. Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции.

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

Существует  несколько способов описание алгоритмов:

1. Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники имеет инструкцию по эксплуатации, т.е. словесное описание алгоритма, в соответствии которому данный прибор должен использоваться. Этот способ допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
2. Псевдокод – описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основные этапы решения задач, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика.
3. Блок-схема – описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций.

 Таким образом, алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Сортировка  – это процесс изменения последовательности элементов данных с целью их расположения по возрастанию или совпадению значений ключевых полей.

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

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

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

1. Сортировка пузырьком.

Условимся считать массив отсортированным, если элементы расположены в

порядке неубывания (т.е. каждый элемент не меньше предыдущего). Это один из простейших методов сортировки. Название метода отражает его сущность: на каждом шаге самый «легкий» элемент поднимается до своего места («всплывает»). Для этого мы просматриваем все элементы снизу вверх, берем пару соседних элементов и, в случае, если они стоят неправильно, меняем их местами. Вместо поднятия самого «легкого» элемента можно

«топить»  самый «тяжелый». Т.к. за каждый шаг  на свое место встает ровно 1

элемент (самый «легкий» из оставшихся), то нам  потребуется выполнить N шагов.

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

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

4. Сортировка Шелла.

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

5. Сортировка вставками (сортировка простым методом включения).

Элементы  исходного массива условно рассматриваются в двух последовательностях: готовая упорядоченная последовательность а(1), а(2),…а(i-1) и исходная а(i), а(i+1),…а(n) последовательность, значения которых в порядке следования необходимо вставить в соответствующие места готовой последовательности путем сдвига вправо (вниз) тех или иных элементов. Для такой вставки в цикле, начиная с i=2 (готовая последовательность содержит 1 элемент, j=2) с шагом 1, каждый элемент а(i) входной последовательности передается и вставляется в нужное место готовой последовательности. Если сортируются элементы в порядке возрастания, то при вставке x=a(i) место вставки определяется, как только найдем элемент готовой последовательности a_j≤x.

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

     Идея алгоритма заключается в  простом подсчете количества  вхождений каждого числа в  массив. Это делается так: выполним  один проход массива и для каждого числа из отрезка [0,max] подсчитаем сколько раз оно встретится. Вычисленные количества сохраним в специальном массиве счетчиков. Затем запишем в массив - результат (а это может быть и исходный массив) каждое число столько раз, чему равно значение соответствующего ему счетчика, то есть, сколько раз оно встретилось.

8. Сортировка методом наименьшего элемента.

Сортировка  данным методом основана на следующем  алгоритме:

• Определяется наименьший элемент и его координаты в заданной последовательности данных;
• Этот наименьший элемент меняется местами с первым элементом;
• Определяется наименьший элемент и его координаты среди оставшихся элементов. Он меняется со вторым элементом;
• Данная процедура повторяется со всеми элементами, пока не останется только один наибольший элемент.

9. Быстрая сортировка (метод Хоора).

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

10. Метод поиска.

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