Информационный центр "Центральный Дом Знаний"
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
Алгоритмы сортировкиОГЛАВЛЕНИЕ ВВЕДЕНИЕ...………………………………………………….……………………..3 1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ……………………………….………………………5 1.1. Понятие алгоритма………...……………...…...…..……………………….…..5 1.2. Алгоритмы сортировки...……………………………...…………………...…..7 2. ПРАКТИЧЕСКАЯ ЧАСТЬ……………………………………………………...12 2.1. Практическое задание №7………...………….………………….…….……..12 2.2. Описание порядка выполнения практического задания……………....……13 ЗАКЛЮЧЕНИЕ……………………………………………………………….…….21 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ……...……………...…………22 ВВЕДЕНИЕ Успешное выполнение большинством специалистов своих функциональных обязанностей в настоящее время во многом определяется умелым использованием персональных компьютеров, средств коммуникаций, профессиональных пакетов прикладных программ, различного рода интеллектуальных информационных технологий. Процессы информатизации общества обусловили необходимость формирования у студентов знаний в области информатики и компьютеризации управленческих процессов. Одно из широко используемых понятий информатики определяет ее как науку, изучающую общие свойства информации, а также методы, процессы, технические и программные средства для ее автоматизированной обработки. Сам термин «информатика» (informatique) возник в 60-х годах во Франции для определения области исследований, связанных с автоматизацией обработки информации с помощью электронных вычислительных машин (ЭВМ). Этот термин был образован слиянием слов information (информация) и automatique (автоматика) для обозначения информационной автоматики или автоматизированной переработки информации. Данная курсовая работа состоит из двух частей: теоретической и практической. Целью теоретической части курсовой работы является ознакомление с алгоритмами сортировки, попытка проанализировать их и осветить каждый из них. В практической части курсовой работы с помощью пакетов прикладных программ (ППП) будут решены и описаны следующие задачи: создание таблиц и заполнение таблиц данными; применение математических формул для выполнения запросов в ППП; построение графиков. Краткие характеристики ПК и программного обеспечения, использованных для выполнения и оформления курсовой работы: Процессор: 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) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает, что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов. Формы представления алгоритма: Словесная форма; Словесно-аналитическая форма; В виде блок-схемы (графическое изображение алгоритма); В виде программы на алгоритмическом языке программирования. Виды алгоритмических структур: Линейный алгоритм, в которой все команды выполняются последовательно одна за другой. Разветвляющийся, в которой в зависимости от условия выполнения либо одна серия команд, либо другая. Циклический, в которой многократно повторяется некоторый участок алгоритма. 1 поколение алгоритмических языков - конец 1950-х начало 1960-х. Совершенствовались ассемблерные языки. В настоящее время они применяются для создания драйверов оборудования ПК. 2 поколение - 60е годы. В это время появляются универсальные языки высшего уровня: ФОРТРАН, АЛГОЛ, КОБОЛ, обеспечивающие создание программ для решения задач различного класса. 3 поколение. С начала 1970-х годов начался переход на создание больших программных комплексов. Они в основном применяются для проектирования приложений баз данных и средств визуального программирования. В середине 1990-х – 4 поколение языков программирования, назначение которых для образования инструкции текст программ на универсальном языке программирования. Система 4 поколения имеет открытую архитектуру и поддерживает значительное число программных продуктов. Языки программирования: Бейсик отличается встроенными математическими функциями и простыми языковыми конструкциями. Паскаль предназначен для решения вычислительных и информационно-логических задач. Си + + был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую. Ада ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем. Java (джава) предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети. другим объектно-ориентировочным языком является язык Delphi (дельпхи). Обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети интернет. Алгоритмы сортировки Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. Практически каждый алгоритм сортировки можно разбить на три части: сравнение, определяющее упорядоченность пары элементов; перестановку, меняющую местами пару элементов; собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены. Подобными свойствами обладают и те алгоритмы сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что, во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь. Основные виды сортировок: 1. Сортировка пузырьком. Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся не отсортированных N-1 элементов (т.е. для тех, которые лежат "ниже" первого). Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод. 2. Сортировка перемешиванием. Сортировка перемешиванием (шейкер-сортировка) — разновидность ïуçырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие — к началу. 3. Сортировка методом вставок. Сортировка вставками элементов a1, a2, …, an относится к наиболее очевидным методам. При таком подходе вводится фиктивный элемент a0=-, а затем каждый элемент, начиная со второго, сравнивается с элементами уже упорядоченной части последовательности и вставляется в нужное место. При вставке элемент aj временно размещается в переменной w, и просматриваются элементы aj-1, aj-2, …,a1 (уже к этому времени упорядоченные). Они сравниваются с w и сдвигаются, если обнаруживается, что они больше чем w. Сложность алгоритма определяется числом проверок условия w<a[i] в цикле. В худшем случае потребуется n(n-1)/2 таких сравнений, то есть сложность сортировки вставками - квадратичная. 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 и 3 будут относительно медленными. 10. Поразрядная сортировка. Поразрядная сортировка — быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки ïерфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным àлфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый àлгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для старших букв. 2. ПРАКТИЧЕСКАЯ ЧАСТЬ 2.1. Практическое задание №7 Фирма ООО «Стройдизайн» осуществляет деятельность, связанную с выполнением работ по ремонту помещений. Прайс-лист на выполняемые работы приведен на рис. 2.1. Данные о заказанных работах указаны на рис 2.2. Построить таблицы по приведенным в приложениях данным. Выполнить расчет стоимости выполняемых работ по полученному заказу, данные расчета занести в таблицу (рис. 2.2). Организовать межтабличные связи для автоматического формирования счета, выставляемого клиенту для оплаты выполняемых работ. Сформировать и заполнить счет на оплату (рис. 2.3). Результаты расчета стоимости каждого вида работ по полученному заказу представить в графическом виде. Прайс-лист Наименование работы Единица измерения Цена за ед. изм., руб. Замена батарей шт. 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 – программа, не требующая знаний программирования, достаточно проста в использовании для поиска результата данной задачи. Порядок выполнения практического задания следующий: Запустить табличный процессор MS Excel. Создать книгу с именем «Стройдизайн». Лист 1 переименовать в лист с названием Работа. На рабочем листе Работа MS Excel создать таблицу базового прайс-листа на выполняемые работы. Заполнить таблицу базового прайс-листа исходными данными (рис. 2.4). Рис. 2.4. Расположение таблицы «Прайс-лист» на рабочем листе Работа MS Excel Разработать структуру шаблона таблицы «Расчет стоимости выполняемых работ» (рис. 2.5). Колонка электронной таблицы Наименование (реквизит) Тип данных Формат данных - длина A Наименование работы текстовый 15 B Единица измерения текстовый 15 C Объем выполняемых работ числовой 2 D Цена за ед. изм., руб. числовой 4 E Стоимость работ, руб. числовой 5 Рис. 2.5. Структура шаблона таблицы «Расчет стоимости выполняемых работ» Лист 2 переименовать в лист с названием Данные о заказе. На рабочем листе Данные о заказе MS Excel создать таблицу, в которой будут содержаться данные о поступившем заказе. Заполнить таблицу «Расчет стоимости выполняемых работ» исходными данными (рис. 2.6). Рис. 2.6. Расположение таблицы «Расчет стоимости выполняемых работ» на рабочем листе Данные о заказе MS Excel Заполнить графу Цена за ед. изм., руб. таблицы «Расчет стоимости выполняемых работ», находящейся на листе Данные о заказе следующим образом: Занести в ячейку D4 формулу: =Работа!С3 В ячейку D5 занести: =Работа!С6 Аналогично сделать и в ячейках D6, D7. Заполнить графу Стоимость работ, руб. таблицы «Расчет стоимости выполняемых работ», находящейся на листе Данные о заказе следующим образом: Занести в ячейку E4 формулу: =C4*D4 Размножить введенную в ячейку E4 формулу для остальных ячеек данной графы (с E5 по E7) (рис. 2.7 и рис 2.8). Расчет стоимости выполняемых работ Наименование работы Единица измерения Объем выполняемых работ Цена за ед. изм., руб. Стоимость работ, руб. Замена батарей шт. 4 250 1000 Наклейка обоев кв.м 20 50 1000 Замена труб м 4 240 960 Настилка паркета кв.м 15 75 1125 Рис. 2.7. Данные о поступившем заказе на 01.02.2009г. Расчет стоимости выполняемых работ Наименование работы Единица измерения Объем выполняемых работ Цена за ед. изм., руб. Стоимость работ, руб. Замена батарей шт. 4 =Работа!C3 =C4*D4 Наклейка обоев кв.м 20 =Работа!C6 =C5*D5 Замена труб м 4 =Работа!C5 =C6*D6 Настилка паркета кв.м 15 =Работа!C7 =C7*D7 Рис. 2.8. Расположение формул в таблице «Расчет стоимости выполняемых работ» Лист 3 переименовать в лист с названием Форма счета. На рабочем листе Форма счета MS Excel создать форму счета на оплату выполненных работ. Путем создания межтабличных связей заполнить созданную форму полученными данными из таблицы «Расчет стоимости выполняемых работ» (рис. 2.9 и рис 2.10).(......) |
Loading
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||