Центральный Дом Знаний - Алгоритмы сортировки

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 854



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


Оглавление
   стр.  
Введение………………………………………………………………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а (быстрая сортировка)
Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым методом сортировки из тех, что оперируют сравнениями. Суть этого метода заключается в том, чтобы найти такой элемент сортируемой последовательности, который бы делил последовательность на две части так, что слева от него находились бы элементы не меньшие его, а справа – не большие. Поиск такого элемента можно организовать многими способами.
Поразрядная сортировка
Быстрая устойчивая сортировка за линейное время, использовалась в устройствах для сортировки ïерфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным àлфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый àлгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для  старших букв.
Пирамидальная сортировка
Этот метод является значительно более сложным, но при этом и более быстрым (особенно на больших массивах информации) алгоритмом. Здесь используется промежуточное преобразование данных к специальному представлению, которое позволяет производить дальнейшую сортировку быстрее. В результате, общее число сравнений и обменов записей местами существенно уменьшается, что особенно важно в случае больших массивов данных.
Сортировка массивом (хеширование)
Суть метода заключается в заполнении вспомогательного массива, содержащего элементы несколько больше, чем исходная последовательность. Заполнение этого вспомогательного массива происходит таким образом: вычисляются значения некоторой монотонной функции, называемой хэш-функция, на элементах сортируемой последовательности и эти значения считаются индексами этих элементов в заполняемом массиве. Если же окажется, что подлежащий заполнению элемент вспомогательного массива уже занят, то происходит сдвиг соответствующих элементов этого массива так, чтобы образовалось "окно” для вносимого элемента и сохранялась упорядоченность между элементами. Функция должна выбираться так, чтобы ее значения лежали внутри диапазона индексов вспомогательного массива.
Цифровая сортировка 
Этой сортировкой можно сортировать целые неотрицательные числа большого диапазона. Идея состоит в следующем: отсортировать числа по младшему разряду, потом устойчивой сортировкой сортируем по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы.(......)
Loading

Календарь

«  Август 2017  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
28293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей