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

ВВЕДЕНИЕ

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

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

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

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

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

В практической части курсовой работы с помощью пакетов прикладных программ (ППП) будут решены и описаны следующие задачи:

1. создание таблиц и заполнение таблиц данными;
2. применение математических формул для выполнения запросов в ППП;
3. построение графиков.

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

• Процессор: INTEL PENTIUM 4 1.7 GHz;
• Оперативная память: SD RAM 256mb;
• Жесткий диск: HDD 40Gb;
• Видеокарта: ATI RADEON 9600pro;
• Клавиатура: Logitech G15;
• Logitech G9.

Программные средства: операционная система Windows ХР Professional sp2, пакет прикладных программ – MS Office 2003(из него использованы для выполнения курсовой работы: текстовый процессор MS Word 2003,  табличный процессор MS Excel2003).

 

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

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

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

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

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

 

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

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

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

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

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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся не отсортированных N-1 элементов (т.е. для тех, которые лежат "ниже" первого). Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

2. Сортировка перемешиванием.

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

3. Сортировка методом вставок.

Сортировка вставками элементов a₁, a₂, …, a_n относится к наиболее очевидным методам. При таком подходе вводится фиктивный элемент a₀=-¥, а затем каждый элемент, начиная со второго, сравнивается с элементами уже упорядоченной части последовательности и вставляется в нужное место. При вставке элемент a_j временно размещается в переменной w, и просматриваются элементы a_j-1, a_j-2, …,a₁ (уже к этому времени упорядоченные). Они сравниваются с w и сдвигаются, если обнаруживается, что они больше чем w.

Сложность алгоритма определяется числом проверок условия w

 

4. Сортировка подсчетом.

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

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

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

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

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

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

6. Сортировка методом выбора.

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

7. Сортировка методом Шелла.

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

8. Метод Хoopа.

Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).

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

9. Цифровая сортировка.

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

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

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

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

10. Поразрядная сортировка.

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

 

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1. Практическое задание №7

Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен на рис. 2.1. Данные о заказанных работах указаны на рис 2.2.

1. Построить таблицы по приведенным в приложениях данным.
2. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (рис. 2.2).
3. Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
4. Сформировать и заполнить счет на оплату (рис. 2.3).
5. Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде.

 

Прайс-лист

Наименование работы	Единица измерения	Цена за ед. изм., руб.
Замена батарей	шт.	250
Замена ванны	шт.	210
Замена труб	м	240
Наклейка обоев	кв.м	50
Настилка паркета	кв.м	75
Побелка потолка	кв.м	15

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

 

Расчет стоимости выполняемых работ
Наименование                                                                                                                                                                                          работы	Единица измерения	Объем выполняемых работ	Цена за ед. изм., руб.	Стоимость работ, руб.
Замена батарей	шт.	4
Наклейка обоев	кв.м	20
Замена труб	м	4
Настилка паркета	кв.м	15

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

 

	ООО "Стройдизайн"
	СЧЕТ №1
	Дата		___.___.20___
	ФИО клиента		_____________________________________
	№ п/п	Наименование работы	Единица измерения	Объем выполняемых работ	Цена за ед. изм., руб.	Стоимость работ, руб.
	1	Замена батарей	шт.
	2	Наклейка обоев	кв.м
	3	Замена труб	м
	4	Настилка паркета	кв.м
					ИТОГО:
					НДС:
				СУММА С НДС:
	Гл. бухгалтер		____________________

 

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

 

2.2. Описание порядка выполнения практического задания

Для решения данной экономической задачи была выбрана среда табличного процессора MS Excel. Microsoft Office Excel является средством для создания электронных таблиц, которые обладают возможностями для проведения простых расчетов, как с использованием арифметических действий, так и с помощью встроенных функций; для построения разных типов диаграмм; для оформления полученных таблиц и т.д. Так же, MS Excel – программа, не требующая знаний программирования, достаточно проста в использовании для поиска результата данной задачи.

Порядок выполнения практического задания следующий:

1. Запустить табличный процессор MS Excel.
2. Создать книгу с именем «Стройдизайн».
3. Лист 1 переименовать в лист с названием Работа.
4. На рабочем листе Работа MS Excel создать таблицу базового прайс-листа на выполняемые работы.
5. Заполнить таблицу базового прайс-листа исходными данными (рис. 2.4).

 

Рис. 2.4. Расположение таблицы «Прайс-лист» на рабочем листе Работа MS Excel

 

1. Разработать структуру шаблона таблицы «Расчет стоимости выполняемых работ» (рис. 2.5).

 

Колонка электронной таблицы	Наименование (реквизит)	Тип данных	Формат данных - длина
A	Наименование работы	текстовый	15
B	Единица измерения	текстовый	15
C	Объем выполняемых работ	числовой	2
D	Цена за ед. изм., руб.	числовой	4
E	Стоимость работ, руб.	числовой	5

Рис. 2.5. Структура шаблона таблицы «Расчет стоимости выполняемых работ»

 

1. Лист 2 переименовать в лист с названием Данные о заказе.
2. На рабочем листе  Данные о заказеMS Excel создать таблицу, в которой будут содержаться данные о поступившем заказе.
3. Заполнить таблицу «Расчет стоимости выполняемых работ» исходными данными (рис. 2.6).

 

Рис. 2.6. Расположение таблицы «Расчет стоимости выполняемых работ» на рабочем листе  Данные о заказе MS Excel

 

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

Занести в ячейку D4 формулу:

=Работа!С3

В ячейку D5 занести:

=Работа!С6

Аналогично сделать и в ячейках D6, D7.

1. Заполнить графу Стоимость работ, руб. таблицы «Расчет стоимости выполняемых работ», находящейся на листе Данные о заказе следующим образом:

Занести в ячейку E4 формулу:

=C4*D4

Размножить введенную в ячейку E4 формулу для остальных ячеек данной графы (с E5 по E7) (рис. 2.7 и рис 2.8).

 

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

 

1. Лист 3 переименовать в лист с названием Форма счета.
2. На рабочем листе Форма счета MS Excel создать форму счета на оплату выполненных работ.
3. Путем создания межтабличных связей заполнить созданную форму полученными данными из таблицы «Расчет стоимости выполняемых работ» (рис. 2.9 и рис 2.10).

 

	ООО "Стройдизайн"
	СЧЕТ №1
	Дата		01.02.2009
	ФИО клиента		Захарова Елена Ивановна
	№ п/п	Наименование работы	Единица измерения	Объем выполняемых работ	Цена за ед. изм., руб.	Стоимость работ, руб.
	1	Замена батарей	шт.	4	250	1000
	2	Наклейка обоев	кв.м	20	50	1000
	3	Замена труб	м	4	240	960
	4	Настилка паркета	кв.м	15	75	1125
					ИТОГО:	4085
					НДС:	531,05
				СУММА С НДС:		4616,05
	Гл. бухгалтер		Петров Г.М.

 

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

 

	ООО "Стройдизайн"
	СЧЕТ №1
	Дата		01.02.2009
	ФИО клиента		Захарова Елена Ивановна
	№ п/п	Наименование работы	Единица измерения	Объем выполняемых работ	Цена за ед. изм., руб.	Стоимость работ, руб.
	1	='Данные о заказе'!A4	='Данные о заказе'!B4	='Данные о заказе'!C4	='Данные о заказе'!D4	='Данные о заказе'!E4
	2	='Данные о заказе'!A5	='Данные о заказе'!B5	='Данные о заказе'!C5	='Данные о заказе'!D5	='Данные о заказе'!E5
	3	='Данные о заказе'!A6	='Данные о заказе'!B6	='Данные о заказе'!C6	='Данные о заказе'!D6	='Данные о заказе'!E6
	4	='Данные о заказе'!A7	='Данные о заказе'!B7	='Данные о заказе'!C7	='Данные о заказе'!D7	='Данные о заказе'!E7
					ИТОГО:	=СУММ(G10:G13)
					НДС:	=G14*13%
				СУММА С НДС:		=G14+G15
	Гл. бухгалтер		Петров  Г.М.

Рис. 2.10. Расположение формул в таблице «Форма счета на оплату выполненных работ»

 

1. Лист 4 переименовать в лист с названием График.
2. На рабочем листе График MS Excel создать сводную таблицу.

17. Путем создания межтабличных связей автоматически заполнить графы Наименование работы и Стоимость работ, руб. полученными данными из таблицы «Расчет стоимости выполняемых работ» (рис. 2.11).

1. Результаты вычислений представить графически (рис. 2.12).

 

ООО "Стройдизайн"
Итоговая стоимость каждого вида работ по полученному заказу на 01. 02. 2009г.
Наименование работы	Стоимость работ, руб.
Замена батарей	1000
Наклейка обоев	1000
Замена труб	960
Настилка паркета	1125
Итого	4085
01. 02. 2009г.                 Бухгалтер             Петров Г. М.

 

Рис. 2.11. Сводная таблица и графическое представление результатов вычислений

 

	ООО "Стройдизайн"
	Итоговая стоимость каждого вида работ по полученному заказу на 01. 02. 2009г.
	='Форма счета'!C9	='Форма счета'!G9
	='Форма счета'!C10	='Форма счета'!G10
	='Форма счета'!C11	='Форма счета'!G11
	='Форма счета'!C12	='Форма счета'!G12
	='Форма счета'!C13	='Форма счета'!G13
	Итого	=СУММ(C7:C10)
	01. 02. 2009г.                 Бухгалтер           Петров Г.М.

Рис. 2.12. Расположение формул в сводной таблице результатов вычислений

 

ЗАКЛЮЧЕНИЕ

Современную жизнь представить без современной техники просто невозможно.

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

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

В теоретической части мы изучили алгоритмы сортировки, их виды, предназначение и характеристики. 

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

 

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

Внимание!

Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы

Бесплатная оценка

Скачать бесплатно