Главная » Бесплатные рефераты » Бесплатные рефераты по информатике »
Алгоритмы сортировки
![Алгоритмы сортировки [28.02.11]](/files/works_screen/89/98.png)
Тема: Алгоритмы сортировки
Раздел: Бесплатные рефераты по информатике
Тип: Курсовая работа | Размер: 340.91K | Скачано: 482 | Добавлен 28.02.11 в 12:18 | Рейтинг: 0 | Еще Курсовые работы
Вуз: ВЗФЭИ
Год и город: Барнаул 2010
Оглавление
стр.
Введение………………………………………………………………3
Теоретическая часть………………….……………………………..4
Практическая часть……………….……………………………….12
Заключение………………………………………………………….18
Список использованной литературы……………………………19
Введение
Данная курсовая работа состоит из двух частей: теоретической и практической. В теоретической части работы будут рассмотрены основные параметры оценки алгоритмов сортировки, наиболее известные методы сортировки, а в практической части на основе экономической задачи будет представлено, как удобно с помощью Microsoft Excel выполнить расчеты, проанализировать полученные числовые данные, а также представить результаты в графическом виде.
Таким образом, целью курсовой работы является описание существующих алгоритмов сортировки и решение задачи экономического типа на основе программы MS Excel. Исходя из цели, следует сформулировать задачи, которые предстоит решить для наиболее полного и качественного представления информации, необходимой в достижении поставленной цели наиболее кратким путем.
Таким образом, задачами курсовой работы являются:
- найти определение понятию алгоритма сортировки;
- определить основные параметры оценки алгоритмов сортировки;
- рассмотреть различные методы сортировки данных;
- разработать алгоритм решения экономической задачи, представленной в практической части работы;
- использовать в работе, в целях более наглядного восприятия, шаблоны
выходных документов, показав их расположение на рабочем листе
табличного процессора;
- представить конечные выходные документы, созданные на основе разработанного алгоритма.
Теоретическая часть
Алгоритм – это точно определенная последовательность действий, которую необходимо выполнить над исходными данными для достижения решения задачи.
Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.
Формы представления алгоритма:
1. Словесная форма;
2. Словесно-аналитическая форма;
3. В виде блок-схемы (графическое изображение алгоритма);
4. В виде программы на алгоритмическом языке программирования.
Виды алгоритмических структур:
1. Линейный алгоритм, в котором все команды выполняются последовательно одна за другой.
2. Разветвляющийся алгоритм, в котором в зависимости от условия выполнения либо одна серия команд, либо другая.
3. Циклический алгоритм, в котором многократно повторяется некоторый участок алгоритма.
Языки программирования:
1. Бейсик, отличается встроенными математическими функциями и простыми языковыми конструкциями.
2. Паскаль, предназначен для решения вычислительных и информационно-логических задач.
3. Си + + был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую.
4. Ада, ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем.
5. Java, предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети.
6. Delphi, обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети Интернет.
Сортировка - это процесс упорядочения некоторого множества элементов в некотором определенном порядке. Определенный порядок (например, упорядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик, по классам, типам и т.п.) в последовательности объектов необходимо для удобства работы с этим объектом. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Имеется два вида алгоритмов сортировки: сортировка массивов, которые могут находиться как в операционной памяти, так и на диске в виде файла прямого доступа, и сортировка последовательных файлов, находящихся на дисках или магнитных лентах. Сортировка массива данных занимает одну из самых высоких проблем современных организаций. Ведь в каждой организации есть свои Базы данных на сотрудников, которых нужно отсортировывать, допустим, по Фамилии или по заработной плате по возрастанию или убыванию.
Основное отличие между сортировкой массивов и сортировкой последовательных файлов заключается в том, что каждый элемент массива является доступным в любое время. Это значит, что в любое время любой элемент массива может сравниваться с любым другим элементом массива и любые два элемента массива могут обмениваться местами. Напротив, в последовательном файле в каждый момент времени доступен лишь один элемент. Из-за этих отличий методы сортировки существенно отличаются для этих двух видов сортировки.
Существует несколько методов сортировки, для того чтобы обоснованно сделать выбор метода, нужно рассмотреть параметры, по которым будет производиться оценка алгоритмов.
Время сортировки. Основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью.
Память. Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость. Устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.
Естественность поведения — эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Существует множество методов сортировки, каждый из которых имеет свои достоинства и недостатки. Я рассмотрю лишь некоторые из них.
Метод пузырька
Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок. Реализация данного метода не требует дополнительной памяти. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где N — количество элементов.
Сортировка перемешиванием
Представляет собой разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие к началу.
Сортировка вставками
Создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Так мы прейдем к ситуации, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку. Таким образом, по очереди вставляем все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после — большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки мы получим упорядоченный исходный массив.
Сортировка подсчётом
Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Для каждого элемента нужно найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место.
Сортировка выбором
Находиться наименьший элемент в массиве и обменивается с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов. Кроме того, хотя сортировка выбором является методом «грубой силы», он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами.
Сортировка слиянием
Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: разбить массив на две части, отсортировать каждую из них, а потом слить обе части в одну отсортированную.
Все рассматриваемые до сих пор алгоритмы сортировки обладают очень серьезным недостатком, а именно, время их выполнения пропорционально квадрату числа элементов. Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины они будут слишком медленными, чтобы их можно было использовать на практике. Если сортировка выполняется слишком долго, то причиной этого может быть используемый алгоритм. Далее рассмотрены методы сортировки, которые выполняются быстрее.
Метод Шелла
Основная идея этого алгоритма заключается в устранении массового беспорядка в массиве, сравнивая далеко стоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).
Метод Хoopа (быстрая сортировка)
Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым методом сортировки из тех, что оперируют сравнениями. Суть этого метода заключается в том, чтобы найти такой элемент сортируемой последовательности, который бы делил последовательность на две части так, что слева от него находились бы элементы не меньшие его, а справа – не большие. Поиск такого элемента можно организовать многими способами.
Поразрядная сортировка
Быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки перфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый алгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для старших букв.
Пирамидальная сортировка
Этот метод является значительно более сложным, но при этом и более быстрым (особенно на больших массивах информации) алгоритмом. Здесь используется промежуточное преобразование данных к специальному представлению, которое позволяет производить дальнейшую сортировку быстрее. В результате, общее число сравнений и обменов записей местами существенно уменьшается, что особенно важно в случае больших массивов данных.
Сортировка массивом (хеширование)
Суть метода заключается в заполнении вспомогательного массива, содержащего элементы несколько больше, чем исходная последовательность. Заполнение этого вспомогательного массива происходит таким образом: вычисляются значения некоторой монотонной функции, называемой хэш-функция, на элементах сортируемой последовательности и эти значения считаются индексами этих элементов в заполняемом массиве. Если же окажется, что подлежащий заполнению элемент вспомогательного массива уже занят, то происходит сдвиг соответствующих элементов этого массива так, чтобы образовалось “окно” для вносимого элемента и сохранялась упорядоченность между элементами. Функция должна выбираться так, чтобы ее значения лежали внутри диапазона индексов вспомогательного массива.
Цифровая сортировка
Этой сортировкой можно сортировать целые неотрицательные числа большого диапазона. Идея состоит в следующем: отсортировать числа по младшему разряду, потом устойчивой сортировкой сортируем по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы.
Практическая часть
Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен на рис. 1. Данные о заказанных работах указаны на рис.2.
- Построить таблицы по приведенным ниже данным.
- Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (рис.2).
- Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ.
- Сформировать и заполнить счет на оплату (рис.3).
- Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде.
Прайс-лист
|
Наименование работы |
Единица измерения |
Цена за ед. изм., руб. |
|
Замена батарей |
шт. |
250 |
|
Замена ванны |
шт. |
210 |
|
Замена труб |
м |
240 |
|
Наклейка обоев |
м2 |
50 |
|
Настилка паркета |
м2 |
75 |
|
Побелка потолка |
м2 |
15 |
Рис. 1. Прайс-лист на выполняемые работы
Расчет стоимости выполняемых работ
|
Наименование работы |
Единица измерения |
Объем выполняемых работ |
Цена за ед. изм., руб. |
Стоимость работ, руб. |
|
Замена батарей |
шт. |
4 |
|
|
|
Наклейка обоев |
м2 |
20 |
|
|
|
Замена труб |
м |
4 |
|
|
|
Настилка паркета |
м2 |
15 |
|
|
Рис.2. Данные о поступившем заказе
|
ООО «Стройдизайн» СЧЕТ № 1 Дата __.__.20__ ФИО клиента __________________________
Гл. бухгалтер ______________________________ |
||||||||||||||||||||||||||||||||||||||||||||||||
Рис.3. Форма счета на оплату выполненных работ
Алгоритм выполнения практической части
1. Запустить табличный процессор MS Excel;
2. Создать книгу с именем «Стройдизайн»;
3. Лист 1 переименовать в лист с названием Прайс-лист;
4. На рабочем листе Прайс-лист MS Excel создать таблицу базового прайс-листа;
5. Заполнить таблицу базового прайс-листа исходными данными (рис.4);
Рис.4. Расположение таблицы «Прайс-лист» на одноименном рабочем листе
MS Excel
6. Лист 2 переименовать в лист с названием Расчет стоимости выполняемых работ;
7. На рабочем листе Расчет стоимости выполняемых работ MS Excel создать таблицу, в которой будет содержаться объем выполняемых работ и их стоимость;
8. Заполнить таблицу Расчет стоимости выполняемых работ исходными данными (рис.5);
Рис.5. Расположение таблицы «Расчет стоимости выполняемых работ» на одноименном рабочем листе MS Excel
9. Заполнить графу Цена за ед. изм., руб. таблицы Расчет стоимости выполняемых работ;
10. Для заполнения графы «Цена за единицу измерения, руб.» используем исходные данные базового прайс-листа. Заполним соответственно наименованию работы ее цену за единицу измерения в рублях.
11. Для расчета стоимости работ вычислим произведение объема работ на цену за единицу измерения. Для этого установим курсор на ячейке Е2 и выполним действия: Вставка / Функция. В окне Мастера функций выберем в категории «Полный алфавитный перечень» функцию ПРОИЗВЕД, и кнопкой ОК откроем следующее окно под названием «Аргументы функции». В нем в поле «Число 1» выберем ячейку С2, а в поле «Число 2» - ячейку D2. После нажатия кнопки ОК в ячейке Е2 будет рассчитана стоимость работ по замене батарей. Размножим введенную в ячейку E2 формулу для остальных ячеек (с E3 по E5) данной графы. Таблица Расчет стоимости выполняемых работ автоматически заполнится (рис. 6);
Рис.6. Расположение полностью заполненной таблицы «Расчет стоимости выполняемых работ» на рабочем одноименном листе MS Excel
12. Лист 3 переименовать в лист с названием Счет;
13. На рабочем листе Счет MS Excel создать форму счета на оплату выполненных работ (рис.7);
Рис.7. Расположение «формы счета на оплату» на рабочем листе «Счет» MS Excel
14. Путем создания межтабличных связей заполнить созданную форму полученными данными из таблицы Расчет стоимости выполняемых работ;
15. Для расчета итоговой стоимости выполняемых работ в ячейке F12 следует установить курсор и ввести функцию. Для этого выполним действия Вставка / Функция, в категории «Математические» выберем функцию «СУММ». Далее в открывшемся окне «Аргументы функции» в качестве первого числа через кнопку «Просмотр» выделим диапазон F8:F11 и нажмем ОК.
15. Для расчета НДС в ячейку F13 введем формулу самостоятельно. Для этого в ячейке поставим знак равенства «=», щелкнем мышью ячейку F12, далее поставим знак произведения «*», и наконец, введем с клавиатуры «18%». После нажатия «Enter» сумма НДС будет вычислена. Таким образом, НДС составил 18% от общей стоимости работ.
16. В ячейке F14 следует вычислить в рублях сумму, подлежащую оплате клиентом, включая НДС. Для этого, используя функцию «СУММ» сложим итоговую стоимость работ и начисленную сумму НДС (ячейки F12 и F13). Таким образом, таблица «Форма счета на оплату» автоматически заполнится (рис. 8);
Рис.8. Расположение полностью заполненной таблицы «Форма счета на оплату выполненных работ» на рабочем листе «Счет» MS Excel
17. Лист 4 переименовываю в лист с названием График.
18. Для представления результатов расчета стоимости каждого вида работ в графическом виде построим диаграмму (рис. 9).
19. Выполним действия Вставка / Диаграмма. В открывшемся окне на первом шаге построения диаграммы выберем на вкладке «Стандартные» гистограмму объемного вида, и нажмем кнопку «Далее». В новом открывшемся окне на вкладке «Диапазон данных» с помощью кнопки «Просмотр» выделим диапазон F8:F11. В поле «Ряды» установим значение «столбцах». На вкладке «Ряд» в поле «Подписи оси Х» выберем через кнопку просмотра диапазон ячеек В8:В11, и нажмем кнопку «Далее». На следующем этапе построения диаграммы, на вкладке «Заголовки» ось Х обозначим как «Виды работ», ось Z – «Сумма (руб.)». На вкладке «Линии сетки» в поле «Ось Z (значений)» выберем только один пункт – «Основные линии». На вкладке «Легенда», для того чтобы ее вовсе не включать в нашу диаграмму, уберем галочку напротив пункта «Добавить легенду», и нажмем кнопку «Далее».
20. На последнем этапе построения диаграммы в поле размещения ее на листе выберем пункт на листе «имеющемся», и через кнопку «Просмотр» укажем лист под названием «График». Нажав кнопку «Готово» создание диаграммы будет завершено.
Рис.9. Размещение гистограммы результата расчета стоимости каждого вида работ по полученному заказу на рабочем листе «График» MS Excel
Заключение
Современную жизнь представить без современной техники просто невозможно.
Ни одна фирма не обходится без помощи компьютеров. Хранение данных, написание документов, составление графиков, таблиц, расписаний, создание презентаций - во всем в этом нам помогает компьютер, и помогает успешно.
В результате выполнения курсовой работы мы на практике познакомились с проектированием таблиц для решений экономических задач.
В теоретической части мы изучили алгоритмы сортировки, их виды, предназначение и характеристики.
Для молодого специалиста, выпускника института, это весьма важная работа. В работе подробно описывается проектирование таблиц для автоматизации обработки экономических данных. Полученные знания будут способствовать наиболее эффективной работе пользователя с ПК.
Список использованной литературы
1. Информатика: Методические указания по выполнению курсовой работы для самостоятельной работы студентов II курса (первое высшее образование). – М.: Вузовский учебник, 2006, - 60с.
2. Информационные системы в экономике: Учеб. Пособие / Под ред. проф. А. Н. Романова, про. Б. Е. Одинцова – М.: Вузовский учебник, 2008. – 411 с.
2. Симонович С. В., Евсеев Г. А. Практическая информатика: Универсальный курс. – М.: АСТ-ПРЕСС: Инфорком-Пресс, 2001, - 480с.
3. Программирование на языке высокого уровня: Текст лекций/ Н.В. Ефимушкина, С.П. Орлов, В.М. Чухонцев; Самар. гос. техн. ун-т. - Самара, 2002. 182с.
4. Андреева А.Ю., Кайгородова М.А. Лабораторный практикум по информатике. Методические указания по выполнению лабораторных работ по дисциплине «Информатика» для студентов 2 курса. Филиал ВЗФЭИ в г. Барнауле, 2009. – 64 с.
5. Ткачук В. Алгоритмы сортировки - http://base.vingrad.ru/view/130-Algoritmyi-sortirovki
6. Ткачук В. Все о программировании - http://www.ru-coding.com/algoritm_1.php
Внимание!
Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы
Delle Понравилось? Нажмите на кнопочку ниже. Вам не сложно, а нам приятно).
Чтобы скачать бесплатно Курсовые работы на максимальной скорости, зарегистрируйтесь или авторизуйтесь на сайте.
Важно! Все представленные Курсовые работы для бесплатного скачивания предназначены для составления плана или основы собственных научных трудов.
Друзья! У вас есть уникальная возможность помочь таким же студентам как и вы! Если наш сайт помог вам найти нужную работу, то вы, безусловно, понимаете как добавленная вами работа может облегчить труд другим.
Если Курсовая работа, по Вашему мнению, плохого качества, или эту работу Вы уже встречали, сообщите об этом нам.
Добавление отзыва к работе
Добавить отзыв могут только зарегистрированные пользователи.